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

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

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

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

Определение[править | править исходный текст]

Конфигурация[править | править исходный текст]

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

Состояния[править | править исходный текст]

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

  1. базовое состояние U
  2. транзитные (или чувствительные) состояния
    1. S
    2. S0
    3. S00
    4. S01
    5. S000
    6. S1
    7. S10
    8. S11
  3. конфлюентные состояния
    1. C00
    2. C10
    3. C01
    4. C11
  4. обычное передающее состояние
    1. T00 вправо
    2. T01 вверх
    3. T02 влево
    4. T03 вниз
  5. специальное передающее состояние
    1. T10 вправо
    2. T11 вверх
    3. T12 влево
    4. T13 вниз

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

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

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

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

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

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

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

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

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

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

  • ячейка в базовом состоянии U, получив сигнал, переходит в состояние S (1)
  • ячейка в состоянии S, не получив сигнала, переходит в состояние S0 (10)
    • ячейка в состоянии S0, не получив сигнала, переходит в S00 (100)
      • ячейка S00, не получив сигнала, переходит в S000 (1000)
        • ячейка S000, не получив сигнала, переходит в T00 (10000)
        • ячейка S000, получив сигнал, переходит в T01 (10001)
      • ячейка S00, получив сигнал, переходит в T02 (1001)
    • ячейка S0, получив сигнал, переходит в S01 (101)
      • ячейка S01, не получив сигнала, переходит в T03 (1010)
      • ячейка S01, получив сигнал, переходит в T10 (1011)
  • ячейка S, получив сигнал, переходит в S1 (11)
    • ячейка S1, не получив сигнала, переходит в S10 (110)
      • ячейка S10, не получив сигнала, переходит в T11 (1100)
      • ячейка S10, получив сигнал, переходит в T12 (1101)
    • ячейка S1, получив сигнал, переходит в S11 (111)
      • ячейка S11, не получив сигнала, переходит в T13 (1110)
      • ячейка S11, получив сигнал, переходит в C00 (1111)

Разрушающие правила[править | править исходный текст]

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

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

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