Модели клеточных автоматов

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

Базовые определения

Определение:

Клеточный автомат представляет собой двусторонне бесконечную ленту, каждая ячейка которой может находиться в некотором состоянии. Множество состояний $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$.

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

Определение:

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

Определение:

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

Определение:

Райский сад — конфигурация КА, которая не может появиться в результате «эволюции», потому что не имеет предшественников.

Теорема (сада Эдема):

Клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен. Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.

Доказательство:

[math]\triangleright[/math]

Данная теорема была выдвинута и доказана Эдвардом Муром.

[math]\triangleleft[/math]

Классификация клеточных автоматов

Классификация Вольфрама

Определение:

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

Классы, предложенные С. Вольфрамом:

1. Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние;
2. Существует много конечных состояний, но все они состоят из набора простых структур, которые остаются неизменными или повторяются через некоторое небольшое число шагов;
3. Поведение сложное, во многих отношениях выглядит хаотическим;
4. Смесь хаоса и порядка: порождаются локальные структуры, которые перемещаются и взаимодействуют друг с другом очень сложным образом.

Классификация Эпштейна

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

Классы, предложенные Д. Эпштейном:

1. Все объекты расширяются: в наборе правил есть правило B1 (клетка переходит в состояние 1, если она имеет ровно одного соседа в состоянии 1);
2. Нет расширяющихся объектов: в наборе правил нет правил B2 или B3 (клетка переходит в состояние 1, если она имеет ровно двух / трёх соседей в состоянии 1).
3. Уменьшение невозможно: в наборе правил есть правила S01234 или B23/S0 (клетка сохраняет состояние 1, если у неё есть от нуля до четырех соседей в состоянии 1/клетка переходит в состояние 1 при наличии у неё ровно двух или трёх соседей в состоянии 1 и сохраняет это состояние, если у неё нет соседей в состоянии 1).
4. Возможны и расширение и уменьшение объектов: все остальные случаи.

Однако, данная классификация так же не лишена недостатков, в частности не удовлетворяет поставленным перед ней же требованиям: целью данной классификации является выделение кандидатов в универсальные клеточные автоматы. Эпштейн утверждал, что универсальные клеточные автоматы могут принадлежать только к классу 4, однако, существует универсальный клеточный автомат, относящийся к классу 3 по данной классификации.

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

Одномерные клеточные автоматы

Коды Вольфрама

Определение:

Код Вольфрама — система именования клеточных автоматов (как правило, ЛКА), предложенная С. Вольфрамом в 1983 году. Код основан на наблюдении, что таблица, определяющая новое состояние каждой ячейки в автомате, как функция состояний в его окрестности, может интерпретироваться как число из [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]-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.

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

TODO: ADD PICTIRES

Правило 30

Определение:

Правило 30 — ЛКА с двумя состояниями (0 и 1).

Для Правила 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:

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

Правило 110

Определение:

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

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

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

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

Правило 184

Определение:

Правило 184 — ЛКА с двумя состояниями (0 и 1).

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

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

Клеточные автоматы на двумерной решетке

Игра «Жизнь»

Определение:

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

Дополнительную информацию по игре вы можете найти в статье "игра «Жизнь»".

Состояния

Каждая клетка поля может быть либо белого, либо черного цвета. Белые клетки называются «живыми», черные — «мертвыми».

Правила

На каждом шаге автомата ко всем клеткам применяются следующие правила:

• В черная клетка, имеющая ровно три белые соседние клетки, становится белой («зарождается жизнь»);
• Если у белой клетки есть две или три белые соседние клетки, то эта клетка сохраняет свой цвет;
• Если у белой клетки соседей белого цвета меньше двух или больше трёх, клетка становится черной («умирает от одиночества» или «от перенаселённости»).

Основные элементы

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

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

• Устойчивые фигуры — фигуры, которые остаются неизменными
• Долгожители — фигуры, которые долго меняются, прежде чем стабилизироваться;
• Осцилляторы — фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;
• Двигающиеся фигуры (космические корабли) — фигуры, у которых состояние повторяется, но с некоторым смещением;
• Ружья — фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;
• Паровозы — двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;
• Пожиратели — устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;
• Отражатели — устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;
• Размножители — конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;

