Универсальный конструктор фон Неймана
фон Неймана Джона Универсальный конструктор — это самовоспроизводящаяся машина в среде клеточного автомата (КА). Он был разработан в 1940-х годах без использования компьютера. Фундаментальные детали машины были опубликованы в книге фон Неймана «Теория самовоспроизводящихся автоматов» , завершенной в 1966 году Артуром Берксом после смерти фон Неймана. [2] Он считается основополагающим для теории автоматов , сложных систем и искусственной жизни . [3] [4] Действительно, нобелевский лауреат Сидни Бреннер считал работу фон Неймана о самовоспроизводящихся автоматах (вместе с работой Тьюринга о вычислительных машинах) центральной и для биологической теории , позволяющей нам «дисциплинировать наши мысли о машинах, как естественных, так и искусственных». [5]
Цель фон Неймана, изложенная в его лекциях в Университете Иллинойса в 1949 году, заключалась в следующем: [2] заключалась в разработке машины, сложность которой могла бы автоматически возрастать, подобно биологическим организмам в условиях естественного отбора . Он спросил, какой порог сложности необходимо преодолеть, чтобы машины смогли развиваться. [4] Его ответ заключался в том, чтобы указать абстрактную машину, которая при запуске будет копировать себя. В его конструкции самовоспроизводящаяся машина состоит из трех частей: «описания» самого себя («чертежа» или программы), универсального механизма-конструктора , который может прочитать любое описание и построить машину (без описания), закодированную в этом описании. и универсальный копировальный аппарат , способный делать копии любого описания. После того, как универсальный конструктор был использован для создания новой машины, закодированной в описании, копирующая машина используется для создания копии этого описания, и эта копия передается новой машине, что приводит к рабочей репликации исходной машины. который может продолжать воспроизводиться. Некоторые машины делают это задом наперед, копируя описание и затем собирая машину. Важно отметить, что самовоспроизводящаяся машина может развиваться, накапливая мутации описания, а не самой машины, приобретая таким образом способность усложняться. [4] [5]
Чтобы более подробно определить свою машину, фон Нейман изобрел концепцию клеточного автомата . Тот , который он использовал, состоит из двумерной сетки ячеек, каждая из которых может находиться в одном из 29 состояний в любой момент времени. На каждом временном шаге каждая ячейка обновляет свое состояние в зависимости от состояний окружающих ячеек на предыдущем временном шаге. Правила, управляющие этими обновлениями, одинаковы для всех ячеек.
Универсальный конструктор — это некая закономерность состояний ячеек в этом клеточном автомате. Он содержит одну строку ячеек, которые служат описанием (аналогично ленте Тьюринга ), кодируя последовательность инструкций, которые служат «чертежом» для машины. Машина считывает эти инструкции одну за другой и выполняет соответствующие действия. Инструкции предписывают машине использовать свою «конструкторскую руку» (еще один автомат, который функционирует как операционная система). [4] ), чтобы построить копию машины без ленты описания в другом месте сетки ячеек. Описание не может содержать инструкции по созданию ленты описания одинаковой длины, так же как контейнер не может содержать контейнер того же размера. Следовательно, машина включает в себя отдельный копировальный аппарат, который считывает ленту с описанием и передает копию вновь построенному аппарату. Получающийся в результате новый набор универсального конструктора и копировальных машин плюс лента с описанием идентичен старому и снова приступает к воспроизведению.
Цель [ править ]
Проект фон Неймана традиционно воспринимался как демонстрация логических требований к самовоспроизводству машин. [3] Однако ясно, что гораздо более простые машины могут добиться самовоспроизведения. Примеры включают тривиальный кристаллоподобный рост , репликацию шаблона и петли Лэнгтона . Но фон Неймана интересовало нечто более глубокое: конструкция, универсальность и эволюция. [4] [5]
Обратите внимание, что более простые самовоспроизводящиеся структуры СА (особенно петля Била и петля Чжоу-Реджиа ) не могут существовать в широком разнообразии форм и, следовательно, имеют очень ограниченную возможность развития . Другие структуры 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
Реализации [ править ]
В теории автоматов концепция универсального конструктора нетривиальна из-за существования шаблонов Эдемского сада (конфигураций, не имеющих предшественников). Но простое определение состоит в том, что универсальный конструктор способен построить любую конечную структуру невозбужденных (покоящихся) ячеек.
Артур Бёркс и другие расширили работу фон Неймана, предоставив гораздо более ясный и полный набор деталей, касающихся конструкции и работы самовоспроизводящего устройства фон Неймана. Особого внимания заслуживает работа Дж. У. Тэтчера, поскольку он значительно упростил конструкцию. Тем не менее, их работа не привела к полной разработке, ячейка за ячейкой, конфигурации, способной демонстрировать самовоспроизведение.
Ренато Нобили и Умберто Песавенто опубликовали первый полностью реализованный самовоспроизводящийся клеточный автомат в 1995 году, почти через пятьдесят лет после работы фон Неймана. [1] [8] Они использовали клеточный автомат с 32 состояниями вместо исходной спецификации фон Неймана с 29 состояниями , расширив ее, чтобы обеспечить более легкое пересечение сигналов, явную функцию памяти и более компактную конструкцию. Они также опубликовали реализацию общего конструктора в исходном ЦС с 29 состояниями, но не способного к полной репликации - конфигурация не может дублировать свою ленту и не может запускать свое потомство; конфигурацию можно только построить. [8] [9]
В 2004 г. Д. Манге и др. сообщил о реализации самовоспроизводящего устройства, соответствующего разработкам фон Неймана. [10]
В 2007 году Nobili опубликовал реализацию с 32 состояниями, в которой используется кодирование по длинам серий, чтобы значительно уменьшить размер ленты. [11]
В 2008 году Уильям Р. Бакли опубликовал две конфигурации, которые являются самовоспроизводящимися в исходном СА фон Неймана с 29 состояниями. [9] Бакли утверждает, что пересечение сигнала внутри клеточных автоматов фон Неймана с 29 состояниями не является необходимым для построения саморепликаторов. [9] Бакли также указывает, что для целей эволюции каждый репликатор должен вернуться к своей исходной конфигурации после репликации, чтобы иметь возможность (теоретически) создать более одной копии. В опубликованном виде дизайн Nobili-Pesavento 1995 года не соответствует этому требованию, но дизайн Nobili 2007 года соответствует; то же самое относится и к конфигурациям Бакли.
опубликовал В 2009 году Бакли вместе с Голли третью конфигурацию клеточных автоматов фон Неймана с 29 состояниями, которые могут выполнять либо целостное самовоспроизведение, либо самовоспроизведение путем частичного построения. Эта конфигурация также демонстрирует, что пересечение сигналов не является необходимым для построения саморепликаторов в клеточных автоматах фон Неймана с 29 состояниями.
CL Nehaniv в 2002 г., а также Y. Takada et al. в 2004 году предложил универсальный конструктор, реализуемый непосредственно на асинхронном клеточном автомате, а не на синхронном клеточном автомате. [12] [13]
Сравнение реализаций [ править ]
| Выполнение | Источник | Набор правил | Прямоугольная область | Количество ячеек | Длина ленты | Соотношение | Период | Сжатие кода ленты | Длина кода ленты | Тип кода ленты | Механизм репликации | Тип репликации | Темпы роста |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Нобили-Песавенто, 1995 г. [1] | . [1] | 32 государства дворян | 97 × 170 | 6,329 | 145,315 | 22.96 | 6.34 × 10 10 | никто | 5 бит | двоичный | Целостный конструктор | неповторяемый | линейный |
| Нобили, 2007 г. | SR_CCN_AP.EVN [11] | 32 государства дворян | 97 × 100 | 5,313 | 56,325 | 10.60 | 9.59 × 10 9 | кодирование с ограниченной длиной серии | 5 бит | двоичный | Целостный конструктор | повторяемый | суперлинейный |
| Бакли, 2008 г. | кодон5.rle [14] | 32 государства дворян | 112 × 50 | 3,343 | 44,155 | 13.21 | 5.87 × 10 9 | автоматическое втягивание | 5 бит | двоичный | Целостный конструктор | повторяемый | линейный |
| Бакли, 2008 г. [9] | replicator.mc | фон Неймана 29 государств | 312 × 132 | 18,589 | 294,844 | 15.86 | 2.61 × 10 11 | автоматическое втягивание | 5 бит | двоичный | Целостный конструктор | повторяемый | линейный |
| Бакли, 2008 г. | кодон4.rle [14] | 32 государства дворян | 109 × 59 | 3,574 | 37,780 | 10.57 | 4.31 × 10 9 |
| 4 бита | двоичный | Целостный конструктор | повторяемый | линейный |
| Бакли, 2009 г. | кодон3.rle | 32 государства дворян | 116 × 95 | 4,855 | 23,577 | 4.86 | 1.63 × 10 9 |
| 3 бита | двоичный | Целостный конструктор | повторяемый | суперлинейный |
| Бакли, 2009 г. | PartialReplicator.mc [14] | фон Неймана 29 государств | 2063 × 377 | 264,321 | — | — | ≈ 1.12 × 10 14 | никто | 4 бита | двоичный | Частичный конструктор | повторяемый | линейный |
| Гучер и Бакли, 2012 г. | phi9.rle [15] | 32 государства дворян | 122 × 60 | 3957 | 8920 | 2.25 | — |
| 3+ бита | тройной | Целостный конструктор | повторяемый | суперлинейный |
По определению фон Неймана, универсальное построение предполагает построение только пассивных конфигураций. По сути, концепция универсальной конструкции представляла собой не что иное, как литературный (или, в данном случае, математический) прием. Это облегчило другие доказательства, например, что хорошо сконструированная машина может заниматься самовоспроизведением, в то время как сама универсальная конструкция просто предполагалась в самом минимальном случае. Универсальная конструкция по этому стандарту тривиальна. Следовательно, хотя все приведенные здесь конфигурации могут создать любую пассивную конфигурацию, ни одна из них не может создать орган пересечения в реальном времени, разработанный Горманом. [9]
и вычислительные затраты Практичность
Все реализации самовоспроизводящейся машины фон Неймана требуют значительных ресурсов для запуска на компьютере. Например, в реализации с 32 состояниями Нобили-Песавенто, показанной выше, хотя тело машины состоит всего из 6329 непустых ячеек (внутри прямоугольника размером 97x170), для нее требуется лента длиной 145 315 ячеек, занимающая 63 ячейки. миллиард временных шагов для репликации. Симулятору, работающему со скоростью 1000 тактов в секунду, потребуется более 2 лет, чтобы сделать первую копию. В 1995 году, когда была опубликована первая реализация, авторы не видели реплики своей собственной машины. Однако в 2008 году алгоритм hashlife был расширен для поддержки наборов правил с 29 и 32 состояниями в Golly . На современном настольном ПК репликация теперь занимает всего несколько минут, хотя для этого требуется значительный объем памяти.
Галерея анимации [ править ]
Пример руки чтения с 29 состояниями.
См. также [ править ]
- клеточный автомат Кодда
- петли Лэнгтона
- Клеточные автоматы Нобили
- Quine — программа, которая производит себя на выходе
- Машина Деда Мороза
- Проводной мир
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с д Песавенто, Умберто (1995), «Реализация самовоспроизводящейся машины фон Неймана» (PDF) , Искусственная жизнь , 2 (4), MIT Press: 337–354, doi : 10.1162/artl.1995.2.337 , PMID 8942052 , заархивировано из оригинала (PDF) 21 июня 2007 г.
- ↑ Перейти обратно: Перейти обратно: а б с д и фон Нейман, Джон; Беркс, Артур В. (1966), Теория самовоспроизводящихся автоматов. (Отсканированная книга онлайн) , University of Illinois Press , получено 28 февраля 2017 г.
- ↑ Перейти обратно: Перейти обратно: а б с д и Макмаллин, Б. (2000), «Джон фон Нейман и эволюционный рост сложности: взгляд назад, взгляд вперед...» , «Искусственная жизнь » , 6 (4): 347–361, doi : 10.1162/106454600300103674 , PMID 11348586 , S2CID 5454783
- ↑ Перейти обратно: Перейти обратно: а б с д и ж г час я дж к л Роша, Луис М. (1998), «Избранная самоорганизация и семиотика эволюционных систем», Evolutionary Systems , Springer, Dordrecht, стр. 341–358, doi : 10.1007/978-94-017-1510-2_25 , ISBN 978-90-481-5103-5
- ↑ Перейти обратно: Перейти обратно: а б с д и ж Бреннер, Сидней (2012), «Сценарий кода жизни» , Nature , 482 (7386): 461, doi : 10.1038/482461a , PMID 22358811 , S2CID 205070101
- ↑ Перейти обратно: Перейти обратно: а б с д Роча, Луис М. (2015), «Глава 6. Фон Нейман и естественный отбор». , Конспект лекций SSIE-583-Курс биологических вычислений и эволюционных систем, Бингемтонский университет
- ^ Патти, Ховард, Х. (2012), «Развивающаяся самореференция: материя, символы и семантическое замыкание» , ЗАКОНЫ, ЯЗЫК и ЖИЗНЬ , Биосемиотика, том. 12, стр. 9–27, номер документа : 10.1007/978-94-007-5161-3_14 , ISBN. 978-94-007-5160-6
{{citation}}: CS1 maint: несколько имен: список авторов ( ссылка ) - ↑ Перейти обратно: Перейти обратно: а б Нобили, Ренато; Песавенто, Умберто (1996), «Обобщенные автоматы фон Неймана», в Бесусси, Э.; Чеккини, А. (ред.), Proc. Искусственные миры и городские исследования, Конференция 1 (PDF) , Венеция: DAEST
- ↑ Перейти обратно: Перейти обратно: а б с д и Бакли, Уильям Р. (2008), «Решения для пересечения сигналов в самовоспроизводящихся клеточных автоматах фон Неймана», Эндрю Адамацки ; Рамон Алонсо-Санс; Анна Лавничак ; Хенаро Хуарес Мартинес; Кеничи Морита; Томас Ворш (ред.), Proc. Автоматы 2008 (PDF) , Лунивер Пресс, стр. 453–503.
- ^ Манге, Дэниел; Стауффер, А.; Пепараоло, Л.; Темпести, Г. (2004), «Макроскопический взгляд на самовоспроизведение», Proceedings of the IEEE , 92 (12): 1929–1945, doi : 10.1109/JPROC.2004.837631 , S2CID 22500865
- ↑ Перейти обратно: Перейти обратно: а б Нобили, Ренато (2007). «Клеточные автоматы Джона фон Неймана» . Архивировано из оригинала 29 января 2011 года . Проверено 29 января 2011 г.
- ^ Неханив, Кристофер Л. (2002), «Самовоспроизведение в асинхронных клеточных автоматах», Конференция NASA/DoD 2002 г. по развивающемуся аппаратному обеспечению (15–18 июля 2002 г., Александрия, Вирджиния, США) , IEEE Computer Society Press, стр. 201– 209
- ^ Такада, Юске; Исокава, Тейджиро; Пепер, Фердинанд; Мацуи, Нобуюки (2004), «Универсальная конструкция самосинхронных клеточных автоматов», в Slot, PMA (ред.), ACRI 2004, LNCS 3305 , стр. 21–30.
- ↑ Перейти обратно: Перейти обратно: а б с Андыкт (18 июля 2023 г.). «Боже мой, симулятор игры жизни» . СоурсФордж .
- ^ «Самовоспроизведение» . Комплексное проективное 4-пространство . 12 ноября 2012 г.