имеем дело с конкретным автоматом. Если же пустые места не заполнены, эта схема представляет собой общее определение автомата в самом широком смысле слова. Так вот: можно описать автомат, обладающий способностью интерпретировать такого рода определение, иначе говоря, такой автомат, который, если ввести в него функции, определяющие в указанном выше смысле работу того или иного конкретного автомата, будет работать так же, как работает последний. Способность выполнять эти действия является не более загадочной, чем способность читать словарь и грамматику и следовать их указаниям относительно использования слов и законов их сочетания. Этот автомат, построенный так, что он может читать описания и имитировать описанный объект, и является универсальным автоматом в смысле Тьюринга. Чтобы он мог дублировать любую операцию, которую может выполнять любой другой автомат, достаточно снабдить его описанием этого автомата и, кроме того, инструкциями, необходимыми последнему для выполнения рассматриваемых операций.

Расширение программы на случай автоматов, которые производят автоматы

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

Основные определения

Как и в предыдущем случае, здесь тоже весьма важно дать строгое определение того, что следует понимать под автоматом в рамках нашего исследования. Прежде всего необходимо составить полный список тех элементарных частей, которые будут использоваться. Этот список должен содержать не только перечисление всех элементарных частей, но и полный набор сведений о том, как работает каждая элементарная часть в отдельности. Относительно легко составить такой список, т. е. написать каталог «машинных деталей», который был бы достаточно обширен, для того чтобы из них можно было строить множество нужных механизмов, и который удовлетворял бы требованиям аксиоматической строгости, необходимой в рассмотрениях этого рода. Этот список даже необязательно делать длинным. Его можно, конечно, сделать произвольно длинным или произвольно коротким. Список получится длинным, если в качестве элементарных частей в него будут включены объекты, которые можно получить в виде комбинаций других элементарных частей. Но список можно сделать и коротким – фактически можно устроить даже так, чтобы в нем была только одна-единственная деталь, – если каждую элементарную часть наделить разнообразными свойствами и функциями. Поэтому любое утверждение относительно числа необходимых элементарных частей представляет собой некоторый разумный компромисс, при котором ни от одной элементарной части не ожидается ничего слишком сложного и ни одна элементарная часть не предполагается выполняющей несколько явно не связанных друг с другом функций. В этом смысле, как можно показать, достаточно около дюжины элементарных частей. После этого проблему самовоспроизведения автоматов можно сформулировать следующим образом. Можно ли из указанных элементов построить такой агрегат, что, если его поместить в резервуар, где в большом количестве «плавают» все эти элементы, он начнет строить другие агрегаты, каждый из которых в конце концов станет новым автоматом, в точности подобным первоначальному? Оказывается, это возможно, и принцип, на котором эта возможность основана, тесно связан с очерченным ранее принципом Тьюринга.

Основная идея доказательства теоремы о самовоспроизведении

Прежде всего можно дать полное описание того, что, собственно, является автоматом в рассматриваемом здесь смысле. Это описание должно носить общий характер, т. е. в нем опять-таки должны быть пустые места, пробелы. Эти пробелы предназначаются для заполнения функциями, описывающими фактическую структуру того или иного автомата. Как и раньше, различие между описанием, в котором имеются пустые места, и описанием, в котором нет пустых мест (так как пробелы подобающим образом заполнены), представляет собой различие между общим описанием произвольного автомата и описанием некоторого конкретного автомата. В принципе, нетрудно описать следующие автоматы.

Автомат A, который отличается тем, что если в него ввести описание любого другого автомата в терминах соответствующим образом подобранных функций, он построит этот автомат. В данном случае описание совсем необязательно должно представлять собой ленту с нанесенными на ней пометками (как это было необходимо для машин Тьюринга), потому что, как правило, мы вряд ли выберем ленту в качестве структурного элемента. Однако совсем нетрудно описать такие комбинации структурных элементов, которые будут обладать всеми свойствами ленты, как устройства для кодирования, содержащего ячейки, в которых можно делать пометки. Описание в этом смысле мы будем называть инструкцией и обозначать буквой J.

«Строительство», или «конструирование», одним автоматом другого следует понимать в том же смысле, что и раньше. Предполагается, что строящий автомат помещен в резервуар, в котором в большом числе «плавают» все элементарные компоненты. В этой среде наш автомат и будет строить новые автоматы. Не следует особенно беспокоиться о том, каким образом фиксированный автомат этого вида окажется в состоянии строить другие автоматы, превосходящие его самого по размерам и сложности. Ибо очевидно, что в этом случае большие размеры и большая сложность автомата, который должен быть построен, найдут свое отражение в, быть может, еще большем увеличении размеров инструкции J, вводимой в автомат-строитель. Как указывалось выше, эти инструкции должны представлять собой агрегаты элементарных частей. В этом смысле можно сказать, что некоторая вещь вызывает процесс, объем и сложность которого определяются объемом и сложностью объекта, который должен быть построен в ходе этого процесса.

В дальнейшем все автоматы, для построения которых использовалась способность автомата А строить другие автоматы, будут разделять с ним это его свойство. Все они будут иметь определенное место для инструкции J, т. е. место, в которое может быть введена такого рода инструкция. Совершенно ясно, что при описании такого автомата (например, с помощью соответствующей инструкции) указание места для инструкции J (понимаемой в указанном выше смысле) составляет некоторую часть всего описания автомата. Поэтому мы можем без каких-либо дальнейших разъяснений говорить о «вводе данной инструкции J в данный автомат».

Автомат В, который может копировать любую введенную в него инструкцию J. Инструкция J есть агрегат элементарных частей в смысле, указанном в а), заменяющий бумажную ленту машины Тьюринга. Указанная особенность автомата В будет использоваться в случае, когда J представляет собой описание другого автомата. Иначе говоря, автомат В является не чем иным, как «копировальной машиной», которая может, просматривая введенную в нее перфорированную ленту, производить другую перфорированную ленту, тождественную первой. Заметим, что и этот автомат может производить объекты, превосходящие его по размерам и сложности. Отметим также, что в этом нет ничего удивительного. Поскольку автомат В может только копировать, то чтобы получить на его выходе некоторый объект,