Универсальный конструктор фон Неймана - Von Neumann universal constructor

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

Джон фон Нейман с универсальный конструктор это самовоспроизводящаяся машина в клеточные автоматы (CA) среда. Он был разработан в 1940-х годах без использования компьютера. Основные детали машины были опубликованы в книге фон Неймана. Теория самовоспроизводящихся автоматов, завершенный в 1966 г. Артур В. Беркс после смерти фон Неймана.[2] Хотя обычно она не так известна, как другие работы фон Неймана, она считается основополагающей для теория автоматов, сложные системы, и искусственная жизнь.[3][4] Действительно, лауреат Нобелевской премии Сидней Бреннер рассмотрел работы фон Неймана о самовоспроизводящихся автоматах (вместе с Тьюринг работа над вычислительными машинами) центральное место в биологическая теория а также, позволяя «дисциплинировать наши мысли о машинах, как естественных, так и искусственных».[5]

Цель фон Неймана, изложенная в его лекциях в Университете Иллинойса в 1949 году,[2] заключалась в разработке машины, сложность которой могла бы расти автоматически, как биологические организмы при естественный отбор. Он спросил, что такое порог сложности которые необходимо пересечь, чтобы машины могли развиваться.[4] Его ответ заключался в том, чтобы указать абстрактную машину, которая при запуске воспроизводит сама себя. В его конструкции самовоспроизводящаяся машина состоит из трех частей: «описания» («чертежа» или программы) самого себя, универсальный конструктор механизм, который может читать любое описание и создавать машину (без описания), закодированную в этом описании, и универсальный копировальный аппарат которые могут делать копии любого описания. После того, как универсальный конструктор был использован для создания новой машины, закодированной в описании, копировальная машина используется для создания копии этого описания, и эта копия передается на новую машину, что приводит к рабочей репликации исходной машины. которые могут продолжать воспроизводиться. Некоторые машины будут делать это в обратном порядке, копируя описание, а затем собирая машину. Важно отметить, что самовоспроизводящаяся машина может развиваться, накапливая мутации описания, а не самой машины, тем самым приобретая способность усложняться.[4][5]

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

Универсальный конструктор - это определенный паттерн состояний клетки в этом клеточном автомате. Он содержит одну строку ячеек, которые служат описанием (аналогично Лента Тьюринга ), кодируя последовательность инструкций, которые служат «планом» для машины. Машина читает эти инструкции одну за другой и выполняет соответствующие действия. Инструкции предписывают машине использовать свою «конструктивную руку» (другой автомат, который функционирует как Операционная система[4]), чтобы создать копию машины без ленты с описанием в каком-либо другом месте сетки ячеек. Описание не может содержать инструкции по созданию ленты описания такой же длины, как контейнер не может содержать контейнер того же размера. Таким образом, машина включает в себя отдельный копировальный аппарат, который считывает ленту описания и передает копию на вновь построенную машину. Полученный новый набор универсального конструктора и копировальных машин плюс лента с описанием идентичен старому, и он снова воспроизводится.

Цель

Система автоматов самовоспроизведения фон Неймана, способная развиваться (рисунок адаптирован из Луис Роша Конспект лекций в Университете Индианы[6]). i) самовоспроизводящаяся система состоит из нескольких автоматов плюс отдельное описание (кодировка, формализованная как Лента Тьюринга ) всех автоматов: универсальный конструктор (A), универсальный копир (B), операционная система (C), дополнительные функции, не участвующие в репликации (D), и отдельное описание Φ (A, B, C, D), кодирующее все автоматы . ii) (Вверху) Универсальный конструктор производит (декодирует) автоматы по их описанию (активный режим описания); (Внизу) Universal Copier копирует описание автоматов (пассивный режим описания); Мутации Φ (D ') в описание Φ (D) (а не изменения в автомате D напрямую) распространяются на множество автоматов, произведенных в следующем поколении, позволяя системе (автомат + описание) продолжать копирование и развитие (D → D').[4] Активный процесс построения из описания параллелей Трансляция ДНК, пассивный процесс копирования параллелей описания Репликация ДНК, и наследование мутировавших описаний параллелей Вертикальное наследование мутаций ДНК в биологии,[4][5] и были предложены фон Нейманом до открытия структуры молекулы ДНК и того, как она отдельно транслируется и реплицируется в клетке.[6]

