Модели клеточных автоматов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Fon Neuman Automat: formal decription in process)
м (Fon Neuman Automat: decription)
 
(не показано 15 промежуточных версий этого же участника)
Строка 345: Строка 345:
 
|id=neiman_auto
 
|id=neiman_auto
 
|definition=
 
|definition=
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref>Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.
+
'''Автомат фон Неймана''' (клеточная модель самовоспроизведения<ref name="neuman_automata">Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971</ref>) {{---}} объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.
 
}}
 
}}
  
 
=== Состояния ===
 
=== Состояния ===
Определим соседей клетки с помощью векторов:
+
Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:
 
* [[#neiman_neighborhood | Окрестность фон Неймана]]: <tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>;
 
* [[#neiman_neighborhood | Окрестность фон Неймана]]: <tex>v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1)</tex>;
 
* Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood | окрестности Мура]]: <tex>v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br><br>
 
* Клетки, дополняющие окрестность фон Неймана до [[#moore_neighborhood | окрестности Мура]]: <tex>v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)</tex><br><br>
 
Состояние клетки $\vartheta$ на $t$-ом шаге: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3), F</tex> {{---}} функция переходов.<br>
 
Состояние клетки $\vartheta$ на $t$-ом шаге: <tex>n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3), F</tex> {{---}} функция переходов.<br>
 
<br>
 
<br>
Состояния рассматриваемого автомата делятся на $4$ различных класса:<br>
+
Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:<br>
 
1. Основное состояние <tex>U</tex> (невозбужденное).<br>
 
1. Основное состояние <tex>U</tex> (невозбужденное).<br>
 
2. Транзитивные состояния <tex>T_{u\alpha\varepsilon}</tex>, где:
 
2. Транзитивные состояния <tex>T_{u\alpha\varepsilon}</tex>, где:
Строка 366: Строка 366:
 
\end{equation*}
 
\end{equation*}
 
</tex><br>
 
</tex><br>
::: <tex> \alpha = 0, \dots, 3 </tex> {{---}} (вправо, вверх, влево, вниз);
+
::: <tex> \alpha = 0, \dots, 3 </tex> {{---}} выходное направление (вправо, вверх, влево, вниз);
 
::: <tex>
 
::: <tex>
 
\varepsilon =  
 
\varepsilon =  
Строка 396: Строка 396:
 
</tex><br>
 
</tex><br>
 
4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$.
 
4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$.
 +
<br><br>
 +
Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит<ref name="neuman_automata"/> аналогию с системой нейронных связей, аналогичным образом строя автомат.<br><br>
 +
Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.<br><br>
 +
Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.<br><br>
 +
По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "вход".<br><br>
 +
Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов.
  
 
=== Правила переходов ===
 
=== Правила переходов ===
Строка 408: Строка 414:
 
# Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:
 
# Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:
 
## $U$, если среди ее соседей найдется  ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$  в состоянии $T_{1{\alpha}'1}$;
 
## $U$, если среди ее соседей найдется  ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$  в состоянии $T_{1{\alpha}'1}$;
## $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и все ее соседи, такие что ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ находятся в состоянии $T_{0{\alpha}'0}$ или $T_{0{\alpha}'1}$;
+
## $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$;
 
## $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.
 
## $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.
 
# Клетка в состоянии $U$ перейдет в состояние:
 
# Клетка в состоянии $U$ перейдет в состояние:
Строка 419: Строка 425:
 
=== Принцип работы ===
 
=== Принцип работы ===
 
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
 
Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана.
 +
Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"<ref name="neuman_automata"/>.
  
 
== Автомат Лэнгтона ==
 
== Автомат Лэнгтона ==

Текущая версия на 01:38, 27 июня 2020

Эта статья находится в разработке!

Содержание

Базовые определения[править]

Определение:
Клеточный автомат[1] представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии.

Множество состояний $Q$, обозначим состояние ячейки $i$ как $s[i]$.
Изначально все ячейки находятся в состоянии $B \in Q$, кроме ячеек с номерами от $1$ до $n$. Ячейка с номером $i$, где $1 \le i \le n$ находится в состоянии $x_i$, где $x$ - входное слово (будем считать, что $\Sigma \subset Q$, $B \notin \Sigma$).

Правила работы клеточного автомата такие: задано число $d$ и функция $f : Q^{2d+1} \to Q$. За один шаг все клетки меняют состояние по следующему правилу: новое состояние клетки $i$ равно $f(s[i - d], s[i - d + 1], \ldots, s[i + d - 1], s[i + d])$. Если клетка с номером $0$ переходит в состояние $Y$, то автомат допускает слово $x$.

Определение и основные свойства линейного клеточного автомата содержатся в статье "линейный клеточный автомат, эквивалентность МТ".


Определение:
Окрестность Мура[2] ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой.
Окрестность Мура порядка [math]r[/math] в двумерном случае представляет собой квадрат со стороной [math]2r + 1[/math][3].


Определение:
Окрестность фон Неймана[4] ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую сторону (грань) с данной ячейкой.


Классификация клеточных автоматов[править]

Классификация Вольфрама[править]

Определение:
Классы Вольфрама[5] — классификация клеточных автоматов, основанная на их поведении.


Классификация Эпштейна[править]

На ряд серьезных недостатков классификации С. Вольфрама указывал[7] Д. Эпштейн.
Один из них состоял в невозможности за разумное время проверить принадлежность клеточного автомата к какому-либо классу для большого числа клеточных автоматов.
В свою очередь он предложил систему классификации двухмерных двоичных клеточных автоматов, призванную выделять кандидатов в универсальные клеточные автоматы.

Однако, данная классификация так же имела серьезные проблемы, и, в конечном счете, не удовлетворяла своему назначению. Более подробные описания данных классификаций, а также других наиболее распространенных, можно найти в работе П.С. Скакова[6]. В ней, в том числе, были выделены основные достоинства и недостатки различных классификаций, и предложена новая, являющаяся уточнением и модификацией существующих и решающая многие их проблемы.

Одномерные клеточные автоматы[править]

Коды Вольфрама[править]

Определение:
Код Вольфрама — система именования клеточных автоматов (как правило, ЛКА), предложенная С. Вольфрамом в 1983 году[8].
Данная система основана на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из [math]k[/math]-цифр в [math]S[/math]-арной позиционной системе счисления, где [math]S[/math] — число состояний, которое может иметь каждая ячейка в автомате, [math]k = S^{2n + 1}[/math] — число конфигураций окрестности, а [math]n[/math] — радиус окрестности.

В соответствии с определением, код может быть вычислен следующим образом:

  1. Определить все возможные конфигурации окрестности данной ячейки;
  2. Интерпретируя каждую конфигурацию как число, как описано выше, отсортировать их по убыванию;
  3. Для каждой конфигурации определить состояние, которое будет иметь данная ячейка в соответствии с правилами переходов на следующей итерации;
  4. Интерпретируя полученный список состояний как [math]S[/math]-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.


Далее в статье будут приведены наиболее известные правила.
Во всех случаях рассматриваются ЛКА с двумя возможными состояниями. Каждая клетка изменяет своё состояние в зависимости от состояния ее ближайших соседей и ее состояния на предыдущем шаге.

Правило 30[править]

Определение:
Правило 30ЛКА с двумя состояниями (0 и 1).
Эволюция клеточного автомата по Правилу 30


Для Правила 30 в таблице даны правила перехода центральной клетки триады в следующее состояние:

Текущее состояние трёх соседних клеток 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 0 0 0 1 1 1 1 0

Так как [math]11110_2 = {30}_{10}[/math], данное правило называется Правилом 30.

Правило 90[править]

Определение:
Правило 90ЛКА с двумя состояниями (0 и 1).
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
Эволюция клеточного автомата по Правилу 90


Правила перехода для Правила 90:

Текущее состояние трёх соседних клеток 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 0 1 0 1 1 0 1 0

Так как [math]1011010_2 = {90}_{10}[/math], данное правило называется Правилом 90.

Правило 110[править]

Определение:
Правило 110ЛКА с двумя состояниями (0 и 1).
Шаг работы автомата состоит в одновременной замене значения в любой ячейке на сумму по модулю 2 её двух соседей.
Эволюция клеточного автомата по Правилу 110


Правила перехода для Правила 110:

Текущее состояние трёх соседних клеток 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 0 1 1 0 1 1 1 0

Так как [math]1101110_2 = {110}_{10}[/math], данное правило называется Правилом 110.








Правило 184[править]

Определение:
Правило 184ЛКА с двумя состояниями (0 и 1).
Эволюция клеточного автомата по Правилу 184


Правила перехода для Правила 184:

Текущее состояние трёх соседних клеток 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 1 0 1 1 1 0 0 0

Так как [math]110111000_2 = {184}_{10}[/math], данное правило называется Правилом 184.

Клеточные автоматы на двумерной решетке[править]

Игра «Жизнь»[править]

Некоторые из приведенных далее определений были взяты с этого[9] сайта, а также со смежных с нем страниц.

Определение:
«Жизнь» — клеточный автомат, представляющий из себя бесконечное клетчатое поле, каждая клетка может быть белой или черной. Состояние, в которое перейдет клетка на следующем шаге, зависит от состояний ее соседей в окрестности Мура.

Основную информацию по игре вы можете найти в статье "игра «Жизнь»". В данном разделе будут рассмотрены лишь основные типы и примеры конфигураций данной игры.

Состояния и правила переходов[править]

Название состояния Цвет Переходит в cостояние
«Живая клетка» Белый «мертвая клетка», если имеет ровно меньше двух или больше трех соседей в состоянии «живая клетка».
«Мертвая клетка» Черный «живая клетка», если имеет ровно трех соседей в состоянии «живая клетка».

Основные элементы[править]

В данном разделе используются термины из «Словаря Жизни»[10].

TODO: ADD PICTURES

Устойчивые фигуры[править]

Определение:
Устойчивый образец — объект, который является собственным родителем.


Определение:
Натюрморт[11] — устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть.


Определение:
Псевдонатюрморт — устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов.


Долгожители[править]

Определение:
Долгожитель — конфигурация из 10 или меньшего числа клеток, которым необходимо не менее 50 поколений для стабилизации[12].


Осцилляторы[править]

Определение:
Осциллятор — конфигурация клеточного автомата, которая после конечного числа поколений повторяется в изначальном виде и положении.


Определение:
Период осциллятора — минимальное число поколений, через которое осциллятор возвращается в исходное состояние.


Двигающиеся фигуры[править]

Определение:
Космический корабль — конфигурация, которая через определённое количество поколений вновь появляется без дополнений или потерь, но со смещением относительно исходного положения.


Определение:
Период космического корабля — минимальное число поколений, за которое космический корабль смещается.


Ружья[править]

Определение:
Ружье — класс конфигураций, у которых основная часть циклически повторяется, как у осцилляторов, а также периодически создаёт космические корабли, которые удаляются от ружья. Данная конфигурация имеет два периода: период создания космических кораблей и период повторения состояний ружья.


Паровозы[править]

Определение:
Паровоз — объект, который движется по полю подобно космическому кораблю, но при этом ещё и оставляет за собой след из других объектов.


Определение:
Грабли — паровозы, оставляющие за собой след исключительно из космических кораблей.


Пожиратели[править]

Определение:
Пожиратель — конфигурация, способная уничтожить космический корабль и восстановиться после контакта.


Отражатели[править]

Определение:
Отражатель — натюрморт или периодическая конфигурация, способная изменить направление движения другой фигуры определенного типа на 90° или 180°, восстанавливая свою структуру после отражения.


Определение:
Время восстановления отражателя — минимальное число поколений, которое должно проходить между столкновением с другими фигурами, чтобы отражатель успевал восстановиться.


Размножители[править]

Определение:
Размножитель — конфигурация, растущая квадратично, производя множество копий вторичной конфигурации, каждая из которых производит множество копий третичной конфигурации.


Существует несколько видов[13] размножителей, отличающихся между собой относительной подвижностью полученных конфигураций. Виды кодируются при сочетаниями трех букв, описывающие, соответственно, первичную, вторичную и третичную конфигурации: Д — движущаяся, Н — неподвижная:

  • НДД — ружьё, вырабатывающее грабли;
  • ДНД — паровоз, вырабатывающий ружья;
  • ДДН — грабли, вырабатывающий паровозы;
  • ДДД — грабли, вырабатывающий грабли.

Wireworld[править]

Определение:
Клеточный автомат Wireworld[14] представляет собой синхронный автомат с двумерной решеткой из квадратов, каждая клетка которой может находиться в одном из четырех состояний.

Состояния и правила переходов[править]

Название состояния Цвет Переходит в состояние
Пустая клетка Черный
Проводник Желтый «голова электрона», если имеет ровно одного или двух соседей в состоянии «голова электрона»
Голова электрона Красный «хвост электрона»
Хвост электрона Синий «проводник»

Общие закономерности[править]

Движение "электрона" в "цепи" происходит со следующими закономерностями:

  • При прохождении электроном разветвления "цепи", в каждое из новых направлений уходит по "электрону";
  • При одновременном столкновении двух и более "электронов", они исчезают.
  • При толщине "провода" больше $2$, "электроны" начинают двигаться хаотично.

Основные элементы[править]

В данной статье приведены лишь основные простейшие элементы, которые можно составить в Wireworld.
Большое количество примеров приведено в Mirek's Cellebration[15] и Zillions of Games[16], WireWorld[17]; с помощью элементов Wireworld также был построен[18] компьютер.

Тактовый генератор[править]

Данный элемент используется для получения электронов, так как при каждом прохождении разветвления электроном, движущимся по петле генератора, образуется новый электрон. Частота появления электронов регулируется длиной петли.

Диод[править]

Данный элемент действует точно так же, как одноименный элемент[19] электрической цепи.

Логические элементы OR, XOR и NAND[править]

Данный элемент действует точно так же, как и одноименные логические элементы[20][21][22].

Самовоспроизводящиеся клеточные автоматы[править]

В ходе работы над математическими и логическими проблемами самовоспроизведения, Дж. фон Нейман поставил пять основных вопросов, которые подробно описаны в книге "Физика процессов эволюции"[23]:
«

  1. Логическая универсальность.
    1. При каких условиях определенный класс автоматов логически универсален?
    2. Существует ли логически универсальный автомат?
  2. Конструируемость.
    1. Может ли один автомат быть построен другим автоматом?
    2. Какой класс автоматов может быть построен каким-то автоматом?
  3. Конструктивная универсальность.
    1. Существует ли конструктивно универсальный автомат? (т. е. автомат, способный построить любой автомат)
  4. Самовоспроизведение.
    1. Существует ли самовоспроизводящийся автомат?
    2. Существует ли автомат, который, помимо самовоспроизведения, может решать и другие задачи?
  5. Эволюция.
    1. Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
    2. Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату? (при надлежащем определении понятия эффективности)
».

В то время, как Тьюринг доказал, что машина Тьюринга является логически универсальной, Дж. фон Нейман построил автомат[24], удовлетворяющий всем пяти свойствам. Одна из таких моделей будет описана далее.

Автомат фон Неймана[править]

Определение:
Автомат фон Неймана (клеточная модель самовоспроизведения[25]) — объект, представляющий собой поле, в каждой клетке которого находится конечный автомат с 29 состояниями.


Состояния[править]

Определим соседей клетки с помощью векторов, установив в координат рассматриваемую клетку:

Состояние клетки $\vartheta$ на $t$-ом шаге: [math]n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3), F[/math] — функция переходов.

Состояния клеток рассматриваемого автомата делятся на $4$ различных класса:
1. Основное состояние [math]U[/math] (невозбужденное).
2. Транзитивные состояния [math]T_{u\alpha\varepsilon}[/math], где:

[math] u = \begin{equation*} \begin{cases} 0 &\text{—$\;$ обычное,}\\ 1 &\text{—$\;$ специальное;}\\ \end{cases} \end{equation*} [/math]
[math] \alpha = 0, \dots, 3 [/math] — выходное направление (вправо, вверх, влево, вниз);
[math] \varepsilon = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой,}\\ 1 &\text{—$\;$ возбуждение;}\\ \end{cases} \end{equation*} [/math]

