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

Джон фон Нейман «s универсальный конструктор является самовоспроизводящиеся машины в клеточных автоматов окружающей среды (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) (Вверху) Универсальный конструктор производит (декодирует) автоматы по их описанию ( активный режим описания); (Внизу) Универсальный копир копирует описание автоматов ( пассивныйрежим описания); Мутации Φ (D ') в описание Φ (D) (а не изменения в автомате D напрямую) распространяются на множество автоматов, произведенных в следующем поколении, позволяя системе (автомат + описание) продолжать воспроизводиться и развиваться (D → D'). [4] Активный процесс построения из описания параллелен трансляции ДНК , пассивный процесс копирования описания параллелен репликации ДНК , а наследование мутировавших описаний параллелен вертикальному наследованию мутаций ДНК в биологии, [4] [5] и был предложен Фон Нейман до открытия структуры молекулы ДНК и того, как она отдельно транслируется и реплицируется в клетке. [6]

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

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

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

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

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

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

Эволюция сложности [ править ]

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

На практике, когда мы рассматриваем конкретную реализацию автомата, которую преследовал фон Нейман, мы делаем вывод, что она не дает особой эволюционной динамики, потому что машины слишком хрупкие - подавляющее большинство возмущений заставляет их эффективно разрушаться. [3] Таким образом, именно концептуальная модель, изложенная в его лекциях в Иллинойсе [2] , представляет сегодня больший интерес, потому что она показывает, как машина может в принципе развиваться. [7] [4] Это открытие тем более примечательно, что модель предшествовала открытию структуры молекулы ДНК, как обсуждалось выше. [6]Также примечательно, что дизайн фон Неймана считает, что мутации в сторону большей сложности должны происходить в (описаниях) подсистем, не участвующих в самом самовоспроизведении, как это концептуализировано дополнительным автоматом D, который, как он считал, выполняет все функции, непосредственно не участвующие в воспроизводстве. (см. рисунок выше с системой автоматов самовоспроизведения фон Неймана, обладающей способностью к развитию.) Действительно, у биологических организмов наблюдались лишь очень незначительные вариации генетического кода, что соответствует логическому обоснованию фон Неймана, согласно которому универсальный конструктор ( A ) и Копир ( 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 состояниями.

CL Nehaniv в 2002 г., а также Y. Takada et al. в 2004 г. предложил универсальный конструктор, реализованный непосредственно на асинхронном клеточном автомате, а не на синхронном клеточном автомате.[12] [13]

Сравнение реализаций [ править ]

ВыполнениеИсточникНабор правилПрямоугольная областьКоличество ячеекДлина лентыСоотношениеПериодСжатие кода лентыДлина кода лентыТип кода лентыМеханизм репликацииТип репликацииСкорость роста
Нобили-Песавенто, 1995 [1][14]Нобили 32-гос.97 × 1706 329145 31522,966,34 × 10 10никто5 битдвоичныйцелостный конструкторнеповторимыйлинейный
Нобили, 2007 г.SR_CCN_AP.EVN [15]Нобили 32-гос.97 × 1005,31356 32510,609,59 × 10 9кодирование с ограничением длины прогона5 битдвоичныйцелостный конструкторповторяемыйсуперлинейный
Бакли, 2008 г.codon5.rle [16]Нобили 32-гос.112 × 503 34344 15513.215,87 х 10 9автоматический возврат5 битдвоичныйцелостный конструкторповторяемыйлинейный
Бакли, 2008 [9]replicator.mc [17]фон Неймана 29-состояние312 × 13218 589294 84415,862,61 × 10 11автоматический возврат5 битдвоичныйцелостный конструкторповторяемыйлинейный
Бакли, 2008 г.codon4.rle [16]Нобили 32-гос.109 × 593,57437 78010,574,31 х 10 9автоматическая ретракция / генерация бит4 битадвоичныйцелостный конструкторповторяемыйлинейный
Бакли, 2009 г.codon3.rleНобили 32-гос.116 × 95485523 5774,861,63 х 10 9автооттягивание / генерация бит / наложение кода3 битадвоичныйцелостный конструкторповторяемыйсуперлинейный
Бакли, 2009 г.PartialReplicator.mc [16]фон Неймана 29-состояние2063 × 377264 321NA-≈1,12 х 10 14никто4 битадвоичныйчастичный конструкторповторяемыйлинейный
Гушер и Бакли, 2012 г.phi9.rle [18]Нобили 32-гос.122 × 60395789202,25-автоматическое ретракция / генерация битов / наложение кода / ограничение длины прогона3+ биттройнойцелостный конструкторповторяемыйсуперлинейный

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

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

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

Галерея анимации [ править ]

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

См. Также [ править ]

  • Клеточный автомат Кодда
  • Петли Лэнгтона
  • Клеточные автоматы нобили
  • Quine , программа, которая производит себя на выходе
  • Машина Санта-Клауса
  • Wireworld

Ссылки [ править ]

  1. ^ a b c Песавенто, Умберто (1995), «Реализация самовоспроизводящейся машины фон Неймана» (PDF) , Artificial Life , MIT Press, 2 (4): 337–354, doi : 10.1162 / artl.1995.2.337 , PMID  8942052 , архивировано из оригинала (PDF) 21 июня 2007 г.
  2. ^ a b c d e фон Нейман, Джон; Беркс, Артур В. (1966),Теория самовоспроизводящихся автоматов. (Отсканированная книга онлайн) , University of Illinois Press , получено 28 февраля 2017 г.
  3. ^ Б с д е McMullin, B. (2000), "Джон фон Нейман и Эволюционный рост сложности: Looking Backwards, Глядя вперед ..." , Artificial Life , 6 (4): 347-361, DOI : 10,1162 / 106454600300103674 , PMID 11348586 
  4. ^ a b c d e f g h i j k l Роча, Луис М. (1998), "Избранная самоорганизация и семиотика эволюционных систем" , Evolutionary Systems , Springer, Dordrecht: 341–358
  5. ^ Б с д е е Бреннер, Сидней (2012), "код сценария Жизнь" , Nature , 482 : 461, DOI : 10.1038 / 482461a , PMID 22358811 
  6. ^ a b c d Роча, Луис М. (2015), «Глава 6. Фон Нейман и естественный отбор». (PDF) , Конспект лекций курса I-485-Biologic Inspired Computing, Университет Индианы (PDF)
  7. ^ Pattee, Говард, H. (1995), "Эволюция самореференция: символы материи, и смысловая замыкание" , Связь и Познание Искусственный интеллект , 12 (1-2): 9-27
  8. ^ a b Нобили, Ренато; Песавенто, Умберто (1996), «Обобщенные автоматы фон Неймана», в Besussi, E .; Чеккини А. (ред.), Proc. Искусственные миры и урбанистика, Конференция 1 (PDF) , Венеция: DAEST
  9. ^ Б с д е Buckley, William R. (2008), «Сигнал Crossing решения в Нейман самовоспроизводящихся клеточных автоматов», в Эндрю Адамацки ; Рамон Алонсо-Санс; Анна Лавничак; Хенаро Хуарес Мартинес; Кеничи Морита; Томас Уорш (ред.), Proc. Автоматы 2008 (PDF) , Luniver Press, стр. 453–503
  10. ^ Манге, Даниил; Stauffer, A .; Peparaolo, L .; Темпести, Г. (2004), «Макроскопический взгляд на самовоспроизведение», Протоколы IEEE , 92 (12): 1929–1945, DOI : 10.1109 / JPROC.2004.837631
  11. ^ "Архивная копия" . Архивировано из оригинала на 29 января 2011 года . Проверено 29 января 2011 года .CS1 maint: archived copy as title (link)
  12. ^ Неханив, Кристофер Л. (2002), «Самовоспроизведение в асинхронных клеточных автоматах», Конференция NASA / DoD 2002 года по эволюционируемому оборудованию (15-18 июля 2002, Александрия, Вирджиния, США) , IEEE Computer Society Press, стр. 201 –209
  13. ↑ Такада, Юске; Исокава, Тейджиро; Пепер, Фердинанд; Мацуи, Нобуюки (2004), «Универсальная конструкция самосинхронных клеточных автоматов», в Sloot, PMA (ed.), ACRI 2004, LNCS 3305 , стр. 21–30.
  14. ^ "Самовоспроизводящийся универсальный конструктор фон Неймана" .
  15. ^ Клеточные автоматы Джона фон Неймана [1]
  16. ^ а б в andykt. «Боже, симулятор игры в жизнь» . SourceForge .
  17. ^ [2]
  18. ^ «Самовоспроизведение» . Комплексное проективное 4-пространство .

Внешние ссылки [ править ]

  • Golly - ускоритель моделирования сотовых автоматов. Очень быстрая реализация перехода между состояниями и поддержка JvN, GoL, Wolfram и других систем.
  • Самовоспроизводящийся универсальный конструктор фон Неймана . Оригинальный исходный код Нобили-Песавенто, анимации и файлы Голли репликаторов.
  • Джон фон Нейман 29 состояние клеточных автоматов Реализовано в OpenLaszlo на Дон Хопкинс
  • Каталог самовоспроизводящихся клеточных автоматов. Этот каталог дополняет Proc. Автоматы 2008 г. Том.