Дизайн фон Неймана традиционно понимался как демонстрация логических требований к самовоспроизводству машин.[3] Однако ясно, что гораздо более простые машины могут достичь самовоспроизводства. Примеры включают тривиальные кристаллический рост, репликация шаблона, и Петли Лэнгтона. Но фон Неймана интересовало нечто более глубокое: конструкция, универсальность и эволюция.[4][5]

Обратите внимание, что более простые самовоспроизводящиеся структуры CA (особенно, Петля Быля и Петля Чоу – Реджа ) не могут существовать в большом разнообразии форм и поэтому имеют очень ограниченные эволюционируемость. Другие структуры CA, такие как Evoloop в некоторой степени эволюционируемы, но все же не поддерживают неограниченную эволюцию. Обычно простые репликаторы не содержат полностью механизмы построения, поскольку репликатор представляет собой информацию, копируемую окружающей средой. Хотя дизайн фон Неймана является логической конструкцией, в принципе это проект, который может быть реализован как физическая машина. Действительно, этот универсальный конструктор можно рассматривать как абстрактный симуляция физического универсальный ассемблер. Вопрос о вкладе окружающей среды в репликацию в некоторой степени открыт, поскольку существуют разные концепции сырья и его доступности.

Ключевой вывод фон Неймана состоит в том, что описание машины, которое копируется и передается потомкам отдельно через универсальный копировальный аппарат, имеет двойное назначение; будучи одновременно активный компонент строительного механизма в воспроизведении и является целью пассивный процесс копирования. Эту роль играет описание (сродни Тьюринг с лента инструкций ) в сочетании универсального конструктора и универсального копировального аппарата фон Неймана.[4] Комбинация универсального конструктора и копировального аппарата плюс лента инструкций концептуализирует и формализует i) самовоспроизведение и ii) неограниченную эволюцию или рост сложности, наблюдаемый в биологических организмах.[3]

Это открытие тем более примечательно, что оно предшествовало открытию структуры молекулы ДНК. Watson и Крик и как он отдельно транслируется и реплицируется в ячейке - хотя он следует Эксперимент Эйвери – Маклауда – Маккарти который идентифицировал ДНК как молекулярный носитель генетической информации в живых организмах.[6] Молекула ДНК обрабатывается отдельными механизмами, которые выполняют ее инструкции (перевод ) и скопируйте (копировать ) ДНК для вновь построенных клеток. Способность к неограниченной эволюции заключается в том, что, как и в природе, ошибки (мутации ) при копировании генетической ленты может привести к жизнеспособным вариантам автомата, которые затем могут развиваться через естественный отбор.[4] Как сказал Бреннер:

Тьюринг изобрел компьютер с хранимой программой, а фон Нейман показал, что описание отделено от универсального конструктора. Это нетривиально. Физик Эрвин Шредингер перепутал программу и конструктор в своей книге 1944 года «Что такое жизнь?», В которой он видел хромосомы как «замысел архитектора и ремесло строителя в одном». Это не правильно. Код скрипта содержит только описание исполнительной функции, но не самой функции.[5]

— Сидней Бреннер

Эволюция сложности

Цель фон Неймана, изложенная в его лекциях в Университете Иллинойса в 1949 году,[2] заключалась в разработке машины, сложность которой могла бы расти автоматически, как биологические организмы при естественный отбор. Он спросил, что это за порог сложности которые необходимо пересечь, чтобы машины могли развиваться и усложняться.[4][3] Его проекты «доказательства принципа» показали, насколько это возможно с логической точки зрения. Используя архитектуру, которая отделяет программируемый («универсальный») конструктор общего назначения от копировального устройства общего назначения, он показал, как описания (ленты) машин могут накапливать мутации в процессе самовоспроизведения и, таким образом, создавать более сложные машины (изображение ниже иллюстрирует эта возможность.). Это очень важный результат, поскольку до этого можно было предположить, что существует фундаментальный логический барьер для существования таких машин; в этом случае биологические организмы, которые эволюционируют и усложняются, не могут быть «машинами» в традиционном понимании. Идея фон Неймана заключалась в том, чтобы представить жизнь как машину Тьюринга, которая аналогичным образом определяется определяемой состоянием «головой» машины, отделенной от ленты памяти.[5]

