Очевидно, что на этом уровне в результате Маккаллока – Питтса не содержится более ничего полезного. В этом отношении он представляет собой лишь новую иллюстрацию той ситуации, которая была обрисована выше. Налицо эквивалентность между законами логики и их осуществлением в нервной сети, и хотя в более простых случаях с помощью этих законов можно получать более простые формы представления для нервных сетей, весьма возможно, что в особо сложных случаях справедливо обратное.
Все это не меняет моей глубокой уверенности в том, что для понимания высокосложных автоматов, и в частности центральной нервной системы, требуется новая существенно-логическая теория. Тем не менее не исключена возможность того, что в ходе этого процесса логика вынуждена будет претерпеть метаморфозу и превратиться в неврологию в гораздо большей степени, чем неврология – в раздел логики. Проведенный выше анализ показывает, что для развития теории центральной нервной системы одну немаловажную вещь можно сделать уже сейчас: именно можно показать, каковы те направления, которые уводят в сторону от действительных проблем.
VI. Понятие сложности. Самовоспроизведение
Изложенные выше соображения показали, что фактор сложности играет важную роль во всякой попытке продвинуться вперед в теории автоматов и что понятие сложности, несмотря на его prima facie[41] количественный характер, может в действительности выражать нечто качественное – иметь принципиальное значение. В оставшейся части своего доклада я подвергну рассмотрению более отдаленное следствие из этого понятия, следствие, которое делает еще более явным один из качественных аспектов этого понятия.
Совершенно очевидно, что в природе существует связь типа «порочного круга», простейшим выражением которой является тот факт, что очень сложные организмы могут воспроизводить себя.
Мы вообще склонны неясно подозревать наличие понятия о «сложности»; это понятие и его предполагаемые свойства никогда не были четко сформулированы. Однако мы всегда склоняемся к допущению, что они проявляются следующим образом. Когда автомат выполняет некоторые операции, следует ожидать, что эти операции будут менее сложными, чем сам автомат. В частности, если автомат способен строить другие автоматы, то должно существовать уменьшение сложности при переходе от автомата-строителя к построенному им автомату. Это означает, что если автомат 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), определяющим работу данного автомата. Если на пустые места подставлены соответствующие значения, мы имеем дело с конкретным автоматом. Если же пустые места не заполнены, эта схема представляет собой общее определение автомата в самом широком смысле слова. Так вот: можно описать автомат, обладающий способностью интерпретировать такого рода определение, иначе говоря, такой автомат, который, если ввести в него функции, определяющие в указанном выше смысле работу того или иного конкретного автомата, будет работать так же, как работает последний. Способность выполнять эти действия является не более загадочной, чем способность читать словарь и грамматику и следовать их указаниям относительно использования слов и законов их сочетания. Этот автомат, построенный так, что он может читать описания и имитировать описанный объект, и является универсальным автоматом в смысле Тьюринга. Чтобы он мог дублировать любую операцию, которую может выполнять любой другой автомат, достаточно снабдить его описанием этого автомата и, кроме того, инструкц