- Автомат фон Неймана
-
Клеточный автомат фон Неймана — клеточный автомат, разработанный фон Нейманом при содействии Станислава Улама для исследования возможности создания самовоспроизводящихся машин.
Клеточный автомат Нобили — разновидность клеточного автомата фон Неймана, дополненного возможностью пересечения сигналов и хранения информации группами передающих клеток. Последняя функция требует три дополнительных состояния, в силу чего автомат Нобили имеет 32 состояния, а не 28. Ещё одной разновидностью является клеточный автомат Хаттона (Hutton), допускающий репликацию кольцевых структур (см. Langton’s loops).
Содержание
Определение
Конфигурация
Клеточный автомат в общем виде представляет собой упорядоченное множество конечных автоматов, обменивающихся информацией с соседними автоматами. В клеточном автомате фон Неймана ячейки упорядочены в виде двухмерной прямоугольной решетки, и взаимодействуют с четырьмя непосредственно прилегающими ячейками. Решетка считается имеющей бесконечный размер в обоих направлениях, а ячейки — идентичными в плане правил перехода. Изменение состояний всех ячеек происходит синхронно.
Состояния
Каждый конечный автомат в пространстве фон Неймана может принимать одно из 29 состояний:
- базовое состояние U
- транзитные (или чувствительные) состояния
- S
- S0
- S00
- S01
- S000
- S1
- S10
- S11
- конфлюентные состояния
- C00
- C10
- C01
- C11
- обычное передающее состояние
- T00 вправо
- T01 вверх
- T02 влево
- T03 вниз
- специальное передающее состояние
- T10 вправо
- T11 вверх
- T12 влево
- T13 вниз
Каждое из передающих состояний (8 состояний) также характеризуется возбужденностью/невозбужденностью (зеленые/синие стрелочки), что дает в итоге 16 передающих состояний. Возбужденное состояние переносит данные со скоростью 1 бит за такт. Конфлюентные состояния имеют задержку на один такт, и таким образом могут хранить 2 бита информации.
Правила перехода передающих состояний
Поток информации между ячейками определяется свойством направленности. Применяются следующие правила:
- Передающие состояния применяют оператор ИЛИ к входным сигналам, то есть ячейка в передающем состоянии (обычном или специальном) перейдет в возбужденное на такте t+1 если любой из входных сигналов является возбужденным на такте t
- Состояния передаются между передающими ячейками соответственно свойству направленности.
- Обычные и специальные передающие состояния являются «антагонистами»:
- Если ячейка А на такте t в обычном возбужденном передающем состоянии указывает на ячейку В в любом специальном передающем состоянии, то на такте t+1 ячейка В перейдет в базовое состояние U. Особое передающее состояние будет «уничтожено».
- Аналогичное событие произойдет, если ячейка в специальном передающем состоянии будет указывать на обычную передающую ячейку.
Правила перехода конфлюентных состояний
Следующие правила применяются к конфлюентным состояниям:
- Конфлюентные ячейки не передают данных между собой.
- Конфлюентные ячейки принимают входные сигналы от одной или нескольких обычных передающих ячеек и выдают их передающим ячейкам (обычным или специальным), которые не указывают на текущую ячейку.
- Данные не передаются в направлении, обратном направленности передающей ячейки.
- Данные, хранимые конфлюентной ячейкой, теряются, если у неё нет прилегающих передающих ячеек (не указывающих на неё).
- Конфлюентные ячейки служат мостами между обычными и специальными передающими ячейками.
- Конфлюентные ячейки применяют оператор И к входным сигналам.
- Конфлюентные ячейки задерживают сигнал на один такт дольше, чем обычные передающие ячейки.
Правила перехода транзитных состояний
В исходном состоянии большая часть клеточного пространства является «пустой», то есть заполненной ячейками в состоянии U. Получив входной сигнал от передающей ячейки, соседняя ячейка в состоянии U переходит в транзитное состояние, проходит ряд состояний и оказывается в одном из передающих или конфлюентных состояний. Это конечное состояние определяется последовательностью входных сигналов. То есть транзитные состояния могут рассматриваться как точки бифуркации на пути от базового состояния к передающим и конфлюентным. В следующих правилах последовательность входных сигналов указана в скобках двоичной строкой:
- ячейка в базовом состоянии U, получив сигнал, переходит в состояние S (1)
- ячейка в состоянии S, не получив сигнала, переходит в состояние S0 (10)
- ячейка в состоянии S0, не получив сигнала, переходит в S00 (100)
- ячейка S00, не получив сигнала, переходит в S000 (1000)
- ячейка S000, не получив сигнала, переходит в T00 (10000)
- ячейка S000, получив сигнал, переходит в T01 (10001)
- ячейка S00, получив сигнал, переходит в T02 (1001)
- ячейка S00, не получив сигнала, переходит в S000 (1000)
- ячейка S0, получив сигнал, переходит в S01 (101)
- ячейка S01, не получив сигнала, переходит в T03 (1010)
- ячейка S01, получив сигнал, переходит в T10 (1011)
- ячейка в состоянии S0, не получив сигнала, переходит в S00 (100)
- ячейка S, получив сигнал, переходит в S1 (11)
- ячейка S1, не получив сигнала, переходит в S10 (110)
- ячейка S10, не получив сигнала, переходит в T11 (1100)
- ячейка S10, получив сигнал, переходит в T12 (1101)
- ячейка S1, получив сигнал, переходит в S11 (111)
- ячейка S11, не получив сигнала, переходит в T13 (1110)
- ячейка S11, получив сигнал, переходит в C00 (1111)
- ячейка S1, не получив сигнала, переходит в S10 (110)
Разрушающие правила
- Входной сигнал от специальной передающей ячейки, полученный ячейкой в конфлюентном или обычном передающем состоянии, переводит эту ячейку в базовое.
- Входной сигнал от обычной передающей ячейки, полученный специальной передающей ячейкой, переводит эту ячейку в базовое.
См. также
Ссылки
- Дж. фон Нейман, Теория самовоспроизводящихся автоматов. М.: «Мир», 1971.
Категория:- Клеточные автоматы
Wikimedia Foundation. 2010.