Наиболее известные представители данных классов будут рассмотрены далее в статье.

TODO: ADD PICTIRES

Устойчивые фигуры

Устойчивые фигуры или «натюрморты», делятся на несколько классов:

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

Долгожители

Определение:

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

Осцилляторы

Определение:

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

Определение:

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

Двигающиеся фигуры

Определение:

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

Определение:

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

Ружья

Определение:

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

У ружья есть два периода: период создания космических кораблей и период повторения состояний ружья.

Паровозы

Определение:

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

Определение:

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

Паровозы условно делят на чистые и грязные:

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

Пожиратели

Определение:

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

Отражатели

Определение:

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

Определение:

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

Размножители

Определение:

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

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

• НДД — ружьё, вырабатывающее грабли;
• ДНД — паровоз, оставляющий ружья на своем пути;
• ДДН — грабли, оставляющие паровозы;
• ДДД — Грабли, оставляющие грабли, так что нет никаких неподвижных элементов.

Райский сад

Теорема применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию. «Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвые. Следовательно, в «Жизни» существуют сады Эдема.

Wireworld

Определение:

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

Состояния

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

Правила

На каждом шаге автомата ко всем клеткам применяются следующие правила:

1. Пустая клетка остается пустой.
2. Клетка, находящаяся в состоянии «голова электрона» переходит в состояние «хвост электрона».
3. Клетка, находящаяся в состоянии «хвост электрона» переходит в состояние «проводник».
4. Клетка, находящаяся в состоянии «проводник» переходит в состояние «голова электрона», в том случае, если среди соседних клеток ровно одна или две находятся в состоянии «голова электрона». Во всех остальных случаях «проводник» остается «проводником».
   

При применении данных правил используется окрестность Мура – считается, что с данной клеткой соседствуют все восемь ее непосредственных соседей.

Общие закономерности

Электрон передвигается со скоростью одна клетка за шаг. Если по проводу навстречу идут два электрона, при столкновении они исчезают. При достижении электроном разветвления проводов по каждому из направлений, кроме исходного, уходит по электрону. Если к разветвлению одновременно подходит [math]2[/math] и более электронов, все они исчезают. При толщине провода в [math]2[/math] клетки поведение электронов аналогично обычному, при большей толщине поведение становится хаотичным.

Основные элементы

Большие коллекции функциональных элементов имеются в пакетах Mirek's Cellebration и Zillions of Games, а также на сайте WireWorld. Кроме того, на сайте The Wireworld computer приводится пример построения в WireWorld компьютера с определенным набором инструкций и регистров, и реализация алгоритма перечисления простых чисел для этого компьютера.

Тактовый генератор

Данный элемент представляет собой «петлю» из клеток проводника, к которой подсоединен провод – выход генератора, и изначально содержит один электрон. С периодом, равным длине петли, этот электрон достигает точки соединения петли с выходом, и дальше разветвляется на два электрона, один из которых идет по выходу, второй – дальше по петле. Таким образом, этот элемент можно использовать для получения в проводе бесконечного количества электронов, следующих один за другим на расстоянии, регулируемом длиной петли.

• 

  Тактовый генератор

Диод

Этот функциональный элемент имеет две точки подсоединения к проводам – вход и выход, и его действие состоит в том, что электроны, пришедшие на вход, передаются на выход, а электроны, пришедшие на выход – исчезают. Таким образом, электроны могут перемещаться по проводу, в который включен диод, лишь в одном направлении.

• 

  Диод

Логические элементы OR, XOR и NAND

Каждый из этих элементов имеет по 2 входа и выход. Наличие электрона на входе соответствует логическому значению «единица», отсутствие – логическому значению «ноль». Электрон на выходе появляется согласно таблице истинности соответствующей логической операции.

• Так, для элемента OR электрон на любом из входов, или электроны на обоих входах одновременно дают электрон на выходе.
  
• Для элемента XOR электрон на любом из входов дает электрон на выходе, но при одновременной подаче электронов на оба входа они исчезают, и электрон на выходе не создается.
  
