Сотовая автоматизация фон Неймана
Клеточные автоматы фон Неймана являются оригинальным выражением клеточных автоматов , развитие которых было вызвано предложениями, сделанными Джону фон Нейману его близким другом и коллегой-математиком Станиславом Уламом . Их первоначальной целью было дать представление о логических требованиях к самовоспроизведению машин фон Неймана , и они были использованы в универсальном конструкторе .
Клеточный автомат Нобили представляет собой разновидность клеточного автомата фон Неймана, дополненную способностью сливающихся клеток пересекать сигналы и хранить информацию. Первый требует дополнительных трех состояний, следовательно, клеточный автомат Нобили имеет 32 состояния, а не 29. Клеточный автомат Хаттона - это еще один вариант, который позволяет цикл данных, аналогичный циклам Лэнгтона воспроизводить .
Определение
[ редактировать ]Конфигурация
[ редактировать ]В общем, клеточные автоматы (КА) представляют собой совокупность автоматов с конечным состоянием (FSA), которые находятся в позиционных отношениях друг с другом, причем каждый FSA обменивается информацией с теми другими FSA, к которым он позиционно примыкает. В клеточном автомате фон Неймана конечные автоматы (или ячейки ) расположены в двумерной декартовой сетке и взаимодействуют с окружающими четырьмя ячейками. Поскольку клеточный автомат фон Неймана был первым примером использования этой схемы, он известен как окрестность фон Неймана .
Набор FSA определяет пространство ячеек бесконечного размера. Все FSA идентичны с точки зрения функции перехода состояний или набора правил.
Окрестность . (функция группировки) является частью функции перехода состояний и определяет для любой ячейки набор других ячеек, от которых зависит состояние этой ячейки
Все ячейки совершают свои переходы синхронно, в такт универсальным «часам», как в синхронной цифровой схеме.
Штаты
[ редактировать ]Каждый FSA клеточного пространства фон Неймана может принимать любое из 29 состояний набора правил. Набор правил сгруппирован в пять ортогональных подмножеств. Каждое состояние включает цвет ячейки в программе клеточных автоматов Golly in (красный, зеленый, синий). Они есть
- основное состояние U (48, 48, 48)
- переходные ) или сенсибилизированные состояния (в 8 подсостояниях
- S (вновь сенсибилизированный) (255, 0, 0)
- S 0 – (сенсибилизированный, не получивший входных данных в течение одного цикла) (255, 125, 0)
- S 00 – (сенсибилизированный, не получивший входных данных в течение двух циклов) (255, 175, 50)
- S 000 – (сенсибилизированный, не получивший входных данных в течение трех циклов) (251, 255, 0)
- S 01 – (сенсибилизированный, не получивший ввод в течение одного цикла, а затем ввод в течение одного цикла) (255, 200, 75)
- S 1 – (сенсибилизированный, получивший ввод за один цикл) (255, 150, 25)
- S 10 – (сенсибилизированный, получивший ввод в течение одного цикла, а затем не входящий в течение одного цикла) (255, 255, 100)
- S 11 – (сенсибилизированный, получивший ввод в течение двух циклов) (255, 250, 125)
- конфлюэнтные состояния (в 4 состояниях возбуждения)
- C 00 – стабилен (и также будет стабилен в следующем цикле) (0, 255, 128)
- C 01 – следующее возбуждение (сейчас неподвижно, но в следующем цикле будет возбуждено) (33, 215, 215)
- C 10 – возбужден (но в следующем цикле будет в покое) (255, 255, 128)
- C 11 – возбуждено-следующее возбуждено (возбуждено в настоящее время и будет возбуждено в следующем цикле) (255, 128, 64)
- обычные состояния передачи (в 4 направлениях, возбуждение или состояние покоя, всего 8 состояний)
- Направлен на север (возбужден и покоен). (36, 200, 36) (106, 106, 255)
- Направлен на юг (возбужден и покоен). (106, 255, 106) (139, 139, 255)
- Направленный на Запад (возбужденный и спокойный) (73, 255, 73) (122, 122, 255)
- Направлен на восток (возбужден и покоен). (27, 176, 27) (89, 89, 255)
- специальные состояния передачи (в 4 направлениях, возбуждение или состояние покоя, всего 8 состояний)
- Направлен на север (возбужден и покоен). (191, 73, 255) (255, 56, 56)
- Направлен на юг (возбужден и покоен). (203, 106, 255) (255, 89, 89)
- Направленный на Запад (возбужденный и спокойный) (197, 89, 255) (255, 73, 73)
- Направлен на восток (возбужден и покоен). (185, 56, 255) (235, 36, 36)
«Возбужденные» состояния переносят данные со скоростью один бит на шаг перехода между состояниями.
Обратите внимание, что слитные состояния имеют свойство задержки в один цикл, таким образом эффективно удерживая два бита данных в любой момент времени.
Правила штата передачи
[ редактировать ]Поток битов между ячейками определяется свойством направления. Применяются следующие правила:
- В состояниях передачи к входам применяется оператор ИЛИ, что означает, что ячейка в состоянии передачи (обычная или специальная) будет возбуждена в момент времени t+1, если какой-либо из входов, указывающих на нее, будет возбужден в момент времени t.
- Данные передаются из ячейки A в обычном состоянии передачи в соседнюю ячейку B в обычном состоянии передачи в соответствии со свойством направления A (если только B не направлена также в сторону A , в этом случае данные исчезают).
- Данные передаются из ячейки A в специальном состоянии передачи в соседнюю ячейку B в специальном состоянии передачи по тем же правилам, что и для обычных состояний передачи.
- Два подмножества состояний передачи, обычные и особые, взаимно антагонистичны:
- Дана ячейка A в момент времени t в возбужденном обычном состоянии передачи.
- указывающий на ячейку B в любом особом состоянии передачи
- в момент времени t+1 ячейка B станет основным состоянием. Специальная ячейка передачи была «уничтожена».
- аналогичная последовательность будет происходить в случае, когда ячейка в специальном состоянии передачи «указывает» на ячейку в обычном состоянии передачи
Слитные государственные правила
[ редактировать ]К сливающимся состояниям применяются следующие особые правила:
- Сливные состояния не передают данные друг другу.
- Слитные состояния принимают входные данные от одного или нескольких обычных состояний передачи и доставляют выходные данные в состояния передачи, обычные и специальные, которые не направлены к слитному состоянию.
- Данные не передаются в соответствии со свойством направления состояния передачи.
- Данные, хранящиеся в слитном состоянии, теряются, если у этого состояния нет соседнего состояния передачи, которое также не указывает на слитное состояние.
- Таким образом, ячейки с конфлюэнтным состоянием используются в качестве «мостов» от линий передачи ячеек с обычным состоянием передачи к клеткам со специальным состоянием передачи.
- Слитное состояние применяет оператор И к входам, «сохраняя» возбужденный вход только в том случае, если все потенциальные входы возбуждаются одновременно.
- Слитные клетки задерживают сигналы на одно поколение больше, чем клетки OTS; это необходимо из-за ограничений четности .
Правила строительства
[ редактировать ]Первоначально большая часть клеточного пространства, вселенной клеточного автомата, является «пустой» и состоит из ячеек в основном состоянии U . При получении входного возбуждения из соседнего обычного или специального состояния передачи ячейка в основном состоянии становится «сенсибилизированной», переходя через серию состояний, прежде чем, наконец, «отдыхать» в состоянии покоя или сливающегося состояния.
Выбор состояния назначения, которого достигнет ячейка, определяется последовательностью входных сигналов. Следовательно, переходные/сенсибилизированные состояния можно рассматривать как узлы бифуркационного дерева , ведущего от основного состояния к каждому из состояний спокойной передачи и сливающегося состояния.
В следующем дереве последовательность входных данных показана в виде двоичной строки после каждого шага:
- клетка в основном состоянии U при получении входных данных перейдет в состояние S (вновь сенсибилизированное) в следующем цикле (1)
- ячейка в состоянии S без ввода данных перейдет в состояние S 0 (10)
- ячейка в состоянии S 0 без ввода данных перейдет в состояние S 00 (100)
- ячейка в состоянии S 00 без ввода данных перейдет в состояние S 000 (1000)
- ячейка в состоянии S 000 , при отсутствии входных данных, перейдет в состояние обычной передачи, направленное на восток (10000)
- ячейка в состоянии S 000 при наличии входных данных перейдет в состояние обычной передачи, направленное на север (10001).
- ячейка в состоянии S 00 при наличии входных данных перейдет в состояние обычной передачи, направленное на запад (1001)
- ячейка в состоянии S 00 без ввода данных перейдет в состояние S 000 (1000)
- ячейка в состоянии S 0 при наличии входных данных перейдет в состояние S 01 (101)
- ячейка в состоянии S 01 , при отсутствии входных данных, перейдет в состояние обычной передачи, направленное на юг (1010).
- ячейка в состоянии S 01 , получив входной сигнал, перейдет в направленное на восток состояние специальной передачи (1011)
- ячейка в состоянии S 0 без ввода данных перейдет в состояние S 00 (100)
- ячейка в состоянии S при наличии входных данных перейдет в состояние S 1 (11)
- ячейка в состоянии S1 , при отсутствии входных данных , перейдет в S10 состояние (110)
- ячейка в состоянии S 10 , при отсутствии входных данных, перейдет в направленное на север состояние специальной передачи (1100)
- ячейка в , состоянии S10 получив входной сигнал, перейдет в направленное на запад состояние специальной передачи (1101)
- ячейка в состоянии S1 111 при наличии входных данных перейдет в ( состояние S11 )
- ячейка в состоянии S 11 , при отсутствии входных данных, перейдет в направленное на юг состояние специальной передачи (1110)
- ячейка в состоянии S 11 , получив входной сигнал, перейдет в спокойное конфлюэнтное состояние C 00 (1111)
- ячейка в состоянии S1 , при отсутствии входных данных , перейдет в S10 состояние (110)
Обратите внимание, что:
- для создания обычного состояния передачи, направленного на восток или север, требуется больше одного цикла ввода (четыре после начальной сенсибилизации), чем для любого другого состояния (которое требует трех циклов ввода после первоначальной сенсибилизации),
- состояние покоя «по умолчанию», приводящее к построению, представляет собой обычное состояние передачи, направленное на восток, которое требует первоначального ввода сенсибилизации, а затем четырех циклов отсутствия ввода.
Правила уничтожения
[ редактировать ]- Ввод в ячейку слитного состояния из ячейки состояния специальной передачи приведет к тому, что ячейка слитного состояния будет возвращена обратно в основное состояние.
- Аналогично, ввод в ячейку обычного состояния передачи из ячейки специального состояния передачи приведет к тому, что ячейка обычного состояния передачи будет переведена обратно в основное состояние.
- И наоборот, ввод в ячейку специального состояния передачи из ячейки обычного состояния передачи приведет к тому, что ячейка специального состояния передачи будет переведена обратно в основное состояние.
См. также
[ редактировать ]Ссылки
[ редактировать ]- Фон Нейман Дж. и А. В. Беркс (1966). Теория самовоспроизводящихся автоматов. Урбана, Издательство Университета Иллинойса. [1]
Внешние ссылки
[ редактировать ]- Golly — поддерживает CA фон Неймана вместе с Game of Life и другими наборами правил.