На практике, когда мы рассматриваем конкретную реализацию автомата, которую преследовал фон Нейман, мы делаем вывод, что она не дает особой эволюционной динамики, потому что машины слишком хрупкие - подавляющее большинство возмущений заставляет их эффективно разрушаться.[3] Таким образом, это концептуальная модель, изложенная в его лекциях в Иллинойсе.[2] Сегодня это вызывает больший интерес, потому что показывает, как машина может развиваться в принципе.[7][4] Это понимание тем более примечательно, что модель предшествовала открытию структуры молекулы ДНК, о которой говорилось выше.[6] Также примечательно, что дизайн фон Неймана считает, что мутации в сторону большей сложности должны происходить в (описаниях) подсистем, не участвующих в самом самовоспроизведении, как это концептуализировано дополнительным автоматом. D он считал, что выполняет все функции, непосредственно не участвующие в воспроизводстве (см. рисунок выше с Системой автоматов самовоспроизведения фон Неймана, способной развиваться). Действительно, у биологических организмов наблюдались лишь очень незначительные вариации генетического кода, что соответствует Обоснование фон Неймана о том, что универсальный конструктор (А) и копир (B) не будут сами развиваться, оставив всю эволюцию (и рост сложности) автомату. D.[4] В своей незаконченной работе фон Нейман также кратко рассматривает конфликты и взаимодействия между своими самовоспроизводящимися машинами, чтобы понять эволюцию экологических и социальных взаимодействий на основе своей теории самовоспроизводящихся машин.[2]:147

Демонстрация способности машины фон Неймана поддерживать наследуемые мутации. (1) На более раннем временном шаге мутация была вручную добавлена ​​на ленту машины второго поколения. (2) Более поздние поколения демонстрируют фенотип мутации (рисунок цветка) и передать мутацию своим детям, поскольку лента каждый раз копируется. Этот пример показывает, как конструкция фон Неймана допускает рост сложности (теоретически), поскольку лента может указывать на более сложную машину, чем та, которая ее производит.

Реализации

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

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

Ренато Нобили и Умберто Песавенто опубликовали первый полностью реализованный самовоспроизводящийся клеточный автомат в 1995 году, почти через пятьдесят лет после работы фон Неймана.[1][8] Они использовали клеточный автомат с 32 состояниями вместо оригинального фон Неймана. 29-состояние, расширяя его, чтобы обеспечить более легкий переход сигналов, явную функцию памяти и более компактный дизайн. Они также опубликовали реализацию общего конструктора в исходном CA с 29 состояниями, но не способного к полной репликации - конфигурация не может дублировать свою ленту и не может запускать свое потомство; конфигурацию можно только построить.[8][9]

В 2004 г. D. Mange et al. сообщили о реализации самовоспроизводящегося репликатора, который согласуется с конструкциями фон Неймана.[10]

В 2007 году Nobili опубликовал реализацию с 32 состояниями, в которой используется кодирование длин серий чтобы значительно уменьшить размер ленты.[11]

В 2008 году Уильям Р. Бакли опубликовал две конфигурации, которые являются саморепликаторами в исходной 29-государственной CA фон Неймана.[9] Бакли утверждает, что пересечение сигнала внутри клеточных автоматов фон Неймана с 29 состояниями не является необходимым для построения саморепликаторов.[9] Бакли также указывает, что для целей эволюции каждый репликатор должен вернуться к своей исходной конфигурации после репликации, чтобы быть способным (теоретически) создавать более одной копии. Как было опубликовано, дизайн Nobili-Pesavento 1995 года не соответствует этому требованию, но дизайн Nobili 2007 года выполняет; то же самое можно сказать и о конфигурациях Бакли.

