Самовоспроизводящиеся клеточные автоматы

Самовоспроизводящиесяклеточныеавтоматы

Эдвард Фредкин наиболее известен в наши дни благодаря воротам Фредкина, универсальной обратимой схеме.

Недавно я узнал, что Фредкин был одним из пионеров в области сотовой связи. автоматы. Его ученик Эдвин Бэнкс описывает клеточный автомат, введенный Фредкиным. .

Эдвард Фредкин из Массачусетского технологического института описал следующее интересное клеточное пространство. Если состояния равны 0 и 1 и если состояние результата получается суммированием соседей по модулю 2, то каждая начальная конфигурация будет воспроизводить свои копии относительно начальной конфигурации.

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

Есть некоторая двусмысленность относительно того, что означает «соседи». В диссертации Бэнкса соседями участка считаются участки на севере, юге, востоке и западе, и это означает, что Бэнкс имеет в виду этих соседей, когда описывает автомат Фредкина. Другие источники говорят, что Фредкин также считал соседние по диагонали участки частью района, то есть северо-запад, северо-восток, юго-запад и юго-восток.

Бэнкс продолжает говорить

Терри Виноград (1970) обобщил этот результат, показывая, что любое соседство, а не только четыре ближайших соседа, и любое количество измерений по-прежнему дает те же результаты.

Я беру это по «четырем ближайшим соседям» – соседям на севере, юге, востоке и западе. Я не уверен, что означает «любое соседство» в теореме Винограда; Я полагаю, что должно быть какое-то подразумеваемое ограничение.

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

Я начну с буквы «E» в середине сетки. Черные квадраты представляют нули, а белые квадраты – единицы.

initial state

Вот первые восемь шагов в развитии этого паттерна с использованием правила, согласно которому «сосед» включает только северных, южных, восточных и западных соседей.

Если мы рассмотрим каждую точку на есть восемь соседей, т.е. мы включаем диагонали, вот как выглядят первые восемь шагов.

Обновление: вот анимированная версия первого автомата

и второй

Эдвин Р. Бэнкс, Обработка и передача информации в клеточных автоматах. Диссертация в Массачусетском технологическом институте. Январь 1971.

Leave a comment

Your email address will not be published. Required fields are marked *