Универсальный конструктор Джона фон Неймана — это самовоспроизводящаяся машина в среде клеточного автомата (КА). Он был разработан в 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 ) и Copier ( B ) сами не будут развиваться, оставив всю эволюцию (и рост сложности) автомату D . [4] В своей незаконченной работе фон Нейман также кратко рассматривает конфликты и взаимодействия между своими самовоспроизводящимися машинами, чтобы понять эволюцию экологических и социальных взаимодействий на основе своей теории самовоспроизводящихся машин. [2] : 147
В теории автоматов концепция универсального конструктора нетривиальна из-за существования шаблонов Эдемского сада (конфигураций, не имеющих предшественников). Но простое определение состоит в том, что универсальный конструктор способен построить любую конечную структуру невозбужденных (покоящихся) ячеек.
Arthur Burks and others extended the work of von Neumann, giving a much clearer and complete set of details regarding the design and operation of von Neumann's self-replicator. The work of J. W. Thatcher is particularly noteworthy, for he greatly simplified the design. Still, their work did not yield a complete design, cell by cell, of a configuration capable of demonstrating self-replication.
Renato Nobili and Umberto Pesavento published the first fully implemented self-reproducing cellular automaton in 1995, nearly fifty years after von Neumann's work.[1][8] They used a 32-state cellular automaton instead of von Neumann's original 29-state specification, extending it to allow for easier signal-crossing, explicit memory function and a more compact design. They also published an implementation of a general constructor within the original 29-state CA but not one capable of complete replication - the configuration cannot duplicate its tape, nor can it trigger its offspring; the configuration can only construct.[8][9]
In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.[10]
In 2007, Nobili published a 32-state implementation that uses run-length encoding to greatly reduce the size of the tape.[11]
In 2008, William R. Buckley published two configurations which are self-replicators within the original 29-state CA of von Neumann.[9] Buckley claims that the crossing of signal within von Neumann 29-state cellular automata is not necessary to the construction of self-replicators.[9] Buckley also points out that for the purposes of evolution, each replicator should return to its original configuration after replicating, in order to be capable (in theory) of making more than one copy. As published, the 1995 design of Nobili-Pesavento does not fulfill this requirement but the 2007 design of Nobili does; the same is true of Buckley's configurations.
In 2009, Buckley published with Golly a third configuration for von Neumann 29-state cellular automata, which can perform either holistic self-replication, or self-replication by partial construction. This configuration also demonstrates that signal crossing is not necessary to the construction of self-replicators within von Neumann 29-state cellular automata.
C. L. Nehaniv in 2002, and also Y. Takada et al. in 2004, proposed a universal constructor directly implemented upon an asynchronous cellular automaton, rather than upon a synchronous cellular automaton.[12][13]
As defined by von Neumann, universal construction entails the construction of passive configurations, only. As such, the concept of universal construction constituted nothing more than a literary (or, in this case, mathematical) device. It facilitated other proof, such as that a machine well constructed may engage in self-replication, while universal construction itself was simply assumed over a most minimal case. Universal construction under this standard is trivial. Hence, while all the configurations given here can construct any passive configuration, none can construct the real-time crossing organ devised by Gorman.[9]
All the implementations of von Neumann's self-reproducing machine require considerable resources to run on computer. For example, in the Nobili-Pesavento 32-state implementation shown above, while the body of the machine is just 6,329 non-empty cells (within a rectangle of size 97x170), it requires a tape that is 145,315 cells long, and takes 63 billion timesteps to replicate. A simulator running at 1,000 timesteps per second would take over 2 years to make the first copy. In 1995, when the first implementation was published, the authors had not seen their own machine replicate. However, in 2008, the hashlife algorithm was extended to support the 29-state and 32-state rulesets in Golly. On a modern desktop PC, replication now takes only a few minutes, although a significant amount of memory is required.
{{citation}}: CS1 maint: multiple names: authors list (link)