Сотовая автоматизация фон Неймана

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

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

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

Определение

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

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

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

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

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

Штаты

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

основное состояние U (48, 48, 48)
переходные ) или сенсибилизированные состояния (в 8 подсостояниях
1. S (вновь сенсибилизированный) (255, 0, 0)
2. S ₀ – (сенсибилизированный, не получивший входных данных в течение одного цикла) (255, 125, 0)
3. S ₀₀ – (сенсибилизированный, не получивший входных данных в течение двух циклов) (255, 175, 50)
4. S ₀₀₀ – (сенсибилизированный, не получивший входных данных в течение трех циклов) (251, 255, 0)
5. S ₀₁ – (сенсибилизированный, не получивший ввод в течение одного цикла, а затем ввод в течение одного цикла) (255, 200, 75)
6. S ₁ – (сенсибилизированный, получивший ввод за один цикл) (255, 150, 25)
7. S ₁₀ – (сенсибилизированный, получивший ввод в течение одного цикла, а затем не входящий в течение одного цикла) (255, 255, 100)
8. S ₁₁ – (сенсибилизированный, получивший ввод в течение двух циклов) (255, 250, 125)
конфлюэнтные состояния (в 4 состояниях возбуждения)
1. C ₀₀ – стабилен (и также будет стабилен в следующем цикле) (0, 255, 128)
2. C ₀₁ – следующее возбуждение (сейчас неподвижно, но в следующем цикле будет возбуждено) (33, 215, 215)
3. C ₁₀ – возбужден (но в следующем цикле будет в покое) (255, 255, 128)
4. C ₁₁ – возбуждено-следующее возбуждено (возбуждено в настоящее время и будет возбуждено в следующем цикле) (255, 128, 64)
обычные состояния передачи (в 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)
специальные состояния передачи (в 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)

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

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

Правила штата передачи

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

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

Слитные государственные правила

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

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

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

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

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

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

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

клетка в основном состоянии U при получении входных данных перейдет в состояние S (вновь сенсибилизированное) в следующем цикле (1)
ячейка в состоянии S без ввода данных перейдет в состояние S ₀ (10)
- ячейка в состоянии S ₀ без ввода данных перейдет в состояние S ₀₀ (100)
  - ячейка в состоянии S ₀₀ без ввода данных перейдет в состояние S ₀₀₀ (1000)
    - ячейка в состоянии S ₀₀₀ , при отсутствии входных данных, перейдет в состояние обычной передачи, направленное на восток (10000)
    - ячейка в состоянии S ₀₀₀ при наличии входных данных перейдет в состояние обычной передачи, направленное на север (10001).
  - ячейка в состоянии S ₀₀ при наличии входных данных перейдет в состояние обычной передачи, направленное на запад (1001)
- ячейка в состоянии S ₀ при наличии входных данных перейдет в состояние S ₀₁ (101)
  - ячейка в состоянии S ₀₁ , при отсутствии входных данных, перейдет в состояние обычной передачи, направленное на юг (1010).
  - ячейка в состоянии S ₀₁ , получив входной сигнал, перейдет в направленное на восток состояние специальной передачи (1011)
ячейка в состоянии S при наличии входных данных перейдет в состояние S ₁ (11)
- ячейка в состоянии S1 _{, при отсутствии входных данных ,} перейдет в S10 _{состояние} (110)
  - ячейка в состоянии S ₁₀ , при отсутствии входных данных, перейдет в направленное на север состояние специальной передачи (1100)
  - ячейка в , _{состоянии S10} получив входной сигнал, перейдет в направленное на запад состояние специальной передачи (1101)
- ячейка в состоянии S1 ₁₁₁ при наличии входных данных перейдет в ( _{состояние S11} )
  - ячейка в состоянии S ₁₁ , при отсутствии входных данных, перейдет в направленное на юг состояние специальной передачи (1110)
  - ячейка в состоянии S ₁₁ , получив входной сигнал, перейдет в спокойное конфлюэнтное состояние C ₀₀ (1111)

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

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

Правила уничтожения

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

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

См. также

Ссылки

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

Внешние ссылки

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