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

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

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

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

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

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

TODO: EXPLAIN CONFIGURATIONS' NATURE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

TODO: FIX FORMATTING

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

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

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

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

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

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

Определим восемь векторов расстояния (TODO: ADD PICTURE):
[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]

Тюрьмиты

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

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

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

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

См.также

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