Содержание к диссертации
Введение
2. Основные определения и вспомогательные понятия 11
2.1. Формальная постановка задачи 11
2.1.1. Лабиринты, в которых происходит преследование . 11
2.1.2. Взаимодействие автоматов 12
2.1.3. Рассматриваемые проблемы 15
2.2. Вспомогательные понятия 16
2.2.1. Вспомогательные определения 16
2.2.2. Композиции автоматов 19
2.2.3. Построение вспомогательных автоматов 20
3. Преследование независимой системой хищников жертв 22
3.1. Траектории автомата в исследуемых лабиринтах 22
3.2. Невозможность поимки жертв независимой системой хищников на плоскости 27
4. Преследование коллективом хищников жертв в бесконечных лабиринтах 30
4.1. Поимка автоматов-жертв с периодическим поведением . 30
4.1.1. Леммы о перемещении автоматов 30
4.1.2. Вычисление коллективом автоматов арифметических функций от параметров, заданных расстановкой автоматов 38
4.1.3. Доказательство возможности поимки жертв с периодическим поведением 44
4.2. Поимка автоматов-жертв с непериодическим поведением . 63
4.2.1. Леммы о перемещении автоматов в квадранте . 63
4.2.2. Вычисление коллективом автоматов еще ряда арифметических функций от параметров, заданных расстановкой автоматов 67
4.2.3. Вычисление параметров жертвы по ее коду 76
4.2.4. Доказательство возможности поимки непериодических жертв в квадранте 84
4.3. Доказательство основной теоремы 106
5. Преследование коллективом хищников жертв внутри квадрата 108
5.1. Поимка данной системы автоматов-жертв 108
5.2. Построение автоматов-жертв, убегающих
от данного коллектива хищников 111
5.3. Доказательство теоремы о преследовании внутри квадрата . 114
Список литературы 117
- Взаимодействие автоматов
- Построение вспомогательных автоматов
- Вычисление коллективом автоматов арифметических функций от параметров, заданных расстановкой автоматов
- Доказательство возможности поимки непериодических жертв в квадранте
Введение к работе
Актуальность темы
Целью работы является постановка и решение задачи математического моделирования процесса преследования группой хищников группы жертв. Геометрия пространства, в котором происходит преследование, моделируется шахматным лабиринтом (т.е. графом определенного вида). Механизмы восприятия и принятия решений перемещающихся объектов - «хищников» и «жертв» моделируется при помощи конечного автомата. Таким образом, задача преследования получает автоматную трактовку и решается в этой постановке методами дискретной математики.
Подобная задача преследования подвижного объекта другим объектом или системой объектов имеет очевидные приложения в биологии, военном деле, робототехнике.
Задача взаимодействия популяций хищников и жертв решалась давно, начиная с Вольтерра1. Для нас более актуальна задача преследования хищниками жертв без моделирования процессов размножения.
Автоматный подход к решению задачи преследования впервые был применен в 1987 г. В. И. Грунской 2. В этой работе рассматривалось взаимодействие двух конечных автоматов W и Z - «хищника» и «жертвы» в шахматных лабиринтах, имеющих вид квадрата со стороной /. Хищники и жертвы обладали способностью видеть происходящее в клетках, соседних с той, в которых они находились и перемещаться за 1 такт на одну клетку по вертикали, по горизонтали или оставаться на месте. Было показано, что для любых /,п Є N существует W с числом состояний 0(п /2), который ловит за время 0(п /4) любой автомат-жертву Z с числом состояний не большим п, в квадрате со стороной, не большей /, при любом начальном расположении W и Z. Также было установлено, что не существует автомата W, ловящего любой Z в произвольном квадрате с фиксированной длиной стороны /, / > 8.
В данной работе автоматная модель преследования хищниками жертв, построенная в работе Грунской, получает свое развитие. Ситуация обобщается по трем параметрам: происходит вариация геометрической среды, в которой происходит преследование, рассматриваются системы хищников и жертв, состоящие из нескольких автоматов, при этом автоматы могут иметь произвольный обзор и произвольные скорости, не превосходящие
1 В.Вольтерра. Математическая теория борьбы за существование, Москва, 2004. 2Грунская В.И., О динамическом взаимодействии автоматов, в кн.: Математическая кибернетика и ее приложения к биологии, МГУ, 1987, стр. 8-18.
обзор.
В качестве пространства преследования рассматриваются несколько типов лабиринтов, являющихся подмножествами плоскости, разбитой на квадраты целочисленной решеткой. Хищники и жертвы представляются в виде инициальных конечных автоматов, которые, находясь в какой-либо клетке лабиринта, умеют обозревать некоторую ее окрестность, и, в зависимости от вида (конфигурации) этой окрестности (т.е. от расположения границы лабиринта и других автоматов в этой окрестности) и своего состояния, способны перемещаться в другую клетку лабиринта. За 1 такт автомат способен переместиться в любую клетку своей окрестности хода. Возможности обзора определяются радиусом обзора автомата, а размер окрестности хода - скоростью автомата, которая не превышает радиус обзора.
Автоматы-хищники и автоматы-жертвы в начале процесса образуют определенную диспозицию, находясь в своих начальных состояниях. После этого начинается процесс перемещения автоматов. В четные такты ходят все жертвы одновременно, в нечетные — все хищники одновременно. Допускается ситуация, когда в одной клетке лабиринта одновременно находится несколько автоматов.
В теории автоматов в лабиринтах рассматривается два способа взаимодействия автоматов. Группа автоматов, перемещающаяся в лабиринте называется независимой системой^ если поведение (т.е. траектория и последовательность внутренних состояний) каждого из этих автоматов не зависит от поведения других автоматов данной группы. Второй возможный способ взаимодействия автоматов в лабиринте заключается в том, что входной символ каждого из этих автоматов зависит от того, присутствуют ли другие автоматы из этой группы в его окрестности обзора, от их распределения в его окрестности обзора, и от состояний тех автоматов, которые оказались в его окрестности обзора. Таким образом, каждый автомат такой группы, при «встрече» с другими автоматами этой группы, способен менять свое поведение, в зависимости расположений и состояний тех автоматов, с которыми он встретился. Группа автоматов, которая взаимодействует таких образом, называется коллектив. Понятно, что независимая система автоматов является простейшим случаем коллектива.
В настоящей работе предполагается, что все жертвы взаимодействуют между собой, как независимая система (при этом, конечно, каждая жертва имеет возможность реагировать на хищников, попавших в ее зону обзора). Гассмотрены оба случая взаимодействия хищников между собой: когда хищники являются независимой системой автоматов, и когда хищники являются коллективом автоматов (в обоих случаях каждый хищник
имеет возможность реагировать на жертв, попавших в его зону обзора).
Жертва считается пойманной, если она оказалась в фиксированной окрестности одного из хищников. Такая жертва исчезает из лабиринта. Система жертв поймана, если пойманы все жертвы.
В данной работе рассматривается случай, когда хищники имеют большую, чем жертвы, скорость, и не меньший, чем жертвы, обзор. Это мотивированно тем, что большинство рассматриваемых лабиринтов являются бесконечными, а для таких лабиринтов, в случае, когда жертва имеет не меньшую скорость, чем хищники и благоприятное начальное расположение относительно хищников, разумное поведение жертвы приведет к тому, что эта жертва никогда не будет поймана (убежит). Таким образом, для бесконечных лабиринтов вопрос о возможности поимки жертв становится содержательным тогда, когда хищники имеют превосходство в скорости.
Фиксируем скорости и обзоры хищников и жертв.
Цель работы
Решение для рассматриваемых классов лабиринтов проблемы существования универсального коллектива хищников, ловящего любую конечную независимую систему жертв при их произвольном начальном расположении в любом лабиринте данного класса.
Для тех классов лабиринтов, для которых первая проблема имеет отрицательное решение, изучение вопроса о возможности поимки данной независимой системы жертв некоторым коллективом хищников при произвольном начальном расположении жертв в любом лабиринте данного класса.
Структура и объем диссертации
Взаимодействие автоматов
Под автоматом будем понимать инициальный конечный автомат (см. [2]) вида A = (A, Q, В, Lp,ip,qo), где А —входной, В — выходной, Q — внутренний алфавиты автомата A, (p:QxA-+Qnip:QxA— B — функции переходов и выходов А, соответственно, qo Є Q — его начальное состояние. Алфавит А определяет возможности А «видеть» происходящее вокруг, а алфавит В — его возможности перемещаться. Алфавит Q и функции (р и ф задают внутреннюю логику автомата А. Пусть дан лабиринт L, являющийся одним из вышеописанных лабиринтов. Рассмотрим автомат А, перемещающийся в L. Выходным алфавитом А является множество В = -D(0)o),y, где параметр VGN называется ско ростъю автомата Л. Входной алфавит Л зависит от параметра R Є N (R V), называемого обзором автомата Л и способа взаимодействрш Л с другими автоматами. Возможны два случая такого взаимодействия: 1) Л является элементом независимой системы автоматов; 2) Л является элементом коллектива автоматов. Автомат со скоростью V и обзором R будем обозначать как A(R: V). Пусть A(R: V) находится в клетке (жо 2/о)- Множество D yo v П L называется окрестностью хода Л, а множество D(XQ Уо) (R-I) П L — зоной обзора Л. Рассмотрим две системы автоматов К = (W\,..., Wm) (R, V) (хищники) HS = (UI,..., Un)(R i V) (жертвы), где R и R! — обзоры, а У и У — скорости хищников и жертв, соответственно. Здесь »5 — независимая система автоматов, К — независимая система или коллектив автоматов. Пусть каждая жертва Щ находится в клетке (х {, y j) лабиринта L, а каждый хищник Wj находится в клетке (xj,yj) лабиринта L в состоянии qj. Положим N = (і? +1)2+(Я/)2 - количество клеток множества D(x yo RI, т.е., максимально возможный размер зоны обзора жертвы (это число одинаково для всех клеток (XQ, УО))- Для каждого і = 1,..., п определим строку [а ъ ..., a N,) следующим образом. Для любого k = 1,..., N Строку (а ъ ... ,a N,) назовем V -конфигурацией. Каждая -конфигурация однозначно задает клетки зоны обзора Щ, не принадлежащие лабиринту, а также клетки зоны обзора Ui, в которых находятся хищники. Положим N = (R-\-V)2 Ч- Я2 - количество клеток множества D(XQ Q R , т.е., максимально возможный размер зоны обзора хищника (это число также одинаково для всех клеток (хо:уо)). Если К — независимая система автоматов, то для каждого j = 1,... , m определим строку ( 2i,..., a r) следующим образом. Для любого k = 1,... ,N —1 ,если к-я клетка множества D x.iV R не принадлежит лабиринту L; ак = 1 , если в к-й клетке множества D(x у ц находится (1) хотя бы одна жертва; О , иначе.
Строку (ai,..., од/") назовем Wj-конфигурацией. Каждая И -конфигурация однозначно задает клетки зоны обзора Wj, не принадлежащие лабиринту и клетки зоны обзора Wj, в которых находятся жертвы. Если К — коллектив автоматов, то для каждого j = 1,..., т определим строку (ai,... ,ajv+m) следующим образом. Обозначим внутренний алфавит Wj как Qj, а множество всех пар вида ((x,y),q), где (х,у) Є D(o,o),i?, q Є [JjLi Qj - как М. Для любого к = 1,..., N символ а определяется равенством (1). Положим для любого р = 1,... ,т, р j a N+p = Положим ((хр - Xj, ур - yj), qp) , если \хр - Xj + \ур - у5\ R; (2) Л , иначе. aN+j = Л. (3) Строку (ai,... , 2лг+тп), определенную равенствами (1) — (3), назовем Wj-конфигурацией. Легко видеть, что а +Р Є (М U {Л}) при р = 1... т. Каждая --конфигурация однозначно задает клетки зоны обзора Wj, .не принадлежащие лабиринту, клетки зоны обзора Wj, в которых находятся жертвы, а также расположения и состояния других хищников, находящихся в зоне обзора Wj. Расположения в лабиринте L жертв и хищников и состояния хищников однозначно задают все [/{-конфигурации и все Wj-конфигурации. Множества всех [/ -конфигураций и всех И -конфигураций при всевозможных расположениях жертв и хищников и состояниях хищников конечны. Обозначим множество всех [/{-конфигураций как F . Аналогично, множество всех Wj-конфигураций обозначим как F. Входным алфавитом каждой жертвы Ui является множество всех пар вида {Т\_, Т ), где Т[ Є ({0} U F ), а Т 2 Є F . Входным алфавитом каждого хищника Wj является множество всех пар вида {Т\,р2), где Т\,Тъ Є F. Момент времени 2т (г Є No) называется т-моментом хода жертв. Момент (2т+ 1) называется г-моментом хода хищников. Промежуток времени [2т, (2т + 1)] называется тактом с номером т. Время взаимодействия автоматов будем измерять в тактах. Преследование системой хищников независимой системы жертв происходит так. Фиксируются начальные (в нулевой момент времени) расположения всех хищников и жертв на плоскости. В нулевой момент каждая жертва Ui воспринимает в качестве входного символа пару (0, ), где -конфигурация - 2 задает клетки зоны обзора Ui, не принадлежащие лабиринту, и клетки зоны обзора Ui, в которых находятся хищники. В момент 2т (т Є N) каждая жертва U{ воспринимает в качестве входного символа пару {Т ЪТ ), задающую клетки зоны обзора Ui, не принадлежащие лабиринту, и клетки зоны обзора Ui, в которых находятся хищники в момент (2т — 1) ив момент 2т. В каждый момент 2т (т G No) жертва Щ, в соответствии со своими функциями переходов и выходов, определяет свое следующее состояние, выходной символ Ь, и перемещается на вектор Ь. В момент (2т + 1) (т Є No) хищник Wj воспринимает в качестве входного символа пару {Т\,Т2), задающую клетки зоны обзора Wj, не принадлежащие лабиринту, клетки зоны обзора Wj, в которых находятся жертвы в момент 2т и в момент (2т + 1), а также, если хищники представляют собой коллектив автоматов, расположения и состояния других хищников, находящихся в зоне обзора Wj в моменты 2т и (2т + 1).
В соответствии со своими функциями переходов и выходов, хищник определяет свое следующее состояние, выходной символ Ь, и перемещается на вектор Ь. Будем рассматривать только такие автоматы (жертв и хищников), для которых перемещение на вектор, равный выходному символу Ъ никогда не выводит за пределы лабиринта, в котором происходит преследование. Система хищников К «ловит» жертву, если жертва в некоторый момент времени оказалась в окрестности хода одного из хищников. Пойманная жертва исчезает из лабиринта. Если система хищников не ловит некоторую жертву, будем говорить что эта жертва убегает от данной системы хищников. К «ловит» независимую систему жертв, если в процессе преследования К ловит каждую жертву. 2.1.3. Рассматриваемые проблемы Задача преследования решается в ситуации, когда фиксированы скорости и обзоры хищников и жертв. Значения скоростей хищников и жертв — V и Vі, соответственно, а обзоров —Я и R!, соответственно. V, V, R и R! — произвольные натуральные числа, удовлетворяющие неравенствам R V, R1 V ,R R , V V. Для каждого типа лабиринтов {LQ, L\, L2, L3, L4 и Ь$) ставится вопрос: существует ли коллектив хищников K(R, V), такой что для любого лабиринта L данного типа, существует такое начальное расположение хищников в L, что коллектив К ловит произвольную конечную независимую систему жертв S(R , V), при любом начальном расположении жертв из S в лабріринте L. Данная проблема для независимых систем хищников решена для слу
Построение вспомогательных автоматов
Неподвижный автомат с 1 состоянием будем обозначать TCQ. Автомат с 1 состоянием, который за каждый такт смещается на 1 вправо, будем обозначать Тії. Построим два семейства автоматов, зависящих от параметров sx,sy Є Z и р Є N (1 1 + \sy\ V, р 2) и от некоторого автомата А. Пусть автомат А неподвижен. Тогда 7Ї2 = Н 2(А, (sx, sy))(V, У) — автомат, который, стартуя из начального состояния (g, gi) (g Є { — 1,1}), за каждый такт смещается на вектор q (sx, sy), пока не увидит А. Увидев А, автомат 7 2 ходит в расположение А и останавливается. 1){Н2(А, (sx, sy)), { - 1,1} х {qu q2}). 2) H2(A,(sx,sy))}((q,qi), Pv(H2(A,(sx,sy)),A) = 1), - ((g,g2), ход в расположение А), где q Є { — 1,1}. 3) H2(A, {sx, Sy)),((q, 9i), Ру(7і2(Л {sx, sy)), A) = 0), -+ ((g, gi), g (sx, sy)), где g Є { - 1,1}. Hz = 1 з(А, (sx, sy),p)(V, V) — автомат, который, стартуя из начального состояния (д, ді) (д Є { — 1,1}), в такты вида р к + h (k,h Є No, 0 h p — 2) смещается на вектор g (sx, sy), а в такты вида p к 4- (p — 1) стоит на месте. Такое движение продолжается, пока Тїз в состоянии (д, др) не окажется в одной клетке с автоматом А (который уже не предполагается неподвижным). Оказавшись в состоянии (g, qp) в одной клетке с А, автомат Нз останавливается. 1)( з(Л( Sx, Sy ),р),{-1,1} х {gb...,gp+i}). 2) Нз(А, (sx, sy),p), ((g, %)), -н- ((g, fc+i), g (sx, sy)), где g є { - 1,1}, 1 i p-l. 3) W3(A (sXi sy),p), ((g, qp), Р0(Пз(А, (sx, sy),p), A) = 0)), - ((g, ft), (0,0)), где g Є { - 1,1}. 4) H3(A, (sx, sy),p), ((g, gp), Р0( з(Л (. s„),p), A) = 1)), - ((g, gp+i), (0,0)), где g Є { - 1,1}. Рассмотрим перемещение произвольного автомата А в лабиринте L одного из рассматриваемых типов (плоскость, полуплоскость, полоса ширины I, полуполоса ширины I, квадрант, квадрат со стороной I). Пусть в зону обзора этого автомата на рассматриваемом промежутке времени не попадают другие автоматы. Оказывается, что в большинстве рассматриваемых лабиринтов последовательность выходных символов и состояний А будет периодической. Лемма 3.1. Произвольный автомат A = A{R: V) с п состояниями, перемещающийся по плоскости LQ так, что другие автоматы не попадают в его зону обзора, имеет периодическую последовательность выходных символов и длина периода этой последовательности d, длина предперио-да do и перемещение s автомата А за период этой последовательности удовлетворяют неравенствам do + d п, \s\ V d.
Доказательство. Т.к. в зону обзора А не попадают другие автоматы, его входной символ постоянен. Поскольку А имеет п состояний, не позднее чем через п тактов он окажется в состоянии, в котором уже находился. Выходные символы и состояния А будут повторяться с длиной предпериода do и периода d, причем do + d п. Рассмотрим период bi,... , выходной последовательности автомата А. Т.к. A(R: V) имеет скорость У, для каждого і = 1,..., d выполнено \b i\ V. Следовательно, \s\ = \bi +... +Ъа\ V d. Лемма доказана. Аналогичный результат имеет место для полуплоскости, полосы ширины I и полуполосы ширины I. Лемма 3.2. Произвольный автомат Л = A(R, V) с п состояниями, перемещающийся в лабиринте L Є {Ьі} U {1/2(/) / Є N} U {Ь%(1) \l N} так, что другие автоматы не попадают в его зону обзора, имеет периодическую последовательность выходных символов. Верны соотношения: 1) d R [п + 1) п, s2 0, \s\ V d, если L — Lb 2) do + d l -п, s2 = 0, \s\ V d, если L = L2(l); 3)d l2-R-(n + l)-n, si 0,52 = 0, \i\ V-d, еслиЬ = Ь3(1). Доказательство. Предположим, доказано, что автомат Л перемещается в лабиринте L с периодической выходной последовательностью, длина периода которой d. Рассмотрим период Ъ\,..., Ьа этой выходной последовательности. Т.к. A(R, V) имеет скорость V, для каждого г = 1,..., d выполнено \Ъ{\ V. Следовательно, s = Ьі + . . + 6 V d. Докажем теперь периодичность выходной последовательности автомата и остальные соотношения отдельно для разных типов лабиринтов. 1) Пусть L = L\. Рассмотрим 3 случая. а) ів процессе движения никогда не видит борта полуплоскости. В этом случае А перемещается так же, как автомат на плоскости. По лемме 3.1. он имеет периодическую последовательность выходных символов, при чем d п R (п 4- 1) п. Очевидно, S2 0 (иначе бы А рано или поздно подошел бы к борту на расстояние, не превосходящее R). б) А видит борт в некоторый момент ()? но никогда не покидает (R (те+1))-окрестность борта. Поскольку А имеет п состояний, не позднее чем через R - (п + 1) п тактов он окажется в состоянии, в котором уже нахо дился в некоторый момент t, t ioj и на том же расстоянии от борта, что и в момент t. Далее Л будет периодически перемещаться в горизонталь ном направлении, выходные символы и СОСТОЯНРІЯ Л будут повторяться с длиной периода d R (п + 1) n, S2 = 0. в) Л видит борт в некоторый момент to, а затем, в момент покидает (R- (n + 1))-окрестность борта. Обозначим наибольший момент из интер вала [to, 2]) в который Л видит борт, как t±. Таким образом на интервале времени [ti + 1, 2] автомат Л не видит борта. Т.к. A(R, V) имеет скорость V, для того чтобы покинуть (R- (п+1))-окрестность борта, ему нужно хотя бы [ ("" V" ] п тактов перемещаться, не видя борта. По лемме 3.1. авто мат Л начнет перемещаться с периодической последовательностью выход ных символов, сумма длин предпериода и периода которой не превосходят п. Обозначим перемещение автомата за период этой последовательности как s = (si,S2). Очевидно, 52 0 (иначе Л не покинул бы (R (n + 1)) окрестность борта). Значит, Л далее никогда не увидит борта, и будет все время перемещаться, как автомат на плоскости. В этом случае, по лемме 3.1., d n R-{n + l)-n. Таким образом, п.1 данной леммы (полуплоскость) полностью разобран. 2) Пусть L = Ьг(Z). Поскольку Л имеет п состояний, не позднее, чем через / п тактов после начала функционирования, Л окажется в состоянии, в котором уже находился в некоторый момент t, и на тех же расстояниях от верхнего и нижнего бортов, что и в момент t. Далее Л будет периодически перемещаться в горизонтальном направлении, выходные символы и состо
Вычисление коллективом автоматов арифметических функций от параметров, заданных расстановкой автоматов
В этом параграфе будет введено несколько типов специальных расстановок автоматов в лабиринте. Большинство автоматов коллектрша пррі каждой РІЗ этих расстановок будут находиться в одной клетке, которая называется центром расстановки. Типы расстановок отличаются тем, какріе из автоматов находятся в других клетках и где по отношению к центру расстановки находятся эти автоматы. Расстояние от этих удаленных автоматов до центра расстановки определяет ее параметры. Таким образом возюікают (а, Ь)-расстановки, ( 2i, а2, b, hi, Д2)-расстановки, и т.д. Оказывается, что существуют коллективы автоматов, в определенном смысле вычисляющие арифметические функции от параметров а, Ъ и других параметров, задаваемых расстановкой из которой данный коллектив автоматов стартует. «Вычисление» коллективом функции / от заданных параметров (например а и 6), означает либо то, что стартуя из (а, 6)-расста-новки автомат функционирует время f(a, Ъ), либо то, что он в результате вычислений остановится, например, в (а, /(а, 6))-расстановке, либо в какой-то другой расстановке, одним из параметров которой будет /(а, Ь). Теперь приведем строгие определения расстановок и необходимые леммы. Фиксируем натуральное V 2. Если коллектив К = (Ai,..., Ат) (т 4), расположен в лабиринте L так, что A i и Аз находятся в клетках (ж0 + а, уо) и (хо + Ь, уо), соответственно, (где а Є No, b Є N, а b), а все остальные автоматы расположены в клетке (хп,уо), то будем говорить, что коллектив К находится в (а, &)-расстановке с центром (хо,уо). Пусть L - произвольный из рассматриваемых лабиринтов: LQ, LI, L2(), L3{1), Ь4 или L5(l). Лемма 4.7.
Для любого с Є N существует коллектив KC(V,V) — (А\,... ..., Аъ ), который, при произвольных а, 6, (хо, т/о), стартуя в лабиринте L из (а, Ь)-расстановки с центром (хо,уо), функционирует 2а c-]b/V[ тактов и останавливается в той же расстановке. Доказательство. Идея доказательства такова. При а = 0 все автоматы стоят на месте. При а 0 происходит следующее. Автоматы А\ и Аз неподвижны, и автомат As перемещается от А\ к Аз и обратно. На каждый такой проход туда-обратно тратится 2c-]b/V[ тактов. Автомат Аъ совершает а проходов, после чего коллектив останавливается. Опишем функционирование коллектива Кс, стартовавшего в нулевой такт из (а, 6)-расстановки с центром (хо,уо) (а 0), более подробно. Для каждого логического фрагмента описания Кс приведем соответствующие строки схемы его функционирования. Перечень автоматов и их внутренних алфавитов. Все состояния автомата А\ являются начальными. Начальными состояниями автоматов А± И АЪ являются q и (gf, 1), соответственно. Автомат Аъ будет перемещаться только в такты вида с т, т Є N. В такие такты он будет находиться в состояниях вида (qf,c) (і = 1,2). Находясь в других состояниях, Аъ стоит на месте. 2) Лз, ((gf, j)), - ((qf,j + 1), (0,0)), где г = 1,2, 1 j с. Автомат Ль движется в сторону Аз, за каждые с подряд идущих тактов перемещаясь на вектор (У, 0), пока не окажется в той же клетке, что и Аз, или правее. 3) Л5, ((gf,c), {{Р0{Аъ,Аг) = 0) V (Л)(Л,Л) = 0)) Л (Ру(А5,А3) = 0)), - ( ,1),(1/,0)). 4) Л, ((д15,с),((Р0(Л,Л) = 0) v (P0(As,A2) = 0)) Л (Р„(Л,.4з) = і)), -((d.l).(V,0)). Этот этап завершится в такт с-]&/У[. Затем Аъ движется обратно в сторону А\, за каждые с подряд идущих тактов перемещаясь на вектор (—V, 0), пока не окажется в одной клетке с А\. 5) Л5, ((ql с), (РИЛ, Л) = 0)), - ((д, 1), (-У, 0)). 6) Л, ((gf, с) (ДКЛ , Лі) = 1)Л(Р (Д5, Л, 9i) = 0)Л(Л не видит слева от себя АА, находящегося на 1 клетку левее Аъ)), —» ((gf, 1), (—V, 0)). 7) Л, (ЙІ, с), (Ру(Л, Л) = 1) Л ((Р (Л, Л, qf) = 1) V (Л видит слева от себя Л, находящегося на 1 клетку левее Л))), — (gf, (—У, 0)).
Этот этап завершится в такт 2с-]6/У[. Если автомат Аъ окажется в этот такт в состоянии gf, он останавливается. В противном случае Аъ снова пойдет к Az (см п. 4)-7) ). Во время каждого, кроме последнего, прохода Аъ от Аз обратно к А\ совершается перемещение автомата АА на 1 в сторону Аъ- Автомат А\, увидев Аъ в состоянии (gf, 1) правее себя, сдвигается на (1, 0), если расстояние от АА ДО АЪ больше 1. 8) Л4, (Й, (Ру(Л4, Л, {ql 1)) = 1) Л (Л правее АА) Л (Pi(Л, Л) = 0)), - ( й,(і,о)). Если расстояние от А± до Аъ равно 1, А возвращается к Ai и останавливается. 9) Л4, (qt (Ру(Л4, Л, (gf,1)) = 1) Л (Аъ правее Л4) Л (Pi(Л, Л) = 1) Л (iV( ,Л) =0))-»((&(-V,0)). 10) Л, (Й,( (Л,Л,(д2,1)) = 1) Л (Л правее Л) Л (Рі(Л4,Л2) = і) л (Р (Д4, Л, (д , д")) = 1)) - ((д , д", д), (хд в расположение Л)), где g ,g"G{-l,l}. П) ЛА, (ql (Ру(Л4,Лг) = 0)) - ( tf, (-У, 0)). 12) Л4, (ді, (Ру(Л, Лі, (q1, q")) = 1)) - ((g , g", g), (ход в расположение Лі)), где g ,g" є {-1,1}. Все описанные перемещения возможны, посколько лабиринт L обладает свойством вместе с любыми двумя клетками с одинаковой т/-координатой содержать и все клетки, находящиеся между ними. Все описанные перемещения осущетсвляются по отрезку, соединяющему начальные расположения автоматов. Легко видеть, что если построенный коллектив стартовал из (а, -расстановки (0 а Ъ), то автомат А совершает а проходов от А\ к Л3 и обратно, после чего Кс останавливается в (а, 6)-расстановке. Т.к. на каждый проход тратится 2c-]b/V[ тактов, время функционирования коллектива равно 2а c-]b/V[. Лемма доказана. Коллектив (А\,..., Ат ) назовем правильным, если автомат А\ имеет внутренний алфавит Q = { — 1,1} х Q . Определим функцию sgnQ(x), принимающую значение 1 при х О, и значение — 1 — иначе. Пусть правильный коллектив К — (Лі,..., Ат) (т 8), расположен в лабиринте L так, что Л2, Аз и А\ находятся в клетках (#о + 2і, Уо), (XQ + а2,2/о) и (хо + 6,2/о), соответственно (аі,а2 Є Ъ, b Є N, max(\ai\, a,2) b), и автомат Лі находится в состоянии q — {sgno(ai),sgno(a2),q ). Если при этом все автоматы коллектива, кроме А2, Лз и Л4, расположены в клетке (хо,уо), будем говорить, что коллектив К находится в (ai,a2,6)-расстановке с центром (хо,уо). Если Л5, AQ, Л7 и Лв находятся в клетках (х0 + Ьъу0), (0:0,2/0 + h2), (х0 + hi,yo + /г2) и (ж0 + h1:y0 + h2) соответственно (/її, /і2 Є Z), и все автоматы коллектива, кроме Л2,..., As расположены в клетке (хо,7/о), будем говорить, что
Доказательство возможности поимки непериодических жертв в квадранте
Пусть (п,р) — код жертвы U = U(R,V), а —входной символ U, соответствующий тому, что U не видит ни одного из хищников, не видит левого ( нижнего ) борта, и видит нижний ( левый } борт на расстоянии ао от себя (ао = 1,...,R ). Пусть в некоторый такт TQ жертва U оказалась в клетке (xoi ао) ((ао, уо)) в состоянии до, при этом траектория U имеет тип 2. Пусть ті — минимальный такт, такой что т\ т$ и автомат U в такт ті видит левый ( нижний ) борт. Обозначим клетку, в которой окажется U в такт ті, как (Ь\,уі) ((#і,Ьі)), а состояние, в котором окажется U в такт ті, как q\. Обозначим входной символ U, соответствующий тому, что U не видит ни одного из хищников, не видит нижнего ( левого ) борта, и видит левый ( нижний ) борт на расстоянии Ъ\ от себя как Ь. Зафиксируем произвольное feeN, такое что к 2. Предположим, XQ 2R к(п + I)2 V (y0 2R-k(n + l)2-V). Будем говорить, что коллектив (Ai,...,Am) (m 13) расположен в сильной нижней ( левой ) (а)(п,р, д)-расстановке с центром (хо, 1) ((1, т/о)}, если коллектив (Лі,..., Ли,Ли, , Ащ ) расположен в нижней ( левой ) (а)(п,ру д)-расстановке с центром (XQ, 1) ((1, уо)), а автомат Ліз находится в клетке (хо,ао) ((оо,г/о))? ГДе ао и а соотносятся так, как указано в предыдущем абзаце. Лемма 4.23. Для любого к 2, к N существует коллектив автоматов K(R,V) = (Wi,..., W23), который, стартуя в Ь из сильной нижней { левой ) (а)(п,р, до)-расстановки с центром (XQ, 1) ((1, т/о)), через Т тактов останавливается в сильной левой ( нижней ) (b)(n,p,qi)-расстановке с центром (1,T/I) ((хі, 1)), где }y&h[-k — Тг(р) Т Доказательство. Построим коллектив K (R,V) = (W/,... , 3), который, стартуя из сильной нижней (а)(п,р, д0)-расстановки с центром (XQ, 1) функционирует так, как описанно в утверждении леммы, останавливаясь в сильной левой (Ь)(п,р, ді)-расстановке). Обозначим коллектив, построенный в лемме 4.22., как К\ = (А{,..., Л\і )
Коллектив К\, стартуя из нижней (а)(п,р, до)-расстановки, останавливается в нижней (а, Ь) (п,р, q, q , q", s , sf), si, -расстановке с тем же центром, где qf, q", 6, si, s, si, S2 — компоненты программы U, соответствующие паре (q,a). Т.к., по предположению леммы, U имеет траекторию типа 2, 8\ О И S2 0. Модифицируем К\, так, чтобы в случае, если коллектив стартует из сильной нижней ( левой ) (a)(n,p,q) расстановки, сначала автомат А ± шел вверх ( вправо ) к А\3, и забирал его с собой обратно к А\. Добавим к коллективу К\ автоматы Л 2 и 23- Используя леммы 4.15., 4.16. и 4.17., модифицируем коллектив К\ так, чтобы, в случае, если после остановки всех автоматов К\ автомат А{ оказался в состоянии вида (а, а , г±, i2, ql, 1), коллектив выполнял ел едущие действия. 1. Автоматы A\i, 12 із и 14 перемещаются в клетку (жо + &\ j 1) 2. Автоматы А$ и А\0 перемещаются в клетки (жо + s + si, 1) и (жо + Sj, 1 + S2), соответственно. Автоматы Ад и А\0 перемещаются в клетки (жо+ +Si -f- n(k — 1)V si, 1) и (жо + Si, 1 + n(k — 1)V 52), соответственно, если все эти клетки принадлежат L (при жо R k(n + I)2 V, все эти клетки принадлежат L/C). Если хотя бы одна из этих клеток не принадлежит Z/4, коллектив останавливается в канонической расстановке в клетке, где находился А{ (считаем, что последним остановился А\ в состоянии вида (a,af,ii,i2,q}0,l)) 3. Автоматы Л, А\, А\, А\, А$ и А\ перемещаются в клетки (жо+Si+n , 1), (ж0+а?+р, 1), {x0+s4+q", 1), (ar0+s? + s, 1), {x0+s0i+n(k-l)V-\Sl\, 1) и (жо + 5і+п(& — l)V-s2, 1), соответственно. Все остальные автоматы (т.е. Л}, А\, Л}5? » "4-2з) перемещаются в клетку (ж0 -f sj , 1). Считаем, что, по окончании функционирования, последним останавливается автомат А\ в (добавленном) состоянии вида (а, af,ii,i2,qjv 1).
Расстановку, в которой оказался этот коллектив назовем ниоюней (а) (п, р, g", S2, Si, S2)-paccmaH06KOU с центром (жо + S , 1). Аналогичная расстановка по вертикали называется левой (а)(п,р, q" , s2, Si, S2)-расстановкой с центром (1, 2/о+ 5?)- Максимально возможное время, которое функционирует этот коллектив, в зависимости от р, обозначим ti(p). Коллективы К1 и К2, построенные в лемме 4.14., будем обозначать как К1 = (Лі, - - -, Аъ) и К2 = (Ви , Вь), соответственно. Построим еще один коллектив: К2 = (Л2,..., Л23 ) Положим Л2 = ЛІ, г = 1,...,5, Л = 7 0- Поведение остальных автоматов коллектива К2 зададим схемой функционирования. Перечень автоматов и алфавитов. Начальными состояниями автомата А являются состояния вида (ai, a2, i\z i2,q[)i а финальными — состояния вида (аі,а2,іі,і2 1+6)- - лемме 4.14., А остановится у левого борта спустя т-п-к-s\-\-}R/V[ тактов после запуска коллектива, где т — максимальное натуральное число, удовдетворяющее Автоматы А Ад, А22 и А23 идут вдоль нижнего борта до угла, затем вдоль левого борта вверх, за каждые к тактов сдвигаясь на (к—1)V клеток. Встретившись с А% они останавливаются в той же клетке, что и он. 2) ЛЬ (gj, №(А?) = )),- (gj+1, (-V, 0)), где г = 8,9,22,23, j = 1,..., к — 1. 3) А, (#), - ( Й, (0.0)), где г = 8, 9, 22, 23. 4) ЛІ (gj, (Р?(А2) = 1)л № (А) = 0)), -+ (gj+1, максимально возможный ход влево), где і = 8,9,22, 23, j = 1,..., к — 1. 5) ЛІ (g5,(Prt(A?) = Ч Л ( (A,A, 4+i) = 0)), -, (gj+1,(0, V)), где і = 8, 9,22, 23, j = 1,..., &; — 1, g +i — финальное состояние автомата А\. 6) Л?, (gj, (Р (А?) = 1) Л (РИА: A, &+i) = Ц). - (Й+і ХД в Расположение A) J гДе = 8, 9, 22, 23, = 1,..., к — 1, gf&+i — финальное состояние автомата А