• Элемент NAND работает как тактовый генератор, и посылает электроны на выход во всех случаях, за исключением случая, когда на оба входа одновременно подаются электроны.
  

• 

  OR

• 

  XOR

• 

  NAND

Двоичный сумматор

Рассмотрим пример более сложной структуры, состоящей из множества простых элементов – двоичный сумматор. Его функция заключается в том, что при подаче на два входа закодированных особым образом чисел, через фиксированное количество шагов (в изображенном примере – 48) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.

• 

  Двоичный сумматор

Самовоспроизводящиеся клеточные автоматы (UNDER CONSTRUCTION)

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

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

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

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

Автомат фон Неймана

Определение:

Автомат фон Неймана (клеточная модель самовоспроизведения) — двумерный клеточный автомат, в каждой клетке поля которого находится конечный автомат с 29 состояниями, каждая клетка имеет 4 соседей, информация приходит с задержкой по крайней мере на 1 единицу времени.

Из 29 состояний одно является невозбудимым, 20 относятся к возбудимым, 8 – к чувствительным.
На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние, затем клеточная система начинает работать по правилам переходов.

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

Формальное описание

Данное описание взято из §5.3 книги "Физика процессов эволюции".
Как было сказано выше, автомат фон Неймана представляет клеточный автомат, у которого каждая клетка может находиться в 29 состояниях. Клеточный автомат состоит из многих однотипных автоматов, расположенных в узлах решетки; выход каждого автомата служит входом для соседних клеток.
Нумерует клетки радиус-вектор [math]\vartheta = (i, j), \; i,j = 0, \pm 1, \pm 2, \dots[/math].

Определение:

Назовем ближайшими соседями клетки те клетки, что лежат в ее окрестности фон Неймана; клетки, дополняющие окрестность фон Неймана до окрестность Мура, назовем ближними соседями.

TODO: ADD PICTURES
Определим восемь векторов расстояния:
[math]v^0 = (1, 0) \;\;\; v^1 = (0, 1) \;\;\; v^2 = (-1, 0) \;\;\; v^3 = (0, -1) \;\;\; v^4 = (1, 1) \;\;\; v^5 = (-1, 1) \;\;\; v^6 = (-1, -1) \;\;\; v^7 = (1, -1)[/math]
Тогда [math]\vartheta + v^\alpha,\; \alpha = 0, \dots , 3[/math] — ближайшие соседи, а [math]\vartheta + v^\alpha,\; \alpha = 7, \dots , 7[/math] — ближние.

Время дискретно, т.е. изменяется по тактам: [math]t = 0, \pm 1, \pm 2, \dots[/math], на каждом такте каждая клетка [math]\vartheta[/math] находится в одном из [math]n[/math] состояний [math]n = 0, \dots , N - 1[/math], т.е. состояние на такте [math]t[/math] есть [math]n_{t}^{\vartheta}[/math].

Состояния изменяются по правилу перехода [math]F[/math], одинаковому для всех клеток (внутренняя однородность):

[math]n_{t}^{\vartheta} = F(n_{t - 1}^\vartheta; n_{t - 1}^{\vartheta + v^\alpha} \; | \; \alpha = 0, \dots , 3)[/math]

В соотношении выше [math]F[/math] зависит от [math]5[/math] переменных, которые могут принимать [math]N[/math] значений, а поскольку [math]F[/math] также принимает [math]N[/math] различных значений при каждом значении аргумента, всего существует [math]m = N^{N^5}[/math] различных функций [math]F[/math] (различных моделей).

Автомат фон Неймана имеет [math]N = 29[/math] различных состояний:
1. Транзитивные состояния (импульсы) [math]T_{u\alpha\varepsilon}[/math], где:

[math] u = \begin{equation*} \begin{cases} 0 &\text{—$\;$ обычное состояние,}\\ 1 &\text{—$\;$ специальное состояние;}\\ \end{cases} \end{equation*} [/math]

