Клеточные автоматы Нобили - Википедия - Nobili cellular automata

λграмм, минимальная самовоспроизводящаяся конфигурация в клеточных автоматах Нобили

Клеточные автоматы нобили (NCA) являются разновидностью клеточные автоматы фон Неймана (vNCA), в котором дополнительные состояния предоставляют средства памяти и беспрепятственного пересечения сигнала. Клеточные автоматы Nobili - это изобретение Ренато Нобили, профессор физики Падуанский университет в Падуе, Италия. Фон Нейман специально исключил использование состояний, предназначенных для пересечения сигнала.

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

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

Пересечение сигнала в vNCA

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

Схема органа пересечения Мухопадхьяй с тремя воротами исключающее ИЛИ.

Пересечение сигнала в NCA

В клеточном автомате Nobili орган, пересекающий сигнал, состоит из одной сливной клетки с двумя перпендикулярными входными путями и двумя перпендикулярными выходными путями. Из-за существенно уменьшенного размера (по сравнению с любым из пересекающихся органов vNCA) самовоспроизводящиеся машины в NCA намного компактнее. Например, самый маленький на данный момент репликатор λграмм, состоит всего из 485 соматических клеток.

Хранение памяти в vNCA

Хранить память в vNCA можно несколькими способами. Один из них (электронный метод) - создать петлю из ячеек ОТС, вокруг которой проходит возбужденный импульс. Безусловно, наиболее распространенный способ (электромеханический метод) - использовать особое состояние передачи для создания и удаления обычного состояния передачи, чтобы действовать как затвор. Незначительные модификации могут дать множество различных вентилей, включая защелки, делители импульсов и одноразовые вентили.

Хранение памяти в NCA

В клеточном автомате Нобили эта задача также упрощена. Конфлюэнтная ячейка без выходов «держит» импульс возбуждения до тех пор, пока не будет создан выход. На диаграмме λграмм выше возбужденная конфлюэнтная ячейка отображается оранжевым цветом. Он будет оставаться в этом состоянии до тех пор, пока не будет создана соседняя ячейка OTS, после чего информация будет перетекать в следующую сливающуюся ячейку.

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

  • Бакли, Уильям Р. (01.01.2008). "(PDF) Решения пересечения сигналов в самовоспроизводящихся клеточных автоматах фон Неймана". ResearchGate. Получено 2019-09-30.CS1 maint: ref = harv (связь)