АВТОМАТ САМОВОСПРОИЗВОДЯЩИЙСЯ

— автомат, который в процессе функционирования строит свою копию. Исследования по теории самовоспроизведения автоматов впервые предпринял Дж. фон Нейман, объяснивший следующим образом приведенное определение. Пусть задан автономный конечный автомат А и некоторый набор Q конечных автоматов (элементов). Если выходные сигналы автомата А удается интерпретировать как указания, какой из элементов набора Q надо взять и к каким элементам из уже имеющегося соединения элементов его присоединить, то последовательность выходных сигналов автомата А можно рассматривать как процесс построения некоторого соединения элементов. Пусть среди выходных сигналов автомата А имеется сигнал, который интерпретируется как «построение закончено». В этом случае автомат А за некоторое конечное число шагов «строит» некоторую логическую сеть L над Q. Пусть эта сеть реализует автомат В, тогда говорят, что А в процессе функционирования строит автомат В. Автомат В наз. «потомком» А, а автомат

А — «родителем» автомата В. Следуя принятой терминологии, будем говорить, что автомат А построен в П, если он реализован в некоторой логической сети над Q. Если бы элементы набора Q были выполнены в виде реальных физ. устройств и автомат А был снабжен исполнительными органами, позволяющими ему выбирать нужные элементы и делать нужные соединения, и автомату А дать достаточное к-во элементов, то он мог бы в действительности построить некоторое устр-во в виде соединения элементов.

Рассмотрим такой набор элементов Q, когда «родитель» любого автомата, построенного в Q, сам может быть построен в Q. Можно предположить, что для любого автомата А его «родитель» — должен быть в некотором смысле более сложным, чем А, т. к. р (А) должен обладать всей информацией о структуре автомата А. Необходимо найти такой А, что т. е. автомат, который строит свою копию (автомат А в этом случае наз. самовоспроизводящимся). При этом представляет интерес не всякое самовоспроизведение автоматов, а самовоспроизведение автоматов, имеющих достаточно сложное строение. Заметим, что если А является А. с., то порожденные им автоматы также будут строить автоматы А, причем их «потомки» будут не только функционально, но и структурно эквивалентны «родителям», т. е. будут совпадать логические сети, реализующие «родителей» и «потомков».

Дж. фон Нейман рассматривал две модели самовоспроизведения. В первой, т. н. кинематической модели, автомат А «плавал» в резервуаре, в котором плавала «пища», т. е. неисчерпаемый запас элементов набора Q. Вторая, т. н. клеточная модель, представляет собой бесконечную двумерную итеративную сеть (см. Автоматы итеративные). Конфигурация b этой сети наз. самовоспроизводящейся, если для любого натурального п найдется такой такт , что если в такт мы зададим на клеточной модели одну конфигурацию Z, то в такт т наша модель будет содержать непересекающихся конфигураций Z. Клеточная модель может рассматриваться как некоторая абстрактная среда, в которой пространство и время дискретны, а передвижения элементов могут быть заменены передачей сигналов.

В обоих случаях для доказательства возможности самовоспроизведения достаточно сложных автоматов Дж. фон Нейман предложил воспользоваться универсальным конструктором. Суть этого предложения сводится к следующему. Зафиксируем некоторый набор элементов Q. Вместо автономного автомата А рассмотрим автомат К со входом. Если, подав на К входную последовательность мы получим выходную последовательность, которую можно рассматривать как процесс построения некоторого автомата то наз. кодом автомата A g (при фиксированном К). Код автомата А обозначают через Автомат К наз. универсальным конструктором, если для любого автомата М в Q найдется такая входная последовательность что при подаче ее на вход К на выходе будет построен автомат М. Т. к. фактически вся информация о структуре автомата, который должен быть построен, может быть записана в его коде, то универсальный конструктор может быть построен даже при достаточно простых наборах элементов.