3. Конфлюэнтные состояния [math]C_{\varepsilon{\varepsilon}'}[/math], где:

[math] \varepsilon = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой,}\\ 1 &\text{—$\;$ возбуждение;}\\ \end{cases} \end{equation*} [/math]
[math] {\varepsilon}' = \begin{equation*} \begin{cases} 0 &\text{—$\;$ покой на следующем такте,}\\ 1 &\text{—$\;$ возбуждение на следующем такте;}\\ \end{cases} \end{equation*} [/math]

4. Чувствительные состояния $S, \; S_0 \;, S_{00} \;, S_{01} \;, S_{000} \;, S_1 \;, S_{10} \;, S_{11}$.

Далее объясним природу вышеперечисленных состояний. Для достижения поставленных целей, Дж. фон Нейман проводит[25] аналогию с системой нейронных связей, аналогичным образом строя автомат.

Для передачи информации между клетками по цепочке из клеток же вводятся состояния $T$, причем наличие нейронного импульса регулируется параметром $\varepsilon$. Так как передача должна быть направленным процессом, вводится параметр $\alpha$, обозначающий, с какого направления клетка в данном состоянии будет принимать импульс.

Работу самих нейронов представляют состояния $С$: каждый нейрон имеет один "выход" и два "входа" (стороны клетки), которые для возбуждения необходимо раздражать одновременно, то есть у "нейрона" должно быть не менее двух соседей в окрестности фон Неймана в состоянии $T_1$, выходные направления которых ориентированы на "нейрон". Для экономии количества состояний вводится условность, что каждая сторона клетки может быть как "входом", так и "выходом" нейрона.

