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

Универсальный конструктор Джона фон Неймана — это самовоспроизводящаяся машина в среде клеточного автомата (КА). Она была разработана в 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 (особенно петля Байла и петля Чжоу-Реджиа ) не могут существовать в широком разнообразии форм и, таким образом, имеют очень ограниченную способность к развитию . Другие структуры CA, такие как Evoloop, в некоторой степени способны к развитию, но все же не поддерживают открытую эволюцию. Обычно простые репликаторы не полностью содержат механизмы построения, поскольку существует степень, в которой репликатор является информацией, скопированной его окружающей средой. Хотя конструкция фон Неймана является логической конструкцией, в принципе это конструкция, которая может быть реализована как физическая машина. Действительно, этот универсальный конструктор можно рассматривать как абстрактную симуляцию физического универсального ассемблера . Вопрос о вкладе окружающей среды в репликацию является несколько открытым, поскольку существуют различные концепции сырья и его доступности.

Ключевое понимание фон Неймана заключается в том, что описание машины, которая копируется и передается потомству отдельно через универсальный копировальный аппарат, имеет двойное применение: будучи и активным компонентом строительного механизма в воспроизводстве, и целью пассивного процесса копирования. Эту роль играет описание (сродни ленте инструкций Тьюринга ) в комбинации фон Неймана универсального конструктора и универсального копировального аппарата. [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-стабильной спецификации фон Неймана , расширив ее для обеспечения более легкого пересечения сигналов, явной функции памяти и более компактной конструкции. Они также опубликовали реализацию общего конструктора в рамках оригинального 29-стабильного CA, но не способного к полной репликации — конфигурация не может дублировать свою ленту и не может запускать свое потомство; конфигурация может только конструировать. [8] [9]

В 2004 году Д. Манге и др. сообщили о реализации саморепликатора, соответствующего проектам фон Неймана. [10]

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

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

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

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

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

ВыполнениеИсточникНабор правилПрямоугольная областьКоличество ячеекДлина лентыСоотношениеПериодСжатие ленточного кодаДлина кода лентыТип кода лентыМеханизм репликацииТип репликацииТемпы роста
Нобили-Песавенто, 1995 [1]. [1]Нобили 32-штатный97 × 1706,329145,31522.966,34 × 10 10никто5 битдвоичныйЦелостный конструкторнеповторимыйлинейный
Нобили, 2007SR_CCN_AP.EVN [11]Нобили 32-штатный97 × 1005,31356,32510.609,59 × 10 9кодирование с ограниченной длиной отрезка5 битдвоичныйЦелостный конструкторповторяемыйсуперлинейный
Бакли, 2008 г.кодон5.rle [14]Нобили 32-штатный112 × 503,34344,15513.215,87 × 10 9авто-ретракция5 битдвоичныйЦелостный конструкторповторяемыйлинейный
Бакли, 2008 [9]репликатор.mcфон Нейман 29-состояние312 × 13218,589294,84415.862,61 × 10 11авто-ретракция5 битдвоичныйЦелостный конструкторповторяемыйлинейный
Бакли, 2008 г.кодон4.rle [14]Нобили 32-штатный109 × 593,57437,78010.574,31 × 10 9
  • авто-ретракция
  • генерация бит
4 битадвоичныйЦелостный конструкторповторяемыйлинейный
Бакли, 2009кодон3.rleНобили 32-штатный116 × 954,85523,5774.861,63 × 10 9
  • авто-ретракция
  • генерация бит
  • наложение кода
3 битадвоичныйЦелостный конструкторповторяемыйсуперлинейный
Бакли, 2009ЧастичныйРепликатор.mc [14]фон Нейман 29-состояние2063 × 377264,321——≈1,12 × 10 14никто4 битадвоичныйЧастичный конструкторповторяемыйлинейный
Гуше и Бакли, 2012phi9.rle [15]Нобили 32-штатный122 × 60395789202.25—
  • авто-ретракция
  • генерация бит
  • наложение кода
  • длина пробега ограничена
3+ битатроичныйЦелостный конструкторповторяемыйсуперлинейный

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

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

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

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

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

Ссылки

  1. ^ abcd Песавенто, Умберто (1995), «Реализация самовоспроизводящейся машины фон Неймана» (PDF) , Искусственная жизнь , 2 (4), MIT Press: 337–354, doi :10.1162/artl.1995.2.337, PMID  8942052, архивировано из оригинала (PDF) 21 июня 2007 г.
  2. ^ abcde фон Нейман, Джон; Беркс, Артур У. (1966), Теория самовоспроизводящихся автоматов. (Отсканированная книга онлайн) , University of Illinois Press , получено 28.02.2017
  3. ^ abcde Макмаллин, Б. (2000), «Джон фон Нейман и эволюционный рост сложности: взгляд назад, взгляд вперед...» , Искусственная жизнь , 6 (4): 347–361, doi :10.1162/106454600300103674, PMID  11348586, S2CID  5454783
  4. ^ abcdefghijkl Роча, Луис М. (1998), «Избранная самоорганизация и семиотика эволюционных систем», Evolutionary Systems , Springer, Дордрехт, стр. 341–358, doi :10.1007/978-94-017-1510-2_25, ISBN 978-90-481-5103-5
  5. ^ abcdef Бреннер, Сидней (2012), «Скрипт кода жизни» , Nature , 482 (7386): 461, doi : 10.1038/482461a, PMID  22358811, S2CID  205070101
  6. ^ abcd Роча, Луис М. (2015), «Глава 6. Фон Нейман и естественный отбор», Конспект лекций курса SSIE-583-Биологически вдохновленные вычисления и эволюционные системы, Университет Бингемтона
  7. ^ Патти, Ховард, Х. (2012), «Развивающаяся самореференция: материя, символы и семантическая замкнутость», ЗАКОНЫ, ЯЗЫК и ЖИЗНЬ , Биосемиотика, т. 12, стр. 9–27, doi :10.1007/978-94-007-5161-3_14, ISBN 978-94-007-5160-6{{citation}}: CS1 maint: несколько имен: список авторов ( ссылка )
  8. ^ аб Нобили, Ренато; Песавенто, Умберто (1996), «Обобщенные автоматы фон Неймана», в Бесусси, Э.; Чеккини, А. (ред.), Proc. Искусственные миры и городские исследования, Конференция 1 (PDF) , Венеция: DAEST
  9. ^ abcde Buckley, William R. (2008), «Решения по пересечению сигналов в самовоспроизводящихся клеточных автоматах фон Неймана», в Andrew Adamatzky ; Ramon Alonso-Sanz; Anna Lawniczak ; Genaro Juarez Martinez; Kenichi Morita; Thomas Worsch (ред.), Proc. Automata 2008 (PDF) , Luniver Press, стр. 453–503
  10. ^ Манге, Даниэль; Штауффер, А.; Пепараоло, Л.; Темпести, Г. (2004), «Макроскопический взгляд на саморепликацию», Труды IEEE , 92 (12): 1929–1945, doi :10.1109/JPROC.2004.837631, S2CID  22500865
  11. ^ ab Nobili, Renato (2007). "Клеточные автоматы Джона фон Неймана". Архивировано из оригинала 29 января 2011 г. Получено 29 января 2011 г.
  12. ^ Неханив, Кристофер Л. (2002), «Самовоспроизведение в асинхронных клеточных автоматах», Конференция NASA/DoD 2002 по эволюционируемому оборудованию (15–18 июля 2002 г., Александрия, Вирджиния, США) , IEEE Computer Society Press, стр. 201–209
  13. ^ Такада, Юске; Исокава, Тейджиро; Пепер, Фердинанд; Мацуи, Нобуюки (2004), «Универсальная конструкция самосинхронных клеточных автоматов», в Slot, PMA (ред.), ACRI 2004, LNCS 3305 , стр. 21–30.
  14. ^ abc andykt (18 июля 2023 г.). "Golly, симулятор игры "Жизнь"". SourceForge .
  15. ^ "Саморепликация". Комплексное проективное 4-пространство . 12 ноября 2012 г.
  • 29-стабильный клеточный автомат Джона фон Неймана, реализованный в OpenLaszlo Доном Хопкинсом
Взято с "https://en.wikipedia.org/w/index.php?title=Von_Neumann_universal_constructor&oldid=1227033638"