В 2009 году Бакли опубликовал Господи Третья конфигурация для клеточных автоматов фон Неймана с 29 состояниями, которые могут выполнять либо целостную саморепликацию, либо самовоспроизведение путем частичного построения. Эта конфигурация также демонстрирует, что пересечение сигналов не является необходимым для построения саморепликаторов внутри клеточных автоматов фон Неймана с 29 состояниями.

К. Л. Неханив в 2002 г., а также Ю. Такада с соавт. в 2004 г. предложил универсальный конструктор, реализованный непосредственно на асинхронном клеточном автомате, а не на синхронном клеточном автомате.[12][13]

Сравнение реализаций

ВыполнениеИсточникНабор правилПрямоугольная областьКоличество ячеекДлина лентыСоотношениеПериодСжатие кода лентыДлина кода лентыТип кода лентыМеханизм репликацииТип репликацииСкорость роста
Нобили-Песавенто, 1995 г.[1][14]Нобили 32-состояние97 × 1706,329145,31522.966.34 × 1010никто5 битдвоичныйцелостный конструкторнеповторимыйлинейный
Нобили, 2007 г.SR_CCN_AP.EVN[15]Нобили 32-состояние97 × 1005,31356,32510.609.59 × 109кодирование с ограничением длины прогона5 битдвоичныйцелостный конструкторповторяемыйсуперлинейный
Бакли, 2008 г.codon5.rle[16]Нобили 32-состояние112 × 503,34344,15513.215,87 х 109автоматическая ретракция5 битдвоичныйцелостный конструкторповторяемыйлинейный
Бакли, 2008 г.[9]Replicator.mc[17]фон Неймана 29-состояние312 × 13218,589294,84415.862.61 × 1011автоматический возврат5 битдвоичныйцелостный конструкторповторяемыйлинейный
Бакли, 2008 г.codon4.rle[16]Нобили 32-состояние109 × 593,57437,78010.574,31 х 109автоматическая ретракция / генерация бит4 битадвоичныйцелостный конструкторповторяемыйлинейный
Бакли, 2009 г.codon3.rleНобили 32-состояние116 × 954,85523,5774.861,63 х 109автооттягивание / генерация бит / наложение кода3 битадвоичныйцелостный конструкторповторяемыйсуперлинейный
Бакли, 2009 г.PartialReplicator.mc[16]фон Неймана 29-состояние2063 × 377264,321NA-≈1,12 х 1014никто4 битадвоичныйчастичный конструкторповторяемыйлинейный
Гушер и Бакли, 2012 г.phi9.rle[18]Нобили 32-состояние122 × 60395789202.25-автоматическое ретракция / генерация бит / наложение кода / ограничение длины прогона3+ биттройнойцелостный конструкторповторяемыйсуперлинейный

Согласно определению фон Неймана, универсальная конструкция влечет за собой построение только пассивных конфигураций. Таким образом, концепция универсального построения представляет собой не что иное, как литературный (или, в данном случае, математический) прием. Это способствовало другим доказательствам, например, что хорошо сконструированная машина может участвовать в самовоспроизведении, в то время как сама универсальная конструкция просто предполагалась в самом минимальном случае. Универсальная конструкция по этому стандарту тривиальна. Следовательно, хотя все приведенные здесь конфигурации могут создавать любую пассивную конфигурацию, ни одна из них не может создать пересекающий орган в реальном времени, разработанный Горманом.[9]

Практичность и вычислительные затраты

Все реализации самовоспроизводящейся машины фон Неймана требуют значительных ресурсов для работы на компьютере. Например, в реализации Nobili-Pesavento с 32 состояниями, показанной выше, в то время как корпус машины состоит всего из 6329 непустых ячеек (в пределах прямоугольника размером 97x170), для нее требуется лента длиной 145 315 ячеек и занимает 63 миллиард временных шагов для воспроизведения. На создание первой копии симулятора, работающего со скоростью 1000 шагов в секунду, потребуется более 2 лет. В 1995 году, когда была опубликована первая реализация, авторы не видели репликации своей собственной машины. Однако в 2008 г. хеш-жизнь алгоритм был расширен для поддержки наборов правил с 29 и 32 состояниями в Господи. На современном настольном ПК репликация теперь занимает всего несколько минут, хотя требуется значительный объем памяти.

