Клеточный автомат Кодда - это клеточный автомат (КА), разработанный британским компьютерным ученым Эдгаром Ф. Коддом в 1968 году. Он был разработан для воссоздания вычислительной и конструкционной универсальности КА фон Неймана, но с меньшим количеством состояний: 8 вместо 29. Кодд показал, что в его СА можно создать самовоспроизводящуюся машину, аналогично универсальному конструктору фон Неймана , но так и не дал полной реализации.
История
В 1940-х и 1950-х годах Джон фон Нейман поставил следующую проблему: [1]
- Какой логической организации достаточно, чтобы автомат мог воспроизводить себя?
Ему удалось сконструировать клеточный автомат с 29 состояниями, а вместе с ним и универсальный конструктор . Кодд, основываясь на работе фон Неймана, нашел более простую машину с восемью состояниями. [2] Этот модифицированный вопрос фон Неймана:
- Какая логическая организация необходима для того, чтобы автомат мог воспроизводить себя?
Через три года после работы Кодда Эдвин Роджер Бэнкс в своей докторской диссертации показал СА с четырьмя состояниями, которая также была способна к универсальным вычислениям и конструированию, но опять же не реализовал самовоспроизводящуюся машину. [3] Джон Девор в своей магистерской диссертации 1973 года изменил правила Кодда, чтобы значительно уменьшить размер конструкции Кодда до такой степени, что она могла быть реализована в компьютерах того времени. Однако лента данных для самовоспроизведения оказалась слишком длинной; Оригинальный дизайн Девора позже был воспроизведен с помощью Голли . Кристофер Лэнгтон сделал еще одну настройку клеточного автомата Кодда в 1984 году, чтобы создать петли Лэнгтона , демонстрируя самовоспроизведение с гораздо меньшим количеством клеток, чем это требовалось для самовоспроизведения в предыдущих правилах, за счет устранения возможности универсальных вычислений и конструирования. [4]
Сравнение наборов правил CA
CA | количество состояний | симметрии | вычислительная и конструктивно-универсальная | размер самовоспроизводящейся машины |
---|---|---|---|---|
фон Нейман | 29 | никто | да | 130 622 ячейки |
Кодд | 8 | вращения | да | 283,126,588 ячеек [5] |
Деворе | 8 | вращения | да | 94,794 ячейки |
Банки IV ( Banks IV Cellular Automaton ) | 2–4 [6] [7] | вращения и отражения | да | Где-то около 100000000000 ячеек |
Петли Лэнгтона | 8 | вращения | нет | 86 ячеек |
Технические характеристики
CA Кодда имеет восемь состояний, определяемых окрестностью фон Неймана с вращательной симметрией.
В таблице ниже показаны сигнальные поезда, необходимые для выполнения различных задач. Некоторые из сигнальных цепей должны быть разделены двумя пробелами (состояние 1) на проводе, чтобы избежать помех, поэтому «расширенная» сигнальная цепочка, используемая на изображении вверху, отображается здесь как «70116011».
цель | сигнальный поезд |
---|---|
продлевать | 70116011 |
extend_left | 4011401150116011 |
extend_right | 5011501140116011 |
втягивать | 4011501160116011 |
retract_left | 5011601160116011 |
retract_right | 4011601160116011 |
отметка | 701160114011501170116011 |
стереть | 601170114011501160116011 |
смысл | 70117011 |
шапка | 40116011 |
inject_sheath | 701150116011 |
inject_trigger | 60117011701160116011 |
Универсальный компьютер-конструктор
Кодд разработал самовоспроизводящийся компьютер в клеточном автомате, основанный на W-машине Вана . Однако дизайн был настолько колоссальным, что его не реализовали до 2009 года, когда Тим Хаттон сконструировал явную конфигурацию. [5] В проекте Кодда были некоторые незначительные ошибки, поэтому реализация Хаттона немного отличается как в конфигурации, так и в наборе правил.
Смотрите также
Рекомендации
- ^ фон Нейман, Джон; Беркс, Артур В. (1966). « Теория самовоспроизводящихся автоматов » . www.walenz.org. Архивировано из оригинала на 2008-01-05 . Проверено 28 января 2012 .
- ^ Кодд, Эдгар Ф. (1968). Клеточные автоматы . Academic Press, Нью-Йорк.
- ^ Бэнкс, Эдвин (1971). Обработка и передача информации в клеточных автоматах . Кандидатская диссертация, Массачусетский технологический институт, факультет машиностроения.
- ^ Лэнгтон, CG (1984). «Самовоспроизведение в клеточных автоматах» (PDF) . Physica D: нелинейные явления . 10 (1–2): 135–144. DOI : 10.1016 / 0167-2789 (84) 90256-2 . ЛВП : 2027,42 / 24968 .
- ^ а б Хаттон, Тим Дж. (2010). «Самовоспроизводящийся компьютер Кодда» (PDF) . Искусственная жизнь . 16 (2): 99–117. DOI : 10.1162 / artl.2010.16.2.16200 . PMID 20067401 .
- ^ http://www.bottomlayer.com/bottom/banks/banks_commentary_03.htm
- ^ http://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf
Внешние ссылки
- В репозитории таблиц правил есть таблица переходов для CA Кодда .
- Golly - поддерживает CA Кодда вместе с Game of Life и другими наборами правил.
- Загрузите полную машину (13 МБ) и дополнительную информацию.
- [1] показывает больше о банках IV.