Оглавление
- 1 Универсальный конструктор Фон Неймана
- 1.1 Универсальный конструктор Джона фон Неймана
- 1.2 Цель и структура машины
- 1.3 Клеточный автомат
- 1.4 Эволюция и сложность
- 1.5 Влияние на биологию
- 1.6 Практические реализации
- 1.7 Наследие и развитие
- 1.8 История самовоспроизводящихся клеточных автоматов
- 1.9 Современные реализации
- 1.10 Универсальная конструкция
- 1.11 Практичность и вычислительные затраты
- 1.12 Полный текст статьи:
- 2 Универсальный конструктор фон Неймана
Универсальный конструктор Фон Неймана
-
Универсальный конструктор Джона фон Неймана
- Разработан в 1940-х годах без использования компьютера
- Опубликован в книге “Теория самовоспроизводящихся автоматов” в 1966 году
- Считается основополагающей для теории автоматов и искусственной жизни
-
Цель и структура машины
- Цель: спроектировать машину, сложность которой может возрастать подобно биологическим организмам
- Состоит из описания, универсального конструктора и копировального аппарата
- Описание копируется и передается потомкам, что позволяет машине эволюционировать
-
Клеточный автомат
- Двумерная сетка ячеек, каждая из которых может находиться в одном из 29 состояний
- Универсальный конструктор содержит описание, кодирующее последовательность инструкций
- Машина считывает инструкции и создает копию без ленты с описанием
-
Эволюция и сложность
- Описание машины имеет двойное назначение: активный компонент и объект копирования
- Ошибки при копировании могут привести к созданию жизнеспособных вариантов автомата
- Фон Нейман показал, что машины могут эволюционировать, накапливая мутации
-
Влияние на биологию
- Фон Нейман предвосхитил открытие структуры ДНК и ее роли в эволюции
- ДНК обрабатывается отдельными механизмами для трансляции и репликации
- Ошибки при копировании ДНК могут привести к созданию жизнеспособных вариантов
-
Практические реализации
- Конкретные реализации автоматов не дают большой эволюционной динамики
- Концептуальная модель фон Неймана показывает, как машина может эволюционировать
- Изменения в сторону большей сложности происходят в подсистемах, не участвующих в самовоспроизводстве
-
Наследие и развитие
- Артур Беркс и другие продолжили работу фон Неймана
- Дж. W. Тэтчер упростил дизайн универсального конструктора
-
История самовоспроизводящихся клеточных автоматов
- Ренато Нобили и Умберто Песавенто опубликовали первый полностью реализованный самовоспроизводящийся клеточный автомат в 1995 году.
- Они использовали клеточный автомат с 32 состояниями вместо 29 состояний фон Неймана.
- В 2004 году Д. Мэнж и др. сообщили о реализации самовоспроизводящегося устройства, согласующегося с разработками фон Неймана.
-
Современные реализации
- В 2007 году Nobili опубликовала реализацию с 32 состояниями, использующую кодирование по длине цикла.
- В 2008 году Уильям Р. Бакли опубликовал две конфигурации, которые являются саморепликаторами в исходном CA фон Неймана с 29 состояниями.
- В 2009 году Бакли совместно с Голли опубликовал третью конфигурацию, демонстрирующую, что пересечение сигналов не является необходимым для построения саморепликаторов.
-
Универсальная конструкция
- C. L. Неханив и Ю. Такада предложили универсальный конструктор, реализованный на асинхронном клеточном автомате.
- Универсальная конструкция подразумевает создание только пассивных конфигураций и не может создать орган пересечения в реальном времени.
-
Практичность и вычислительные затраты
- Все реализации самовоспроизводящейся машины фон Неймана требуют значительных ресурсов для запуска на компьютере.
- В 1995 году авторы не видели, как их машина воспроизводилась, но в 2008 году алгоритм hashlife был расширен для поддержки наборов правил из 29 и 32 штатов.
- На современном настольном ПК репликация занимает всего несколько минут, хотя и требует значительного объема памяти.