Галерея анимации

  • Пример руки чтения с 29 состояниями.

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

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

  1. ^ а б c Песавенто, Умберто (1995), «Реализация самовоспроизводящейся машины фон Неймана» (PDF), Искусственная жизнь, MIT Press, 2 (4): 337–354, Дои:10.1162 / artl.1995.2.337, PMID  8942052, заархивировано из оригинал (PDF) 21 июня 2007 г.
  2. ^ а б c d е фон Нейман, Джон; Беркс, Артур В. (1966), Теория самовоспроизводящихся автоматов. (Отсканированная книга онлайн), Университет Иллинойса Press, получено 2017-02-28
  3. ^ а б c d е Макмаллин, Б. (2000), «Джон фон Нейман и эволюционный рост сложности: взгляд назад, взгляд вперед ...», Искусственная жизнь, 6 (4): 347–361, Дои:10.1162/106454600300103674, PMID  11348586
  4. ^ а б c d е ж грамм час я j k л Роча, Луис М. (1998), «Избранная самоорганизация и семиотика эволюционных систем», Эволюционные системы, Springer, Dordrecht: 341–358.
  5. ^ а б c d е ж Бреннер, Сидней (2012), «Скрипт кода жизни», Природа, 482: 461, Дои:10.1038 / 482461a, PMID  22358811
  6. ^ а б c d Роча, Луис М. (2015), «Глава 6. Фон Нейман и естественный отбор». (PDF), Лекционные заметки по курсу I-485-Биологически вдохновленные вычисления, Университет Индианы (PDF)
  7. ^ Патти, Ховард, Х. (1995), «Эволюция самореференции: символы материи и семантическая завершенность», Коммуникация и познание Искусственный интеллект, 12(1-2): 9–27
  8. ^ а б Нобили, Ренато; Песавенто, Умберто (1996), «Обобщенные автоматы фон Неймана», в Besussi, E .; Чеккини, А. (ред.), Proc. Искусственные миры и урбанистика, Конференция 1 (PDF), Венеция: DAEST
  9. ^ а б c d е Бакли, Уильям Р. (2008), "Решения по пересечению сигналов в самовоспроизводящихся клеточных автоматах фон Неймана", в Андрей Адамацки; Рамон Алонсо-Санс; Анна Лавничак; Хенаро Хуарес Мартинес; Кеничи Морита; Томас Уорш (ред.), Proc. Автоматы 2008 (PDF), Лунивер Пресс, стр. 453–503.
  10. ^ Манге, Дэниел; Stauffer, A .; Peparaolo, L .; Темпести, Г. (2004), "Макроскопический взгляд на самовоспроизведение", Труды IEEE, 92 (12): 1929–1945, Дои:10.1109 / JPROC.2004.837631
  11. ^ «Архивная копия». Архивировано из оригинал 29 января 2011 г.. Получено 29 января, 2011.CS1 maint: заархивированная копия как заголовок (ссылка на сайт)
  12. ^ Неханив, Кристофер Л. (2002), "Самовоспроизводство в асинхронных клеточных автоматах", Конференция НАСА / Министерства обороны 2002 г. по эволюционируемому оборудованию (15-18 июля 2002 г., Александрия, Вирджиния, США), IEEE Computer Society Press, стр. 201–209.
  13. ^ Такада, Юске; Исокава, Тейджиро; Пепер, Фердинанд; Мацуи, Нобуюки (2004), «Универсальная конструкция на самосинхронных клеточных автоматах», в Sloot, P.M.A. (ред.), ACRI 2004, LNCS 3305, стр. 21–30
  14. ^ "Самовоспроизводящийся универсальный конструктор фон Неймана".
  15. ^ Клеточные автоматы Джона фон Неймана[1]
  16. ^ а б c Andykt. «Боже, симулятор игры в жизнь». SourceForge.
  17. ^ [2]
  18. ^ «Самовоспроизведение». Комплексное проективное 4-пространство.

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