Клеточный автомат Кодда
Клеточный автомат Кодда — клеточный автомат (КА), разработанный британским ученым-компьютерщиком Эдгаром Ф. Коддом в 1968 году. Он был разработан для воссоздания универсальности вычислений и конструкций КА фон Неймана , но с меньшим количеством состояний: 8 вместо 29. Кодд показал, что в его КА можно создать самовоспроизводящуюся машину, аналогично универсальному конструктору фон Неймана , но так и не дал полной реализации.
История
В 1940-х и 1950-х годах Джон фон Нейман сформулировал следующую проблему: [1]
- Какая логическая организация достаточна для того, чтобы автомат мог воспроизводить себя?
Он смог построить клеточный автомат с 29 состояниями, а вместе с ним и универсальный конструктор . Кодд, основываясь на работе фон Неймана, нашел более простую машину с восемью состояниями. [2] Это изменило вопрос фон Неймана:
- Какая логическая организация необходима автомату, чтобы иметь возможность воспроизводить себя?
Через три года после работы Кодда Эдвин Роджер Бэнкс в своей докторской диссертации показал 4-х ступенчатый КА, который также был способен к универсальным вычислениям и построению, но снова не реализовал самовоспроизводящуюся машину. [3] Джон Девор в своей магистерской диссертации 1973 года подправил правила Кодда, чтобы значительно уменьшить размер конструкции Кодда. Моделирование конструкции Девора было продемонстрировано на третьей конференции по искусственной жизни в 1992 году, показав последние шаги построения и активации модели потомства, но полная саморепликация не была смоделирована до 2000-х годов с использованием Golly . Кристофер Лэнгтон внес еще одну поправку в клеточный автомат Кодда в 1984 году, чтобы создать петли Лэнгтона , демонстрируя саморепликацию с гораздо меньшим количеством клеток, чем требовалось для самовоспроизводства в предыдущих правилах, ценой устранения возможности универсальных вычислений и построения. [4]
Сравнение наборов правил CA
| КА | количество штатов | симметрии | вычислительно- и конструкционно-универсальный | размер самовоспроизводящейся машины |
|---|---|---|---|---|
| фон Нейман | 29 | никто | да | 130 622 ячеек |
| Кодд | 8 | вращения | да | 283,126,588 клеток [5] |
| Деворе | 8 | вращения | да | 94,794 ячеек |
| Banks IV (Клеточный автомат Banks IV) | 2 - 4 [6] [3] | вращения и отражения | да | Где-то около 100 000 000 000 клеток |
| петли Лэнгтона | 8 | вращения | нет | 86 ячеек |
Спецификация
Калибровочный автомат Кодда имеет восемь состояний, определяемых окрестностью фон Неймана с вращательной симметрией.
В таблице ниже показаны сигнальные последовательности, необходимые для выполнения различных задач. Некоторые сигнальные последовательности должны быть разделены двумя пробелами (состояние 1) на проводе, чтобы избежать помех, поэтому сигнальная последовательность «extend», используемая на изображении вверху, здесь представлена как «70116011».
| цель | сигнальный поезд |
|---|---|
| продлевать | 70116011 |
| продлить_влево | 4011401150116011 |
| расширить_право | 5011501140116011 |
| отозвать | 4011501160116011 |
| retract_left | 5011601160116011 |
| retract_right | 4011601160116011 |
| отметка | 701160114011501170116011 |
| стереть | 601170114011501160116011 |
| смысл | 70117011 |
| колпачок | 40116011 |
| инъекция_оболочки | 701150116011 |
| inject_trigger | 60117011701160116011 |
Универсальный компьютер-конструктор
Кодд спроектировал самовоспроизводящийся компьютер в клеточном автомате на основе W-машины Вана . Однако проект был настолько колоссален, что избегал реализации до 2009 года, когда Тим Хаттон сконструировал явную конфигурацию. [5] В проекте Кодда были некоторые незначительные ошибки, поэтому реализация Хаттона немного отличается как по конфигурации, так и по набору правил.
Смотрите также
- Искусственная жизнь
- Клеточный автомат
- Игра жизни Конвея
- петли Лэнгтона
- Клеточный автомат фон Неймана
- Wireworld
Ссылки
- ^ фон Нейман, Джон; Беркс, Артур В. (1966). "Теория самовоспроизводящихся автоматов". www.walenz.org. Архивировано из оригинала 2008-01-05 . Получено 2012-01-28 .
- ^ Кодд, Эдгар Ф. (1968). Клеточные автоматы . Academic Press, Нью-Йорк.
- ^ ab Banks, Edwin (1971). Обработка и передача информации в клеточных автоматах. Кандидатская диссертация, Массачусетский технологический институт, кафедра машиностроения.
- ^ Лэнгтон, К. Г. (1984). «Самовоспроизведение в клеточных автоматах» (PDF) . Physica D: Nonlinear Phenomena . 10 ( 1– 2): 135– 144. Bibcode :1984PhyD...10..135L. doi :10.1016/0167-2789(84)90256-2. hdl : 2027.42/24968 .
- ^ ab Hutton, Tim J. (2010). "Самовоспроизводящийся компьютер Кодда" (PDF) . Искусственная жизнь . 16 (2): 99– 117. doi :10.1162/artl.2010.16.2.16200. PMID 20067401. S2CID 10049331. Архивировано из оригинала (PDF) 2012-02-05 . Получено 2010-08-01 .
- ^ «Доказательство Роджера Бэнкса универсальности вычислений в клеточных автоматах».
Внешние ссылки
- В репозитории таблиц правил имеется таблица переходов для CA Кодда.
- Golly - поддерживает CA Кодда, а также игру «Жизнь» и другие наборы правил.
- Загрузите полную версию машины (13 МБ) и более подробную информацию.
- [1] показывает больше информации о Банксе IV.
