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

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

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

Окрестность Мура ячейки — совокупность ячеек в сетке (двумерном паркете, трёхмерном Евклидовом пространстве, разбитом на равновеликие кубы), имеющих общую вершину с данной ячейкой. Окрестность Мура порядка [math]r[/math] — множество клеток, расстояние Чебышёва до которых от данной клетки не превышает [math]r[/math]. Окрестность Мура порядка [math]r[/math] в двумерном случае представляет собой квадрат со стороной [math]2r + 1[/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) на выходе появится закодированное таким же образом число – сумма чисел на входах. Числа кодируются в двоичном виде, от младших битов к старшим, каждый бит кодируется наличием или отсутствием электрона на определенной позиции. На рисунке ниже эти позиции отмечены точками и изображениями чисел (значений каждого бита) из клеток в состоянии «проводник» по краям входов и выхода. Сами по себе эти отметки не несут никакой функциональной нагрузки, а служат лишь в пояснительных целях. Изображенный ниже сумматор имеет разрядность входов три бита, но можно получить сумматор с любой разрядностью, удлинив или укоротив провода на входах и выходе.

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

См.также

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