Клеточный автомат фон Неймана - Von Neumann cellular automaton

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

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

Клеточный автомат Нобили представляет собой разновидность клеточного автомата фон Неймана, дополненную способностью сливающихся клеток пересекать сигналы и хранить информацию. Первое требует дополнительных трех состояний, поэтому клеточный автомат Нобили имеет 32 состояния, а не 29. Клеточный автомат Хаттона - это еще одна разновидность, которая допускает цикл данных, аналогичный Петли Лэнгтона, чтобы воспроизвести.

Определение

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

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

Набор FSA определяет клеточное пространство бесконечного размера. Все FSA идентичны с точки зрения функции перехода между состояниями или набора правил.

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

Все ячейки совершают свои переходы синхронно, в соответствии с универсальными «часами», как в синхронной цифровой схеме.

состояния

Каждый FSA пространства ячеек фон Неймана может принимать любое из 29 состояний набора правил. Набор правил сгруппирован в пять ортогональных подмножеств. Каждое состояние включает в себя цвет клетки в программе клеточного автомата. Господи в (красный, зеленый, синий). Они есть

  1. а земля государственный U   (48, 48, 48)
  2. то переход или же сенсибилизированный состояния (в 8 подсостояниях)
    1. S (недавно повышенная чувствительность)   (255, 0, 0)
    2. S0 - (сенсибилизировано, не получая ввода в течение одного цикла)   (255, 125, 0)
    3. S00 - (сенсибилизировано, не получая ввода в течение двух циклов)   (255, 175, 50)
    4. S000 - (сенсибилизировано, не получая ввода в течение трех циклов)   (251, 255, 0)
    5. S01 - (сенсибилизировано, не получая ввода для одного цикла, а затем ввода для одного цикла)   (255, 200, 75)
    6. S1 - (сенсибилизированный, получив ввод за один цикл)   (255, 150, 25)
    7. S10 - (сенсибилизированный, получив ввод для одного цикла, а затем нет ввода для одного цикла)   (255, 255, 100)
    8. S11 - (сенсибилизированный, получив ввод за два цикла)   (255, 250, 125)
  3. то сливаться состояния (в 4-х состояниях возбуждения)
    1. C00 - в состоянии покоя (также будет в состоянии покоя в следующем цикле)   (0, 255, 128)
    2. C01 - следующий возбужденный (сейчас неподвижен, но будет возбужден в следующем цикле)   (33, 215, 215)
    3. C10 - возбужден (но в следующем цикле будет неподвижен)   (255, 255, 128)
    4. C11 - возбужден следующий-возбужден (возбужден сейчас и будет возбужден в следующем цикле)   (255, 128, 64)
  4. то обычная передача состояния (в 4 направлениях, возбужденное или покоящееся, составляющее 8 состояний)
    1. Направлен на север (возбужден и неподвижен)   (36, 200, 36)   (106, 106, 255)
    2. Направлен на юг (возбужден и неподвижен)   (106, 255, 106)   (139, 139, 255)
    3. На запад (возбужден и неподвижен)   (73, 255, 73)   (122, 122, 255)
    4. Направлен на восток (возбужден и неподвижен)   (27, 176, 27)   (89, 89, 255)
  5. то специальная трансмиссия состояния (в 4 направлениях, возбужденное или покоящееся, составляющее 8 состояний)
    1. Направлен на север (возбужден и неподвижен)   (191, 73, 255)   (255, 56, 56)
    2. Направлен на юг (возбужден и неподвижен)   (203, 106, 255)   (255, 89, 89)
    3. Направлен на запад (возбужденный и спокойный)   (197, 89, 255)   (255, 73, 73)
    4. Направлен на восток (возбужден и неподвижен)   (185, 56, 255)   (235, 36, 36)

«Возбужденные» состояния переносят данные со скоростью один бит на шаг перехода между состояниями.

Обратите внимание, что конфлюэнтные состояния имеют свойство задержки на один цикл, таким образом эффективно удерживая два бита данных в любой момент времени.

Правила состояния передачи

