Автомат фон Неймана

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

Одна из простых конфигураций в клеточном автомате фон Неймана. Двоичный сигнал циркулирует вдоль петли из синих ячеек, используя переход между обычным и возбужденным состоянием передающих ячеек. Коммутирующая ячейка дублирует сигнал в красную линию, состоящую из ячеек особого передающего состояния. Сигнал проходит по линии и создает новую ячейку. Двоичный сигнал 1011 кодирует восточно-ориентированное передающее состояние, таким образом продолжая линию вправо. В процессе создания новая ячейка, управляемая бинарной последовательностью, проходит ряд сенсибилизированных состояний.

ОпределениеПравить

КонфигурацияПравить

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

СостоянияПравить

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

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

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

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

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

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

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

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

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

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

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

В исходном состоянии большая часть клеточного пространства является «пустой», то есть заполненной ячейками в состоянии 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)

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

Примерно 4000 битов данных конструируют сложный паттерн. Здесь используется разновидность КА фон Неймана с 32 состояниями, известная как Hutton32.

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

МодификацииПравить

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

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

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

См. такжеПравить

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

СсылкиПравить

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