[math] \alpha = \begin{equation*} \begin{cases} 0 &\text{—$\;$ вправо,}\\ 1 &\text{—$\;$ вверх,}\\ 2 &\text{—$\;$ влево,}\\ 3 &\text{—$\;$ вниз;}\\ \end{cases} \end{equation*} [/math]

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

2. Конфлюэнтные состояния [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]

3. Основное состояние [math]U[/math] (невозбужденное).
4. Чувствительные (сенситивные) состояния [math]S_{\Sigma}[/math], где:

[math]\Sigma = \Theta, 0, 1, 00, 01, 10, 11, 000[/math]

и

[math]S_{0000} = T_{000},[/math]

[math]S_{0001} = T_{010},[/math]

[math]S_{001} = T_{020},[/math]

[math]S_{010} = T_{030},[/math]

[math]S_{011} = T_{100},[/math]

[math]S_{100} = T_{110},[/math]

[math]S_{101} = T_{120},[/math]

[math]S_{110} = T_{130},[/math]

[math]S_{111} = C_{00},[/math]

Основное состояние $U$ может оставаться неизменным или, путем возбуждения, переходить в чувствительное состояние $S$. В последнем случае последнее автоматически пробегает определенную последовательность чувствительных состояний, которая неизбежно заканчивается конфлюэнтным состоянием $C$ или транзитивным состоянием $T$. Оба конечных состояния могут попеременно находиться в возбужденной и невозбужденной форме, оставаться неизменными или переходить снова в основное состояние.

Более подробно $F$ определяется следующими соотношениями:

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

Принцип работы

TODO: ADD PICS
На бесконечном поле задается исходный конечный набор клеток, имеющих не невозбудимое состояние. Затем клеточная система начинает работать по правилам переходов. Логическая структура бесконечного клеточного автомата такова, что через некоторый промежуток времени в некоторой области клеточного пространства, отличной от начального условия, появляется копия начального автомата. От дискретной клеточной модели самовоспроизведения фон Нейман собирался перейти к непрерывной модели, которая представляла бы систему дифференциальных уравнений в частных производных диффузионного типа.

Автомат Лэнгтона

Одним из направлений развития работы фон Неймана стали попытки конструирования более простых самовоспроизводящихся клеточных автоматов. Примером эволюции простого самовоспроизводящегося автомата — автомат Лэнгтона.

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

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

Определение:

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

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

Состояния автомата Лэнгтона:

• $0,\;1,\;2$ — служебные состояния;
• $3,\;4,\;5,\;6,\;7$ — сигнальные состояния.

Из клеток в состоянии $2$ строятся «стенки» автомата. Состояние $1$ является «несущей частотой», или, скорее, «несущей лентой» сигнала. Вслед за сигнальным состоянием должно идти состояние $0$ — так задается направление распространения сигнала. Состояние $3$ используется в качестве промежуточного состояния при повороте, состояния $5$ и $6$ используются при отделении дочернего автомата и для инициализации новой итерации самовоспроизведения.

Принцип работы

TODO: ADD PICTURES
Когда конца ленты достигает сигнал $70$, то длина ленты увеличивается на $1$. Когда в конец ленты приходят два сигнала $40$, то лента делает поворот налево. Копия исходного состояния получается через $151$ такт времени после запуска автомата.

Тюрьмиты

Определение:

Тьюрмит — это движущаяся по плоскости, размеченной клетками, машина Тьюринга, которая хранит свое внутреннее состояние, и, в зависимости от него и от цвета клетки, на которой она стоит, изменяет свое состояние, перекрашивает клетку в другой цвет и делает поворот влево или вправо.

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

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

TODO: ADD PICTURES
Тьюрмиты можно программировать для решения достаточно сложных задач: например, один тьюрмит может анализировать размеченную поверхность и оставлять на ней пометки для другого, который будет вносить в нее изменения. При помощи всего лишь одного тьюрмита можно реализовать клеточный автомат «Жизнь»: тьюрмит обегает колонию и в соответствии с заданными правилами рисует следующее поколение.

См.также

• Линейный клеточный автомат, эквивалентность МТ
• Машина Тьюринга
• Линейный ограниченный автомат
• Автомат фон Неймана
• Муравей Лэнгтона