Войти
Первая реализация самовоспроизводящегося универсального конструктора фон Неймана. Показаны три поколения машин: второе почти закончило постройку третьего. Строки, идущие вправо, - это ленты генетических инструкций, которые копируются вместе с телом машин. Показанная машина работает в 32-государственной версии среды клеточных автоматов фон Неймана, а не в его исходной спецификации с 29 состояниями. Универсальный конструктор Джона фон Неймана является самим собой -реплицирующая машина в среде клеточных автоматов (CA). Он был разработан в 1940-х годах без использования компьютера. Основные детали машины были опубликованы в книге фон Неймана «Теория самовоспроизводящихся автоматов», завершенной в 1966 году Артуром В. Берксом после смерти фон Неймана. Хотя обычно она не так известна, как другие работы фон Неймана, она считается основополагающей для теории автоматов, сложных систем и искусственной жизни. Действительно, лауреат Нобелевской премии Сидней Бреннер считал работу фон Неймана о самовоспроизводящихся автоматах (вместе с работой Тьюринга о вычислительных машинах) центральной в биологической теории., позволяя нам «дисциплинировать наши мысли о машинах, как естественных, так и искусственных».
Целью фон Неймана, как указано в его лекциях в Университете Иллинойса в 1949 году, было разработать машину, сложность которой могла бы расти автоматически сродни биологическим организмам естественного отбора. Он спросил, каков порог сложности, который необходимо преодолеть, чтобы машины могли развиваться. Его ответ заключался в том, чтобы указать абстрактную машину, которая при запуске воспроизводит сама себя. В его конструкции самовоспроизводящаяся машина состоит из трех частей: «описания» («чертежа» или программы) самого себя, универсального конструкторского механизма, который может прочитать любое описание и построить машину (без описания), закодированную в этом описании., и универсальный копировальный аппарат, который может делать копии любого описания. После того, как универсальный конструктор был использован для создания новой машины, закодированной в описании, копировальная машина используется для создания копии этого описания, и эта копия передается на новую машину, что приводит к рабочей репликации исходной машины. которые могут продолжать воспроизводиться. Некоторые машины будут делать это в обратном порядке, копируя описание, а затем собирая машину. Важно отметить, что самовоспроизводящаяся машина может развиваться, накапливая мутации описания, а не самой машины, таким образом получая способность усложняться.
Чтобы определить свою машину более подробно, фон Нейман изобрел концепцию клеточный автомат. , который он использовал, состоит из двумерной сетки ячеек, каждая из которых может находиться в одном из 29 состояний в любой момент времени. На каждом временном шаге каждая ячейка обновляет свое состояние в зависимости от состояний окружающих ячеек на предыдущем временном шаге. Правила, регулирующие эти обновления, идентичны для всех ячеек.
Универсальный конструктор - это определенный паттерн состояний клетки в этом клеточном автомате. Он содержит одну строку ячеек, которые служат в качестве описания (сродни ленте Тьюринга ), кодирующей последовательность инструкций, которые служат «планом» для машины. Машина читает эти инструкции одну за другой и выполняет соответствующие действия. Инструкции предписывают машине использовать свою «конструктивную руку» (другой автомат, который функционирует как Операционная система ) для создания копии машины без ленты описания в каком-либо другом месте в сетке ячеек. Описание не может содержать инструкции по созданию ленты описания такой же длины, как контейнер не может содержать контейнер того же размера. Таким образом, машина включает в себя отдельный копировальный аппарат, который считывает ленту описания и передает копию на вновь построенную машину. Полученный в результате новый набор универсального конструктора и копировальных машин плюс лента с описанием идентичен старому, и он снова воспроизводится.
Система автоматов самовоспроизведения фон Неймана с возможностью развития (рисунок адаптирован из конспектов лекций Луиса Роча в Университете Индианы). i) самовоспроизводящаяся система состоит из нескольких автоматов плюс отдельное описание (кодировка, формализованная как «лента» Тьюринга ) всех автоматов: универсальный конструктор (A), универсальный копир (B), Операционная система (C), дополнительные функции, не связанные с репликацией (D), и отдельное описание Φ (A, B, C, D), кодирующее все автоматы. ii) (Вверху) Универсальный конструктор производит (декодирует) автоматы по их описанию (активный режим описания); (Внизу) Universal Copier копирует описание автоматов (пассивный режим описания); Мутации Φ (D ') в описание Φ (D) (а не изменения в автомате D напрямую) распространяются на множество автоматов, произведенных в следующем поколении, позволяя системе (автомат + описание) продолжать копирование и развитие (D → D'). Активный процесс построения из описания параллелен трансляции ДНК, пассивный процесс копирования описания параллелен репликации ДНК, а наследование мутировавших описаний параллелен Вертикальное наследование мутаций ДНК в биологии, и были предложены фон Нейманом до открытия структуры молекулы ДНК и того, как она отдельно транслируется и реплицируется в клетке. Дизайн фон Неймана традиционно понимался как демонстрация логической требования к самовоспроизведению машины. Однако ясно, что гораздо более простые машины могут достичь самовоспроизведения. Примеры включают тривиальный кристаллоподобный рост, репликацию шаблона и петли Лэнгтона. Но фон Нейман интересовался чем-то более глубоким: конструированием, универсальностью и эволюцией.
Обратите внимание, что более простые самовоспроизводящиеся структуры СА (особенно, петля Била и Чжоу– Цикл Reggia ) не может существовать в большом разнообразии форм и поэтому имеет очень ограниченную возможность развития. Другие структуры CA, такие как Evoloop, в некоторой степени эволюционируют, но все же не поддерживают неограниченное развитие. Обычно простые репликаторы не содержат полностью механизмы построения, поскольку репликатор представляет собой информацию, копируемую окружающей средой. Хотя дизайн фон Неймана является логической конструкцией, в принципе это проект, который может быть реализован как физическая машина. Действительно, этот универсальный конструктор можно рассматривать как абстрактное моделирование физического универсального ассемблера. Вопрос о вкладе окружающей среды в репликацию в некоторой степени открыт, поскольку существуют разные концепции сырья и его доступности.
Ключевой вывод фон Неймана состоит в том, что описание машины, которое копируется и передается потомкам отдельно через универсальный копировальный аппарат, имеет двойное назначение; одновременно являясь активным компонентом строительного механизма при воспроизведении и являясь целью процесса пассивного копирования. Эту роль играет описание (сродни ленте Тьюринга инструкций ) в комбинации универсального конструктора и универсального копировального аппарата фон Неймана. Комбинация универсального конструктора и копировального аппарата, плюс лента инструкций концептуализирует и формализует i) самовоспроизведение и ii) неограниченную эволюцию или рост сложности, наблюдаемый в биологических организмах.
Это понимание - все. тем более примечателен, что он предшествовал открытию структуры молекулы ДНК Уотсоном и Криком и того, как он отдельно транслируется и реплицируется в клетке, хотя он следовал Эксперимент Эйвери-Маклауда-Маккарти, который идентифицировал ДНК как молекулярный носитель генетической информации в живых организмах. Молекула ДНК обрабатывается отдельными механизмами, которые выполняют ее инструкции (трансляция ) и копируют (реплицировать ) ДНК для вновь сконструированных клеток. Возможность достижения неограниченной эволюции заключается в том, что, как и в природе, ошибки (мутации ) при копировании генетической ленты могут привести к появлению жизнеспособных вариантов автомата, которые затем могут развиваться через естественный отбор. Как выразился Бреннер:
Тьюринг изобрел компьютер с хранимой программой, а фон Нейман показал, что описание отделено от универсального конструктора. Это нетривиально. Физик Эрвин Шредингер перепутал программу и конструктор в своей книге 1944 года «Что такое жизнь?», В которой он рассматривал хромосомы как «замысел архитектора и ремесло строителя в одном». Это не правильно. Кодовый сценарий содержит только описание исполнительной функции, но не самой функции.
— Сидней БреннерЦель фон Неймана, как указано в его лекциях в Университете Иллинойса в 1949 году., заключалась в разработке машины, сложность которой могла бы расти автоматически, как биологические организмы при естественном отборе. Он спросил, каков порог сложности, который необходимо преодолеть, чтобы машины могли развиваться и усложняться. Его проекты «доказательства принципа» показали, насколько это возможно с логической точки зрения. Используя архитектуру, которая отделяет программируемый («универсальный») конструктор общего назначения от копировального устройства общего назначения, он показал, как описания (ленты) машин могут накапливать мутации в процессе самовоспроизведения и, таким образом, развивать более сложные машины (изображение ниже иллюстрирует эта возможность.). Это очень важный результат, так как до этого можно было предположить, что существует фундаментальный логический барьер для существования таких машин; в этом случае биологические организмы, которые эволюционируют и усложняются, не могут быть «машинами» в традиционном понимании. Идея фон Неймана заключалась в том, чтобы представить жизнь как машину Тьюринга, которая аналогичным образом определяется «головой» машины с определенным состоянием, отделенной от ленты памяти.
На практике, когда мы рассматриваем конкретную реализацию автомата Фон Нойманн, мы пришли к выводу, что он не дает большой эволюционной динамики, потому что машины слишком хрупкие - подавляющее большинство возмущений заставляет их эффективно разрушаться. Таким образом, именно концептуальная модель, изложенная в его лекциях в Иллинойсе, сегодня представляет больший интерес, потому что она показывает, как машина может в принципе развиваться. Это открытие тем более примечательно, что модель предшествовала открытию структуры молекулы ДНК, о которой говорилось выше. Также примечательно, что дизайн фон Неймана считает, что мутации в сторону большей сложности должны происходить в (описаниях) подсистем, не участвующих в самом самовоспроизведении, как это концептуализировано дополнительным автоматом D. (см. рисунок выше с системой автоматов самовоспроизведения фон Неймана, обладающей способностью к развитию.) Действительно, у биологических организмов наблюдались лишь очень незначительные вариации генетического кода, что соответствует логическому обоснованию фон Неймана, согласно которому универсальный конструктор (A) и Копир (B) сам по себе не будет развиваться, оставив всю эволюцию (и рост сложности) автомату D. В своей незаконченной работе фон Нейман также кратко рассматривает конфликты и взаимодействия между своими самовоспроизводящимися машинами, чтобы понять эволюцию экологических и социальных взаимодействия из его теории самовоспроизводящихся машин.
Демонстрация способности машины фон Неймана поддерживать наследуемые мутации. (1) На более раннем временном шаге мутация была вручную добавлена на ленту машины второго поколения. (2) Более поздние поколения демонстрируют фенотип мутации (рисунок цветка) и передают мутацию своим детям, поскольку лента каждый раз копируется. Этот пример показывает, как конструкция фон Неймана допускает рост сложности (теоретически), поскольку лента может указывать на машину, более сложную, чем та, которая ее производит. В теории автоматов концепция универсальный конструктор нетривиален из-за существования паттернов Garden of Eden. Но простое определение состоит в том, что универсальный конструктор способен построить любой конечный образец невозбужденных (неподвижных) ячеек.
Артур Бёркс и другие расширили работу фон Неймана, предоставив гораздо более ясный и полный набор деталей, касающихся конструкции и работы самовоспроизводителя фон Неймана. Особого внимания заслуживает работа Дж. У. Тэтчера, который значительно упростил конструкцию. Тем не менее, их работа не дала полной конструкции, ячейка за ячейкой, конфигурации, способной демонстрировать самовоспроизведение.
и Умберто Песавенто опубликовали первый полностью реализованный самовоспроизводящийся клеточный автомат в 1995 году, почти через пятьдесят лет после работы фон Неймана. Они использовали клеточный автомат с 32 состояниями вместо оригинальной спецификации с 29 состояниями фон Неймана, расширив ее, чтобы обеспечить более легкое пересечение сигналов, явную функцию памяти и более компактный дизайн. Они также опубликовали реализацию общего конструктора в исходном СА с 29 состояниями, но не способного к полной репликации - конфигурация не может дублировать свою ленту и не может запускать свое потомство; конфигурацию можно только построить.
В 2004 г. D. Mange et al. сообщил о реализации самовоспроизводящегося репликатора, который согласуется с разработкой фон Неймана.
В 2007 году Nobili опубликовал реализацию с 32 состояниями, в которой используется кодирование длин серий, чтобы значительно уменьшить размер ленты.
В 2008 году Уильям Р. Бакли опубликовал две конфигурации, которые являются саморепликаторами в исходной 29-штатной CA фон Неймана. Бакли утверждает, что пересечение сигнала внутри клеточных автоматов фон Неймана с 29 состояниями не является необходимым для построения саморепликаторов. Бакли также указывает, что для целей эволюции каждый репликатор должен вернуться к своей исходной конфигурации после репликации, чтобы иметь возможность (теоретически) создавать более одной копии. Как было опубликовано, дизайн Nobili-Pesavento 1995 года не соответствует этому требованию, но дизайн Nobili 2007 года выполняет; то же самое можно сказать и о конфигурациях Бакли.
В 2009 году Бакли вместе с Голли опубликовал третью конфигурацию для клеточных автоматов фон Неймана с 29 состояниями, которые могут выполнять либо целостную саморепликацию, либо саморепликацию путем частичного построения. Эта конфигурация также демонстрирует, что пересечение сигналов не является необходимым для построения саморепликаторов внутри клеточных автоматов фон Неймана с 29 состояниями.
С. Л. Неханив в 2002 г., а также Ю. Такада и соавт. в 2004 г. предложил универсальный конструктор, реализованный непосредственно на асинхронном клеточном автомате, а не на синхронном клеточном автомате.
| Реализация | Источник | Набор правил | Прямоугольная область | Количество ячеек | Длина ленты | Коэффициент | Период | Сжатие кода ленты | Длина кода ленты | Тип кода ленты | Механизм репликации | Тип репликации | Скорость роста |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Нобили-Песавенто, 1995 | Нобили с 32 состояниями | 97 × 170 | 6,329 | 145,315 | 22,96 | 6,34 × 10 | нет | 5 бит | двоичный | целостный конструктор | неповторяемый | линейный | |
| Nobili, 2007 | SR_CCN_AP.EVN | Nobili 32-state | 97 × 100 | 5,313 | 56,325 | 10,60 | 9,59 × 10 | кодирование с ограничением длины прогона | 5 биты | двоичный | целостный конструктор | повторяемый | суперлинейный |
| Buckley, 2008 | codon5.rle | Nobili с 32 состояниями | 112 × 50 | 3,343 | 44,155 | 13,21 | 5,87 x 10 | автооттягивание | 5 бит | двоичный | целостный конструктор | повторяемый | линейный |
| Бакли, 2008 | replicator.mc | 29-состояние фон Неймана | 312 × 132 | 18,589 | 294,844 | 15,86 | 2,61 × 10 | автоматический ретракт | 5 бит | двоичный | целостный конструктор | повторяемый | linear |
| Buckley, 2008 | codon4.rle | Nobili 32-state | 109 × 59 | 3,574 | 37,780 | 10,57 | 4,31 x 10 | автоотвод / генерация бит | 4 бита | двоичный | целостный конструктор | повторяемый | линейный |
| Buckley, 2009 | codon3.rle | Nobili с 32 состояниями | 116 × 95 | 4,855 | 23,577 | 4,86 | 1,63 x 10 | автоматическое удаление / генерация бит / наложение кода | 3 бита | двоичный | целостный конструктор | повторяемый | суперлинейный |
| Buckley, 2009 | PartialReplicator.mc | 29-состояние фон Неймана | 2063 × 377 | 264,321 | NA | - | ≈1,12 x 10 | нет | 4 бита | двоичный | частичный конструктор | повторяемый | линейный |
| Goucher Buckley, 2012 | phi9.rle | Nobili 32 -состояние | 122 × 60 | 3957 | 8920 | 2.25 | - | автоматический возврат / генерация битов / наложение кода / ограниченная длина прогона | 3+ бита | тройной | целостный конструктор | повторяемый | суперлинейный |
Как определено фон Нейманом, универсальная конструкция влечет за собой строительство только пассивных конфигураций. Таким образом, концепция универсального построения представляет собой не что иное, как литературный (или, в данном случае, математический) прием. Это способствовало другому доказательству, например, что хорошо сконструированная машина может участвовать в самовоспроизведении, в то время как сама универсальная конструкция просто предполагалась в самом минимальном случае. Универсальная конструкция по этому стандарту тривиальна. Следовательно, хотя все приведенные здесь конфигурации могут создать любую пассивную конфигурацию, ни одна из них не может создать пересекающий орган в реальном времени, разработанный Горманом.
Все реализации самого фон Неймана -воспроизводящая машина требует значительных ресурсов для работы на компьютере. Например, в реализации Nobili-Pesavento с 32 состояниями, показанной выше, в то время как корпус машины состоит всего из 6329 непустых ячеек (в пределах прямоугольника размером 97x170), для него требуется лента длиной 145 315 ячеек и занимает 63 миллиард временных шагов для воспроизведения. На создание первой копии симулятора, работающего со скоростью 1000 шагов в секунду, потребуется более 2 лет. В 1995 году, когда была опубликована первая реализация, авторы не видели репликации своей собственной машины. Однако в 2008 году алгоритм hashlife был расширен для поддержки наборов правил с 29 и 32 состояниями в Golly. На современном настольном ПК репликация теперь занимает всего несколько минут, хотя требуется значительный объем памяти.
Пример руки чтения с 29 состояниями.