По аналогии с нейронными сетями, автомат должен иметь возможность "расщеплять" передаваемый сигнал, т.е. обеспечить возможность передачи его нескольким клеткам сразу. Данную функцию выполняют конфлюэнтные состояния, по определению имея несколько "выходов" и один "вход".

Состояния $S_{\Sigma0}$ и $S_{\Sigma1}$ используются для совершения прямого (возбуждение невозбужденных клеток) и обратного (приведение к покою возбужденных клеток) процессов.

Правила переходов[править]

Функция переходов $F$ определяется следующими соотношениями:

  1. Клетка в состоянии $T_{u\alpha\varepsilon}$ перейдет в состояние:
    1. $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u'{\alpha}'{\vartheta}'}$;
    2. $T_{u{\alpha}1}$, если пункт $1.1$ не выполнен, и среди ее соседей найдется клетка, удовлетворяющая одному из условий:
      1. ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'} \neq -v^\alpha$ в состоянии $T_{u{\alpha}'1}$;
      2. ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{\beta} \neq -v^\alpha, \; \beta = 0,\dots, 3$ в состоянии $C_1$;
    3. $T_{u{\alpha}0}$ во всех остальных случаях.
  2. Клетка в состоянии $C_{\varepsilon\varepsilon'}$ перейдет в состояние:
    1. $U$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{1{\alpha}'1}$;
    2. $C_{\varepsilon'1}$, если пункт $2.1$ не выполнен, и среди ее соседей найдется клетка ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{0{\alpha}'1}$, а все остальные такие клетки не будут находиться в состоянии $T_{0{\alpha}'0}$;
    3. $n_{\vartheta}^{t} = C_{\varepsilon'0}$, иначе.
  3. Клетка в состоянии $U$ перейдет в состояние:
    1. $S_0$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
    2. $U$ во всех остальных случаях.
  4. Клетка в состоянии $S_\Sigma, \; \Sigma=0,\dots,000$ перейдет в состояние:
    1. $S_{\Sigma1}$, если среди ее соседей найдется ${\vartheta}'\; : \; \vartheta - {\vartheta}' = v^{{\alpha}'}$ в состоянии $T_{u{\alpha}'1}$;
    2. $S_{\Sigma0}$, во всех остальных случаях.

Принцип работы[править]

Начальная конфигурация описывается конечным набором клеток, находящихся в возбудимом или чувствительном состоянии. Правила данного автомата устроены таким образом, что через некоторое количество шагов на поле появляется копия начальной конфигурации в области, отличающейся от той, в которой начальная конфигурация была задана. Более детальное описание механизма работы автомата можно найти в главе 2 книги "Теория самовоспроизводящихся автоматов"[25].

Автомат Лэнгтона[править]

Примером более простого самовоспроизводящегося клеточного автомата является автомат Лэнгтона[24].

Также интерес представляет Муравей Лэнгтона[26], разработанный в 1986 году Крисом Лэнгтоном и являющимся, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями[27].

Определение:
Автомат Лэнгтона — двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.

В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.

Сигнальная лента несет информацию, необходимую для создания копии автомата.


Состояния[править]

Сигнальные состояния[править]

Состояния $3-7$ относят к классу сигнальных:

  • $3$ используется при повороте;
  • $5$ и $6$ используются для самовоспроизведения.

Служебные состояния[править]

Состояния $0-2$ относят к классу служебных:

  • $0$, идущее вслед за сигнальным задает направление распространения сигнала;
  • $1$ является «несущей лентой» сигнала;
  • Из клеток в состоянии $2$ строятся «стенки» автомата.

Принцип работы[править]

  • Увеличение длины ленты на $1$ достигается путем передачи на ее конец сигнала $70$;
  • Поворот ленты влево достигается путем передачи на ее конец сигнала $40$;
  • Воспроизведение исходной конфигурации происходит через $151$ такт времени после запуска автомата.

Тьюрмиты[править]

Определение:
Тьюрмит[24] — это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.
Результат работы муравья Лэнгтона после 27731 итераций

Каждая строка программы записывается в следующем виде:

<текущее состояние> <цвет клетки под тьюрмитом> <новый цвет клетки> <смена направления> <новое состояние>


Игра «Жизнь» эмулируется[24] с помощью одного тьюрмита: он по очереди обходит все клетки поля и рисует новую конфигурацию в соответствии с правилами игры.
В области исследований модели ДНК при моделировании активно используются взаимодействующие и плиточные тьюрмиты[24] .

См.также[править]

Литература[править]

  1. Список заданий по ДМ 2к 2020 весна. URL: http://neerc.ifmo.ru/wiki/index.php?title=Список_заданий_по_ДМ_2к_2020_весна
  2. Окрестность Мура. URL: https://ru.wikipedia.org/wiki/Окрестность_Мура
  3. Weisstein, Eric W. Moore Neighborhood. URL: https://mathworld.wolfram.com/MooreNeighborhood.html
  4. Окрестность фон Неймана. URL: https://ru.wikipedia.org/wiki/Окрестность_фон_Неймана
  5. Wolfram, Stephen, A New Kind of Science. Wolfram Media, Inc., May 14, 2002. ISBN 1-57955-008-8
  6. 6,0 6,1 6,2 Скаков П.С. Классификация поведения одномерных клеточных автоматов. СПб., 2007 — URL: http://is.ifmo.ru/diploma-theses/_skakov_master.pdf
  7. Eppstein D. Classification of Cellular Automata. http://www.ics.uci.edu/~eppstein/ca/wolfram.html
  8. Wolfram, Stephen (July 1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55: 601–644
  9. Игра "Жизнь". URL: https://ru.wikipedia.org/wiki/Игра_«Жизнь»
  10. «Словарь Жизни». URL:http://beluch.ru/life/lifelex/lexr_o.htm
  11. Eric Weisstein. Still Life
  12. Gardner, M. (1983). "The Game of Life, Part III". Wheels, Life and Other Mathematical Amusements: 246
  13. Breeder – from Eric Weisstein's Treasure Trove of Life
  14. Трофимов Д., Наумов Л. Реализация клеточного автомата WireWorld с помощью инструментального средства CAME&L и его зональная оптимизация, 2007. URL: http://is.ifmo.ru/works/wireworld/
  15. "Mirek's Cellebration". URL:http://mirekw.com/ca/index.html
  16. "Zillions of Games". URL:http://zillionsofgames.com
  17. "WireWorld". URL:http://karl.kiwi.gen.nz/CA-Wireworld.html.
  18. "The Wireworld computer". URL:http://www.quinapalus.com/wi-index.html
  19. Диод. URL: https://ru.wikipedia.org/wiki/Диод
  20. Дизъюнкция. URL: https://ru.wikipedia.org/wiki/Дизъюнкция
  21. Исключающее «или». URL: https://ru.wikipedia.org/wiki/Исключающее_«или»
  22. NAND (логический элемент). URL: https://ru.wikipedia.org/wiki/Штрих_Шеффера
  23. Эбелинг Вернер, Энгель Андреас, Файстель Райнер. Физика процессов эволюции. Пер. с нем. Ю. А. Данилова. — М.: Эдиториал УРСС, 2001. - 328 с.
  24. 24,0 24,1 24,2 24,3 24,4 Г. Г. Малинецкий, Н. А. Митин, С. А. Науменко, “Нанобиология и синергетика. Проблемы и идеи (Часть 2)”, Препринты ИПМ им. М. В. Келдыша, 2005, 081. URL: http://spkurdyumov.ru/uploads/2013/09/miittin.pdf
  25. 25,0 25,1 25,2 Нейман Дж. фон. Теория самовоспроизводящихся автоматов. М.: Мир, 1971
  26. Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149
  27. Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.
  28. Лобанов А.И. Модели клеточных автоматов // Компьютерные исследования и моделирование, 2010, т. 2, № 3, с. 273-293. URL: http://vst.ics.org.ru/uploads/crmissues/kim_2010_2_3/crm10304.pdf