На поток битов между ячейками указывает свойство direction. Применяются следующие правила:

  • Состояния передачи применяют к входам оператор ИЛИ, что означает, что ячейка в состоянии передачи (обычном или специальном) будет возбуждена во время т + 1 если любой входов, указывающих на него, возбуждается во время т
  • Данные передаются из ячейки А в обычном состоянии передачи в соседнюю соту B в обычном состоянии передачи, в соответствии со свойством направления А (пока не B также направлен на А, и в этом случае данные исчезнут).
  • Данные передаются из ячейки А в особом состоянии передачи в соседнюю ячейку B в особом состоянии передачи по тем же правилам, что и для обычных состояний передачи.
  • Два подмножества состояний передачи, обычное и особое, являются антагонистическими:
    • Учитывая ячейку А вовремя т в возбужденном обычном состоянии передачи
    • указывая на ячейку B в любом особом состоянии трансмиссии
    • вовремя т + 1 клетка B станет основным состоянием. Специальная трансмиссионная ячейка была «разрушена».
    • аналогичная последовательность будет иметь место в случае, если ячейка в специальном состоянии передачи «указывает» на ячейку в обычном состоянии передачи.

Правила конфлюэнтного государства

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

  • Конфлюэнтные состояния не передают данные между собой.
  • Конфлюэнтные состояния принимают входные данные из одного или нескольких обычных состояний передачи и доставляют выходные данные в состояния передачи, обычные и особые, которые не направлены на конфлюэнтное состояние.
  • Данные не передаются против свойства направления состояния передачи.
  • Данные, содержащиеся в конфлюэнтном состоянии, теряются, если это состояние не имеет смежного состояния передачи, которое также не указывает на конфлюэнтное состояние.
  • Таким образом, ячейки сливающегося состояния используются как «мосты» от линий передачи ячеек с обычным состоянием передачи к ячейкам со специальным состоянием передачи.
  • В конфлюэнтном состоянии оператор AND применяется к входам, только «экономя» возбужденный вход, если все потенциальные входы возбуждаются одновременно.
  • Сливающиеся ячейки задерживают сигналы на одно поколение больше, чем ячейки OTS; это необходимо из-за паритет ограничения.

Правила строительства

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

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

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

В следующем дереве последовательность входных данных показана в виде двоичной строки после каждого шага:

  • ячейка в основном состоянии U, учитывая ввод, перейдет к S (вновь сенсибилизированное) состояние в следующем цикле (1)
  • ячейка в S состояние без ввода перейдет в S0 состояние (10)
    • ячейка в S0 состояние без ввода перейдет в S00 состояние (100)
      • ячейка в S00 состояние без ввода перейдет в S000 состояние (1000)
        • ячейка в S000 состояние без ввода перейдет в состояние обычной передачи, направленное на восток (10000)
        • ячейка в S000 состояние при заданном входе перейдет в состояние обычной передачи, направленное на север (10001)
      • ячейка в S00 состояние, заданное входом, перейдет в состояние обычной передачи, направленной на запад (1001)
    • ячейка в S0 состояние при вводе перейдет в S01 состояние (101)
      • ячейка в S01 состояние без ввода перейдет в состояние обычной передачи, направленной на юг (1010)
      • ячейка в S01 состояние при заданном входе перейдет в состояние специальной передачи, направленной на восток (1011)
  • ячейка в S состояние при вводе перейдет в S1 состояние (11)
    • ячейка в S1 состояние без ввода перейдет в S10 состояние (110)
      • ячейка в S10 состояние без ввода перейдет в состояние специальной передачи, направленное на север (1100)
      • ячейка в S10 состояние при заданном входе перейдет в состояние специальной передачи, направленной на запад (1101)
    • ячейка в S1 состояние при вводе перейдет в S11 состояние (111)
      • ячейка в S11 состояние без ввода перейдет в состояние специальной передачи, направленной на юг (1110)
      • ячейка в S11 состояние, заданное входом, перейдет в спокойное конфлюэнтное состояние C00 (1111)

Обратите внимание, что:

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

Правила разрушения

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

Смотрите также

Рекомендации

  • Фон Нейман, Дж. И А. В. Беркс (1966). Теория самовоспроизводящихся автоматов. Урбана, Университет Иллинойс Press. [1]

внешняя ссылка