WikiDer > Клеточный автомат Codds - Википедия

Codds cellular automaton - Wikipedia
Простая конфигурация клеточного автомата Кодда. Сигналы проходят по проводу, состоящему из ячеек в состоянии 1 (синий), покрытых ячейками в состоянии 2 (красный). Две сигнальные цепочки циркулируют по петле и дублируются в Т-образном соединении на открытый участок провода. Первый (7-0) заставляет оголиться конец провода в оболочке. Второй (6-0) снова обволакивает оголенный конец, оставляя провод на одну ячейку длиннее, чем раньше.

Клеточный автомат Кодда это клеточный автомат (CA) разработан Британский специалист в области информатики Эдгар Ф. Кодд в 1968 году. Он был разработан, чтобы воссоздать вычислительную и конструктивную универсальность фон Неймана но с меньшим количеством состояний: 8 вместо 29. Кодд показал, что можно создать самовоспроизводящуюся машину в его СА, аналогично тому, как это сделал фон Нейман. универсальный конструктор, но так и не дал полной реализации.

История

В 1940-х и 1950-х годах Джон фон Нейман поставил следующую проблему:[1]

  • Какого рода логическая организация достаточна для того, чтобы автомат мог воспроизводить себя?

Он смог построить клеточный автомат с 29 штатами, а с ним универсальный конструктор. Кодд, основываясь на работе фон Неймана, нашел более простую машину с восемью состояниями.[2] Это модифицированный вопрос фон Неймана:

  • Что это за логическая организация необходимо чтобы автомат мог воспроизводить себя?

Через три года после работы Кодда Эдвин Роджер Бэнкс в своей докторской диссертации показал СА с четырьмя состояниями, которая также была способна к универсальным вычислениям и построению, но опять же не реализовал самовоспроизводящуюся машину.[3] Джон Девор в своей магистерской диссертации 1973 года изменил правила Кодда, чтобы значительно уменьшить размер дизайна Кодда до такой степени, что он мог быть реализован в компьютерах того времени. Однако лента данных для самовоспроизведения была слишком длинной; Оригинальный дизайн Девора позже был воспроизведен с использованием Господи. Кристофер Лэнгтон сделал еще одну настройку клеточного автомата Кодда в 1984 году, чтобы создать Петли Лэнгтона, демонстрируя самовоспроизведение с гораздо меньшим количеством клеток, чем это требовалось для самовоспроизведения в предыдущих правилах, за счет устранения возможности универсальных вычислений и конструирования.[4]

Сравнение наборов правил CA

CAколичество состоянийсимметриивычислительные и конструктивные универсальныеразмер самовоспроизводящейся машины
фон Нейман29никтода130 622 ячейки
Codd8вращенияда283,126,588 ячеек[5]
Деворе8вращенияда94,794 ячейки
Банки IV (Банки IV Сотовый автомат)2 - 4 [6][7]вращения и отражениядаГде-то около 100000000000 ячеек
Петли Лэнгтона8вращениянет86 ячеек

Технические характеристики

Строительный рычаг в СА Кодда можно переместить в нужное положение с помощью команд, перечисленных в тексте. Здесь рука поворачивается влево, затем вправо, затем записывает ячейку, прежде чем отступить по тому же пути.

CA Кодда имеет восемь состояний, определяемых район фон Неймана с вращательной симметрией.

В таблице ниже показаны сигнальные поезда, необходимые для выполнения различных задач. Некоторые из сигнальных цепей должны быть разделены двумя пробелами (состояние 1) на проводе, чтобы избежать помех, поэтому «расширенная» сигнальная цепочка, используемая на изображении вверху, отображается здесь как «70116011».

цельсигнальный поезд
продлевать70116011
extend_left4011401150116011
extend_right5011501140116011
втягивать4011501160116011
retract_left5011601160116011
retract_right4011601160116011
отметка701160114011501170116011
стереть601170114011501160116011
смысл70117011
колпачок40116011
inject_sheath701150116011
inject_trigger60117011701160116011

Универсальный компьютер-конструктор

Кодд разработал самовоспроизводящийся компьютер в клеточном автомате на основе W-машина Вана. Однако дизайн был настолько колоссальным, что его не реализовали до 2009 года, когда Тим Хаттон сконструировал явную конфигурацию.[5] В дизайне Кодда были некоторые незначительные ошибки, поэтому реализация Хаттона немного отличается как в конфигурации, так и в наборе правил.

Смотрите также

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

  1. ^ фон Нейман, Джон; Беркс, Артур В. (1966). "Теория самовоспроизводящихся автоматов.". www.walenz.org. Архивировано из оригинал на 2008-01-05. Получено 2012-01-28.
  2. ^ Кодд, Эдгар Ф. (1968). Клеточные автоматы. Academic Press, Нью-Йорк.
  3. ^ Бэнкс, Эдвин (1971). Обработка и передача информации в клеточных автоматах. Кандидатская диссертация, MIT, факультет машиностроения.
  4. ^ Лэнгтон, К. Г. (1984). «Самовоспроизводство в клеточных автоматах» (PDF). Physica D: нелинейные явления. 10 (1–2): 135–144. Дои:10.1016/0167-2789(84)90256-2.
  5. ^ а б Хаттон, Тим Дж. (2010). "Самовоспроизводящийся компьютер Кодда" (PDF). Искусственная жизнь. 16 (2): 99–117. Дои:10.1162 / artl.2010.16.2.16200. PMID 20067401.
  6. ^ http://www.bottomlayer.com/bottom/banks/banks_commentary_03.htm
  7. ^ http://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf

внешняя ссылка