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

Определение

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

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

Состояния

Каждый конечный автомат в пространстве фон Неймана может принимать одно из 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)

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

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

Модификации

Одной из разновидностей автомата фон Неймана является автомат Нобили , в котором введены дополнительные состояния для обеспечения памяти и возможности пересечения сигналов без интерференции, для чего использована возможность хранения информации группами клеток. Последняя функция требует три дополнительных состояния, в силу чего автомат Нобили имеет 32 состояния, а не 29. Является изобретением ( итал. Renato Nobili ), профессора физики университета Падуя , Италия . Фон Нейман намеренно исключил состояния, предназначенные для пересечения сигналов.

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

Ещё одной разновидностью является автомат Хаттона ( англ. Hutton ), допускающий репликацию кольцевых структур (см. на английском языке ).

См. также

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

Ссылки

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