Клеточный автомат фон Неймана

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

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

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

• 1 Определение
  • 1.1 Конфигурация
  • 1.2 Состояния
  • 1.3 Правила состояния передачи
  • 1.4 Правила состояния слияния
  • 1.5 Правила построения
  • 1.6 Правила разрушения
• 2 См. также
• 3 Ссылки
• 4 Внешние ссылки

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

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

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

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

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

Состояния

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

1. a заземление состояние 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, 21 5, 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. На восток (возбужденный и спокойный ent) (185, 56, 255) (235, 36, 36)

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

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

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

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

• Состояния передачи применяют оператор OR к входам, что означает, что ячейка в состоянии передачи (обычном или специальном) будет возбуждена в момент времени t + 1, если какой-либо из входов указывает на он возбуждается в момент времени t
• . Данные передаются из ячейки A в обычном состоянии передачи в соседнюю ячейку B в обычном состоянии передачи, в соответствии со свойством направления A (если B также не направлен на A, и в этом случае данные исчезают).
• Данные передаются из ячейки A в особом состоянии передачи в соседнюю соту B в особом состоянии передачи в соответствии с теми же правилами, что и для обычных состояний передачи.
• Два подмножества состояний передачи, обычное и специальное, являются взаимно антагонистическими:
  • Данная ячейка A в момент времени t в возбужденном состоянии обычной передачи
  • указывает на ячейку B в любом особом состоянии передачи
  • в момент t + 1 ячейка B w плохо станет основным государством. Ячейка специальной передачи была «уничтожена».
  • аналогичная последовательность будет иметь место в случае ячейки в специальном состоянии передачи, «указывающей» на ячейку в обычном состоянии передачи

Правила слияния состояний

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

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

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

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

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

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

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

• ячейка в основном состоянии U при заданном входе перейдет в Состояние S (новая сенсибилизация) в следующем цикле (1)
• ячейка в состоянии S при отсутствии ввода перейдет в состояние S0(10)
  • ячейка в состоянии S0при отсутствии ввода перейдет в состояние S00(100)
    • ячейка в состоянии S00, если нет вход, перейдет в состояние S000(1000)
      • ячейка в состоянии S000, при отсутствии ввода перейдет в состояние обычной передачи, направленное на восток (10000)
      • , ячейка в состоянии S000при наличии ввода перейдет в состояние обычной передачи в северном направлении (10001)
    • ячейка в состоянии S00при заданном входе перейдет в состояние обычной передачи в направлении на запад (1001)
  • ячейка в состоянии S0, учитывая ввод, перейдет в th e 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.

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

• клеточный автомат Кодда
• Петли Лэнгтона
• Универсальный конструктор фон Неймана
• Wireworld

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

• Голли - поддерживает CA фон Неймана вместе с Game of Life и другими наборами правил.