Лекция
Привет, Вы узнаете о том , что такое клеточный автомат фон неймана, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое клеточный автомат фон неймана , настоятельно рекомендую прочитать все из категории Моделирование и Моделирование систем.
клеточный автомат фон неймана — клеточный автомат, разработанный фон Нейманом при содействии Станислава Улама для исследования возможности создания самовоспроизводящихся машин.
Одна из простых конфигураций в клеточном автомате фон Неймана. Двоичный сигнал циркулирует вдоль петли из синих ячеек, используя переход между обычным и возбужденным состоянием передающих ячеек. Коммутирующая ячейка дублирует сигнал в красную линию, состоящую из ячеек особого передающего состояния. Сигнал проходит по линии и создает новую ячейку. Двоичный сигнал 1011 кодирует восточно-ориентированное передающее состояние, таким образом продолжая линию вправо. В процессе создания новая ячейка, управляемая бинарной последовательностью, проходит ряд сенсибилизированных состояний.
Клеточный автомат в общем виде представляет собой упорядоченное множество конечных автоматов, обменивающихся информацией с соседними автоматами. В клеточном автомате фон Неймана ячейки упорядочены в виде двухмерной прямоугольной решетки и взаимодействуют с четырьмя непосредственно прилегающими ячейками, образующими окрестность фон Неймана. Решетка считается имеющей бесконечный размер в обоих направлениях, а ячейки — идентичными в плане правил перехода. Изменение состояний всех ячеек происходит синхронно.
Каждый конечный автомат в пространстве фон Неймана может принимать одно из 29 состояний:
Каждое из передающих состояний (8 состояний) также характеризуется возбужденностью/невозбужденностью (зеленые/синие стрелочки), что дает в итоге 16 передающих состояний. Возбужденное состояние переносит данные со скоростью 1 бит за такт. Конфлюентные состояния имеют задержку на один такт, и таким образом могут хранить 2 бита информации.
Поток информации между ячейками определяется свойством направленности. Применяются следующие правила:
Следующие правила применяются к конфлюентным состояниям:
Девять типов ячеек, которые могут быть созданы в КА фон Неймана. Об этом говорит сайт https://intellect.icu . Здесь двоичные сигналы проходят по обычным передающим ячейкам, создавая новые ячейки на конце линий. К примеру, двоичная строка 1011, показанная в пятой линии, создает специальное передающее состояние с направлением вправо. Взаимодействие между передающими линиями отсутствует, что позволяет плотно упаковывать ячейки.
В исходном состоянии большая часть клеточного пространства является «пустой», то есть заполненной ячейками в состоянии U. Получив входной сигнал от передающей ячейки, соседняя ячейка в состоянии U переходит в транзитное состояние, проходит ряд состояний и оказывается в одном из передающих или конфлюентных состояний. Это конечное состояние определяется последовательностью входных сигналов. То есть транзитные состояния могут рассматриваться как точки бифуркации на пути от базового состояния к передающим и конфлюентным. В следующих правилах последовательность входных сигналов указана в скобках двоичной строкой:
Примерно 4000 битов данных конструируют сложный паттерн. Здесь используется разновидность КА фон Неймана с 32 состояниями, известная как Hutton32.
Одной из разновидностей автомата фон Неймана является автомат Нобили, в котором введены дополнительные состояния для обеспечения памяти и возможности пересечения сигналов без интерференции, для чего использована возможность хранения информации группами клеток. Последняя функция требует три дополнительных состояния, в силу чего автомат Нобили имеет 32 состояния, а не 29. Является изобретением Ренато Нобили (итал. Renato Nobili), профессора физики университета Падуя, Италия. Фон Нейман намеренно исключил состояния, предназначенные для пересечения сигналов.
Конфлюентное состояние изменено таким образом, чтобы передавать независимо друг от друга два одновременно приходящих сигнала, либо запоминать и передавать с задержкой входные сигналы.
Еще одной разновидностью является автомат Хаттона (англ. Hutton), допускающий репликацию кольцевых структур (см. Langton's loops на английском языке).
Клеточный автомат Нобили — разновидность клеточного автомата фон Неймана, в который введены дополнительные состояния для обеспечения памяти и возможности пересечения сигналов без интерференции. Является изобретением Ренато Нобили, профессора физики университета Падуя, Италия. Фон Нейман намеренно исключил состояния, предназначенные для пересечения сигналов.
Конфлюентное состояние изменено таким образом, чтобы передавать независимо друг от друга два одновременно приходящих сигнала, либо запоминать и передавать с задержкой входные сигналы.
λ G , минимальная самовоспроизводящаяся конфигурация в клеточных автоматах Нобили
Клеточные автоматы Нобили (NCA) представляют собой разновидность клеточных автоматов фон Неймана (vNCA), в которых дополнительные состояния обеспечивают средства памяти и беспрепятственное пересечение сигнала. Клеточные автоматы Nobili - изобретение Ренато Нобили , профессора физики Падуанского университета в Падуе, Италия. Фон Нейман специально исключил использование состояний, предназначенных для пересечения сигнала.
Конфлюэнтное состояние изменяется, так что оно действует как орган, пересекающий сигнал, если попадают ровно два пути сигнала (они входят и выходят из конфлюэнтного состояния), или действует как орган памяти, если существуют только входы.
Преимущество этих изменений в наборе состояний клеточных автоматов фон Неймана состоит в том, что пересечение сигналов значительно упрощается, конфигурации немного меньше, чем соответствующая конфигурация клеточных автоматов фон Неймана, и увеличивается вычислительная производительность.
В оригинальном клеточном автомате фон Неймана пересечение сигналов намного сложнее. Наиболее широко используемые органы пропуска сигнала являются кодированный канал (разработанный самим фон Неймана), Гормана в реальном масштабе времени пересечения органа , и пересечения органа Mukhopadhyay . Кодированный канал может пересекать только отдельные импульсы; другие способны беспрепятственно пересекать целые пакеты, аналогично органу пересечения в клеточном автомате Нобили. Орган пересечения Mukhopadhyay состоит из трех ворот XOR , как показано (слева).
Схема пересекающего органа Мухопадхьяй, показывающая три ворот исключающее-ИЛИ.
В клеточном автомате Nobili орган, пересекающий сигнал, состоит из одной сливающейся клетки с двумя перпендикулярными входными путями и двумя перпендикулярными выходными путями. Из-за существенно уменьшенного размера (по сравнению с любым из пересекающихся органов vNCA) самовоспроизводящиеся машины в NCA намного компактнее. Например, самый маленький на сегодняшний день репликатор, λ G , включает всего 485 соматических клеток.
Хранить память в vNCA можно несколькими способами. Один из них (электронный метод) состоит в создании петли из ячеек ОТС, вокруг которой проходит возбужденный импульс. Самым распространенным способом (электромеханический метод) является использование специального состояния передачи для создания и удаления обычного состояния передачи, которое действует как затвор. Незначительные модификации могут привести к появлению множества различных вентилей, включая защелки, делители импульсов и одноразовые вентили.
В клеточном автомате Нобили эта задача также упрощена. Конфлюэнтная ячейка без выходов «держит» импульс возбуждения до тех пор, пока не будет создан выход. На диаграмме λ G выше возбужденная конфлюэнтная ячейка отображается оранжевым цветом. Он будет оставаться в этом состоянии до тех пор, пока не будет создана соседняя ячейка OTS, после чего информация будет перетекать в следующую конфлюэнтную ячейку.
Исследование, описанное в статье про клеточный автомат фон неймана, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое клеточный автомат фон неймана и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Моделирование и Моделирование систем
Комментарии
Оставить комментарий
Моделирование и Моделирование систем
Термины: Моделирование и Моделирование систем