Совершенно очевидно, что в природе существует связь типа «порочного круга», простейшим выражением которой является тот факт, что очень сложные организмы могут воспроизводить себя.

Мы вообще склонны неясно подозревать наличие понятия о «сложности»; это понятие и его предполагаемые свойства никогда не были четко сформулированы. Однако мы всегда склоняемся к допущению, что они проявляются следующим образом. Когда автомат выполняет некоторые операции, следует ожидать, что эти операции будут менее сложными, чем сам автомат. В частности, если автомат способен строить другие автоматы, то должно существовать уменьшение сложности при переходе от автомата-строителя к построенному им автомату. Это означает, что если автомат A может произвести автомат В, то автомат A каким-то образом должен содержать полное описание автомата В. Чтобы описание было эффективным, в A, кроме того, должны иметься различные устройства для наблюдения за тем, чтобы это описание соответствующим образом интерпретировалось, а предусматриваемые им строительные операции выполнялись. В этом смысле кажется как будто естественным ожидать известной тенденции к вырождению, т. е. того, что будет наблюдаться некоторое уменьшение сложности, по мере того как одни автоматы будут производить другие.

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

Таким образом, между правдоподобием наших выводов и очевидностью фактов налицо явное несоответствие, если не хуже. Ввиду этого заслуживает, по-видимому, внимания попытка выяснить, нет ли здесь чего-нибудь такого, что можно было бы сформулировать строго.

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

Теория вычислительных автоматов Тьюринга

Английский логик Тьюринг около 12 лет тому назад рассмотрел следующую проблему.

Тьюринг хотел сформулировать общее определение вычислительного автомата. Формальное определение получилось таким.

Автомат есть «черный ящик», который мы не описываем подробно, но который обладает следующими свойствами. Он имеет конечное число состояний, которые следует prima facie характеризовать, только указав их число (скажем, π) и занумеровав их числами 1, 2, π. Работа автомата будет существенно охарактеризована, если указать, каким образом можно вызвать изменение его состояния, т. е. как перевести автомат из состояния i в состояние j. Это изменение состояния потребует некоторого взаимодействия с внешним миром, которое будет стандартизовано следующим образом. Поскольку речь идет о машине, весь внешний мир можно представить себе состоящим из длинной бумажной ленты. Пусть эта лента имеет, например, 1 дюйм в ширину и разделена на ячейки (клетки), имеющие 1 дюйм в длину. В каждой ячейке этой ленты мы можем ставить или не ставить какой-нибудь знак, например точку, причем мы предполагаем, что эту точку можно как ставить, так и стирать. Ячейку, отмеченную точкой, мы будем называть «1», ячейку, не отмеченную точкой, будем называть «0». (Мы могли бы отмечать ячейки, используя большее число знаков, но, как показал Тьюринг, это не играет роли, ибо не приводит к чему-либо существенно более общему.) При описании положения ленты относительно автомата предполагается, что автомат может непосредственно контролировать одну ячейку ленты и что он обладает способностью передвигать ленту вперед и назад, скажем, на одну клетку за один раз. Чтобы пояснить вышеизложенное, допустим, что автомат находится в состоянии i (= 1, 2, 3, n) и что на ленте он видит знак е (= 0, 1); потом он переходит в состояние j (= 1, 2, 3,, n) передвигает ленту пар ячеек (р = 0, +1, –1; +1 означает, что автомат передвинул ленту на одну ячейку вперед, –1 – на одну ячейку назад) и вписывает в новую клетку, которая оказывается в поле его зрения, знак f (= 0, 1; «вписывание нуля» означает, что автомат стирает точку; «вписывание единицы» означает, что автомат ставит точку). Задав j, р и f как функции от i и е, мы полностью определим действие такого автомата.

Тьюринг тщательно проанализировал, какие математические процессы могут осуществлять автоматы этого типа. В связи с этим он доказал различные теоремы, касающиеся классической «проблемы разрешимости» логики[42], но я не буду касаться здесь этого вопроса. Он также ввел и проанализировал понятие «универсального автомата». Эта часть его работы имеет непосредственное отношение к нашей теме. Бесконечные последовательности цифр е (= 0, 1) являются одним из основных объектов математического исследования. Рассматриваемые как представления чисел в двоичной системе, они, в сущности, оказываются эквивалентными понятию действительного числа. Поэтому Тьюринг в своих рассуждениях исходил из таких последовательностей.

Тьюринг исследовал вопрос, какие автоматы могли бы построить ту или иную последовательность. Иначе говоря, если задан закон образования такой последовательности, то спрашивается, какой автомат следует применить для образования последовательности согласно этому закону. При этом под процессом «образования» последовательности понимается следующее. Автомат способен «образовать» некоторую последовательность, если возможно разметить определенный конечный участок ленты таким образом, что если ленту ввести в рассматриваемый автомат, последний выпишет эту последовательность на остальной свободной (и бесконечной) части ленты. Разумеется, этот процесс выписывания бесконечной последовательности никогда не закончится. То, что имеется в виду, когда говорят, что автомат способен выписать на ленте данную бесконечную последовательность, – это лишь то, что, выполняя эту задачу, он будет работать неограниченно долго и при условии, что ему предоставят достаточно времени, выпишет на ленте любую требуемую (разумеется, конечную) часть данной (бесконечной) последовательности. Упомянутый выше конечный участок ленты, размечаемый перед введением ленты в автомат, представляет собой «инструкцию» автомату для решения этой задачи.

Основной результат теории Тьюринга

A priori кажется, что создание «универсального автомата» невозможно. Как может существовать автомат, столь же эффективный, как и любой автомат, который только можно себе представить, в том числе, например, автомат, вдвое больший данного по размерам и сложности?

Тем не менее Тьюринг доказал, что такой автомат возможен. Хотя структура универсального автомата очень сложна, принцип, лежащий в его основе, весьма прост.

Тьюринг заметил, что совершенно общее описание произвольного автомата может быть дано (в смысле предыдущего определения) с помощью конечного числа слов. Это описание будет содержать некоторые пустые места – пробелы, которые соответствуют упомянутым выше функциям (функциям j, р, f, которые зависят от i, e), определяющим работу данного автомата. Если на пустые места подставлены соответствующие значения, мы