Клеточный автомат фон Неймана — клеточный автомат, разработанный фон Нейманом при содействии Станислава Улама для исследования возможности создания самовоспроизводящихся машин.

Клеточный автомат Нобили — разновидность клеточного автомата фон Неймана, дополненного возможностью пересечения сигналов и хранения информации группами передающих клеток. Последняя функция требует три дополнительных состояния, в силу чего автомат Нобили имеет 32 состояния, а не 28. Ещё одной разновидностью является клеточный автомат Хаттона (Hutton), допускающий репликацию кольцевых структур (см. Langton’s loops).

Определение

Конфигурация

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

Состояния

Каждый конечный автомат в пространстве фон Неймана может принимать одно из 29 состояний:

1. базовое состояние U
2. транзитные (или чувствительные) состояния
   1. S
   2. S₀
   3. S₀₀
   4. S₀₁
   5. S₀₀₀
   6. S₁
   7. S₁₀
   8. S₁₁
3. конфлюентные состояния
   1. C₀₀
   2. C₁₀
   3. C₀₁
   4. C₁₁
4. обычное передающее состояние
   1. T₀₀ вправо
   2. T₀₁ вверх
   3. T₀₂ влево
   4. T₀₃ вниз
5. специальное передающее состояние
   1. T₁₀ вправо
   2. T₁₁ вверх
   3. T₁₂ влево
   4. T₁₃ вниз

Каждое из передающих состояний (8 состояний) также характеризуется возбужденностью/невозбужденностью (зеленые/синие стрелочки), что дает в итоге 16 передающих состояний. Возбужденное состояние переносит данные со скоростью 1 бит за такт. Конфлюентные состояния имеют задержку на один такт, и таким образом могут хранить 2 бита информации.

Правила перехода передающих состояний

Поток информации между ячейками определяется свойством направленности. Применяются следующие правила:

• Передающие состояния применяют оператор ИЛИ к входным сигналам, то есть ячейка в передающем состоянии (обычном или специальном) перейдет в возбужденное на такте t+1 если любой из входных сигналов является возбужденным на такте t
• Состояния передаются между передающими ячейками соответственно свойству направленности.
• Обычные и специальные передающие состояния являются «антагонистами»:
  • Если ячейка А на такте t в обычном возбужденном передающем состоянии указывает на ячейку В в любом специальном передающем состоянии, то на такте t+1 ячейка В перейдет в базовое состояние U. Особое передающее состояние будет «уничтожено».
  • Аналогичное событие произойдет, если ячейка в специальном передающем состоянии будет указывать на обычную передающую ячейку.

Правила перехода конфлюентных состояний

Следующие правила применяются к конфлюентным состояниям:

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

Правила перехода транзитных состояний

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

• ячейка в базовом состоянии U, получив сигнал, переходит в состояние S (1)
• ячейка в состоянии S, не получив сигнала, переходит в состояние S₀ (10)
  • ячейка в состоянии S₀, не получив сигнала, переходит в S₀₀ (100)
    • ячейка S₀₀, не получив сигнала, переходит в S₀₀₀ (1000)
      • ячейка S₀₀₀, не получив сигнала, переходит в T₀₀ (10000)
      • ячейка S₀₀₀, получив сигнал, переходит в T₀₁ (10001)
    • ячейка S₀₀, получив сигнал, переходит в T₀₂ (1001)
  • ячейка S₀, получив сигнал, переходит в S₀₁ (101)
    • ячейка S₀₁, не получив сигнала, переходит в T₀₃ (1010)
    • ячейка S₀₁, получив сигнал, переходит в T₁₀ (1011)
• ячейка S, получив сигнал, переходит в S₁ (11)
  • ячейка S₁, не получив сигнала, переходит в S₁₀ (110)
    • ячейка S₁₀, не получив сигнала, переходит в T₁₁ (1100)
    • ячейка S₁₀, получив сигнал, переходит в T₁₂ (1101)
  • ячейка S₁, получив сигнал, переходит в S₁₁ (111)
    • ячейка S₁₁, не получив сигнала, переходит в T₁₃ (1110)
    • ячейка S₁₁, получив сигнал, переходит в C₀₀ (1111)

Разрушающие правила

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

См. также

• Машина фон Неймана

Ссылки

• Дж. фон Нейман, Теория самовоспроизводящихся автоматов. М.: «Мир», 1971.