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

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

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

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

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

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

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

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

Игра «Жизнь» (ADD PICTURES)

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

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

Состояния

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

Правила

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

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

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

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

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

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

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

TODO: ADD PICTIRES

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

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

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

Долгожители

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

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

Осцилляторы

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

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

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

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

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

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

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

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

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

Ружья

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

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

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

Паровозы

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

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

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

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

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

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

Пожиратели

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

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

Отражатели

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

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

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

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

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

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

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

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

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

Райский сад

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Автомат Ооно–Кохомото (NOT STARTED)

TODO: WRITE THE ARTICLE Смотреть в статье.

Классификация Вольфрама и коды Вольфрама (EXPLAIN THE RULES)

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

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

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

1. Эволюция системы заканчивается переходом всех клеток поля в одинаковое состояние;
2. Существует много конечных состояний, но все они состоят из набора простых структур, которые остаются неизменными или повторяются через некоторое небольшое число шагов;
3. Поведение сложное, во многих отношениях выглядит хаотическим;
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]-арное число, преобразовать это число в десятичное. Полученное десятичное число является кодом Вольфрама.

Далее в статье будут приведены наиболее известные правила.

Wireworld

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

Клеточный автомат 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) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.

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

См.также

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