С другой стороны, код также можно представить в виде подходящего соединения элементов, реализующего автономный автомат выдающий этот код. Если соединить выход автомата со входом автомата К, что соответствует подаче входной последовательности на вход автомата К, то получим автономный автомат АГ], который порождает автомат

В этом случае автомат это автомат К, снабженный описанием своего же кода. Очевидно, что этот автомат не является А. с., т. к. он строит только автомат К без кода.

Для построения А. с. надо к автомату К добавить т. н. устр-во копирования Р, т. е. автомат, который, получив на вход код , строит на выходе копию этого кода и управляющее устр-во R (назначение его будет объяснено ниже). Полученный автомат имеет один вход и работает следующим образом. Если на его вход подать код то сначала К построит автомат 4., потом Р построит копию кода и наконец, эта копия будет подана на вход автомата т. е. будет построен автомат Управляющее устр-во R следит за тем, чтобы отмеченные выше действия были выполнены в указанной последовательности. Подадим теперь на вход автомата его собственный код, т. е. построим автомат . Очевидно, что он будет строить автоматы , т. е. будет А. с. Описанный здесь механизм самовоспроизведения поразительно напоминает процесс самовоспроизведения простейших (одноклеточных) живых организмов.

Аксиоматическое построение теории самовоспроизведения предпринял амер. математик Дж. Майхилл. Он доказал теорему, являющуюся обобщением теоремы о существовании А. с. Для широкого класса нумераций автоматов имеет место следующий факт: для любой вычислимой функции существует автомат с номером такой, что порождаемый им автомат имеет номер имеем теорему о существовании А. с.). Более того, он доказал и теорему о существовании т. н. самосовершенствующихся автоматов. Считают, что автомат более совершенный, чем автомат если при естественном уточнении понятия вычислительной способности можно сказать, что автомат способен вычислить все то, что и автомат A i и еще что-нибудь сверх этого. Справедлива теорема: существует такая бесконечная последовательность автоматов что одновременно

где . Доказывая эти теоремы, необходимо иметь такой набор элементов, из которых можно было бы построить универсальный конструктор, устр-во копирования кода и т. д.

Амер. математик Э. Мур показал, что в любой клеточной модели из достаточно широкого класса таких моделей существуют конфигурации, которые не могут быть самовоспроизводящимися. Известны попытки физ. построения моделей самовоспроизведения.

Например, англ. генетик Л. Пенроуз сделал механические элементы двух видов А и В так, что они могут сцепляться друг с другом одним из двух способов АВ или В А. Если в поднос, в котором находятся несцепленные друг с другом элементы А и В, поместить «родителя» АВ и затем начать поднос встряхивать, то в нем будут порождаться только сцепления АВ, т. е. А В будет воспроизводить себя. Если же туда поместить В А, то будут порождаться соединения В А. Амер. ученый Г. Джекобсон построил такую электромех. модель самовоспроизведения: составленные из различных вагонов игрушечные поезда, используя системы разъездных путей, так перегоняли не сцепленные между собой вагончики, что составляли поезд, подобный себе.

Лит.: Нейман Дж. фон. Общая и логическая теория автоматов. В кн.: Тьюринг А. Может ли машина мыслить? Пер. с англ. М., 1960; Penrose L. Automatic mechanical selfreproduction. «New Biology», 1959, № 28; Джекобсон Г. О моделях воспроизведения. В кн.: Кибернетический сборник, № 7. М., 1963; Майхилл Дж. Абстрактная теория самовоспроизведения. В кн.: Общая теория систем. Пер. с англ. М., 1966; Мур Э. Ф. Математические модели самовоспроизведения. В кн.: Математические проблемы в биологии. Пер. с англ. М., 1966; Арбиб М. Мозг, машина и математика. Пер. с англ. М., 1968 [библиогр. с. 217—224]; Сodd Е. F. Cellular aut6mata. New York - London, 1968 [библиогр. с. 118]; Нейман Дж. фон. Теория самовос-производящихся автоматов. Пер. с англ. М., 1971 [библиогр. с. 322—326]. М. И. Кратко.