Решение

      Фергюссон (да, по-своему, как и чудаковатый Уолтон) пытался создать нечто такое, что в случае успеха можно было бы считать осуществлением самой страстной мечты Лейбница; ведь Лейбниц серьезно размышлял о возможности создания счетной машины, которая могла бы решить все математические проблемы, а заодно и философские! Однако мечта Лейбница о машине, решающей любые математические задачи (а философские проблемы тем более), оказалась недостижимой. Этот вывод следует из результатов. полученных Гёделем, Россером, Черчем, Клини, Тьюрингом, Постом. К их работам мы сейчас и обратимся.
      Существует определенный класс счетных машин. назначение которых состоит в том, чтобы производить, те или иные математические операции над положительными целыми числами. Мы подаем на вход такой машины некое число х и получаем на выходе новое число у. Например, можно легко представить себе машину (не очень, понятно, интересную), которая при подаче на ее вход числа х дает нам на выходе число х+1. Обычно говорят, что такая машина выполняет операцию прибавления единицы. Можно сделать машину, которая выполняет, скажем, операцию сложения двух чисел. В такой машине мы сначала подаем на вход число х, потом число у, затем нажимаем кнопку и через какое-то время получаем на выходе число х+у. (Для таких машин имеется свое техническое название — их, по-моему, называют суммирующими машинами!)
      Существует и другой тип машин, которые можно назвать генерирующими, или перечисляющими, машинами Такие машины будут играть более важную роль в наших последующих рассуждениях (где мы следуем теориям Поста). Эти машины не имеют входов; они запрограммированы на генерирование множества положительных целых чисел. Например, одна машина может генерировать у нас множество четных чисел, другая — генерировать множество нечетных чисел, третья — множество простых чисел, и т. д. При этом типичная машинная программа для генерирования четных чисел может выглядеть так.
      Мы задаем машине две команды (1) напечатать число 2; (2) если напечатано число n, то напечатать число n+2. (Разрешается задавать вспомогательные правила, которые определяют порядок выполнения команд таким способом, чтобы машина в конечном счете выполнила все, что она может выполнить.) Такая машина, подчиняясь команде (1), рано или поздно напечатает число 2, а напечатав 2 она в конце концов, подчиняясь команде (2), напечатает число 4, затем, напечатав 4, она, опять же руководствуясь командой (2), напечатает число 6, потом числа 8, 10 и т. д. Тем самым наша машина будет генерировать множество четных чисел. (Отметим, что без введения дополнительных команд она никогда не сможет произвести нам числа 1, 3, 5 или любое другое нечетное число.) Чтобы запрограммировать машину на генерирование нечетных чисел, нам следует просто заменить первую команду на команду «напечатать число 1». Иногда объединяют вместе две или несколько машин, с тем чтобы информация на выходе одной машины могла быть использована в другой. Пусть, например, у нас имеются две машины, А и В, программу для которых мы составим следующим образом. Машине А мы зададим две команды: (1) напечатать число 1; (2) если машина В напечатала число n, то напечатать число n+1. Машине В мы задаем только одну команду: (1) если машина А напечатала число n, то напечатать число n+1. Какие числа будет генерировать машина А, а какие — машина В? Ответ: машина А будет генерировать множество нечетных чисел, а машина В — множество четных чисел.
      Теперь представим себе, что программа для генерирующей машины записывается не на естественном языке, а кодируется в виде некоторого целого числа (представляющего собой цепочку цифр); кодирование можно осуществить так, чтобы каждое положительное целое число представляло собой номер определенной программы. Пусть Мn — это машина, программа которой имеет кодовый номер n. Расположим теперь все генерирующие машины в виде бесконечной последовательности М1, М2…, Мn… (М1 — это машина с номером программы 1, М2 — машина с номером программы 2 и т. д.)
      Для любого множества чисел А (естественно, имеется в виду множество положительных целых чисел) и для любой машины М мы будем говорить, что машина М генерирует множество А, или, иначе, машина М перечисляет множество А, если каждое число, входящее в множество А, в конце концов будет напечатано машиной М, и в то же время ни одно число, не входящее в А, этой машиной напечатано не будет. Множество А мы будем называть эффективно перечислимым (иногда говорят — рекурсивно перечислимым), если существует хотя бы одна машина Мi которая перечисляет множество А. Кроме того, мы будем говорить, что множество А разрешимо (или рекурсивно), если существуют одна машина Мi, которая перечисляет само множество А, и другая машина Мj которая перечисляет множество всех чисел, не входящих в А. Таким образом, множество А является разрешимым том и только том случае, если и A, и его дополнение А являются эффективно перечислимыми.
      Предположим, что множество А — разрешимо и у нас имеются машина Мi, которая генерирует А, и машина Мj которая генерирует дополнение А. Тогда оказывается, что существует эффективный способ, позволяющий определять, входит ли некоторое число n в множество А или нет. Допустим, к примеру, нас интересует, входит ли в множество А число 10. Мы приводим в действие обе машины одновременно и ждем. Если число 10 принадлежит множеству А, то рано или поздно это число будет напечатано машиной Mi, так что мы сразу узнаем, что число 10 входит в А. Если же число 10 не принадлежит множеству А, то в конце концов это число напечатает машина Mj — тем самым мы сразу узнаем, что число 10 не входит в А. Таким образом, в конечном итоге мы обязательно выясним, принадлежит ли число 10 множеству А или нет. (Понятно, что сказать заранее, сколько нам придется ждать, невозможно; нам известно лишь, что через какой-то конечный промежуток времени мы непременно узнаем ответ.)
      Предположим теперь, что множество А эффективно перечислимо, но неразрешимо. В таком случае у нас имеется машина Мi, которая генерирует множество А, но не окажется машины, которая генерировала бы дополнение А. Допустим, что мы опять хотим узнать, входит ли в А некоторое заданное число — скажем, число 10. Лучшее, что мы можем сделать в таком случае — запустить машину Mi, и надеяться на удачу! Теперь наши шансы узнать ответ составляют лишь 50 %. Если число 10 действительно входит в множество А, то в конце концов мы обязательно это узнаем, поскольку рано или поздно машина М, напечатает это число. Если же число 10 в А не входит, то машина Мi, никогда этого числа не напечатает, однако сколько бы мы ни ждали, у нас никогда не будет уверенности, что через какое-то время машина все-таки не напечатает число 10. Итак, если число 10 принадлежит множеству А, то рано или поздно мы узнаем об этом; если же число 10 не принадлежит А, то мы никогда не будем знать об этом наверняка (во всяком случае, если ограничимся наблюдением за машиной М,). Такое множество А можно с основанием называть полуразрешимым.
      Первое важное свойство генерирующих машин заключается в том, что можно сконструировать так называемую универсальную машину U, назначение к торой — систематически наблюдать за поведением во машин m1, М2, М3…, Мn… и, как только машина Мх напечатает число у, сразу же сообщить нам об этом. Но каким образом это сделать? Очень просто— напечатать некоторое число, скажем для данных х и у напечатать х*у, то есть число, как и ранее, состоящее из цепочки единиц длиной х, за которой следует цепочка нулей длиной у. Итак, основная команда для машины U такова: когда машина М* напечатает число у, то напечатать число х*у.
      Допустим, например, что машина Ма запрограммирована на генерирование множества нечетных чисел, а машина Мb — на генерирование множества четных чисел. Тогда машина U будет печатать числа а*1, а*3, а*5 и т. д., а также числа b*2, b*4, b*8 и т. д., однако она никогда не напечатает число а*4 (поскольку машина Ма никогда не напечатает число 4) или число b*3 (поскольку машина Мb никогда не напечатаем число 3).
      Далее, поскольку машина U имеет свою собственную программу, то, следовательно, она входит в семейство программируемых машин М1 М2…, Мn… Это значит, что существует некоторая машина Мь номер программы которой k совпадает с номером программы машины U, причем машина М* и есть сама машина U! (В строгой научной статье я указал бы, что это за число k.)
      Можно заметить, что наша универсальная машина Mk наблюдает в числе прочих и за своим собственным поведением. Поэтому, как только машина Мk напечатает число n, она должна напечатать число k* n, а значит, и число k*(k*n), а также и число k*[k*(k* n)] и т. д.
      Другой важной особенностью этих машин является то, что, имея произвольную машину Мa, мы всегда можем запрограммировать другую машину Mb, таким образом, чтобы она печатала в точности такие числа х, при которых машина Мa, печатает числа х* х. (Машина Mb, так сказать, «следит» за машиной Мa и действует но такой команде: напечатать число х после того, как машина Мa напечатает число х*х.) Можно, наконец, закодировать программы так, что для каждого а таким числом b окажется число 2а; тогда для каждого а машина М2а будет печатать в точности такие числа х, при которых машина Мa печатает числа х*х. Представим себе, что мы так и устроили, и запишем два основных утверждения, на которые будем опираться в дальнейшем.
       Утверждение 1.Универсальная машина U печатает число x*у, если и только если машина Мx печатает число у.
       Утверждение 2.Для каждого числа а машина М2a, печатает число х, если и только если машина Ма печатает число х*х.
      Вот теперь мы подходим к самому главному. Оказывается, что любую формальную математическую задачу можно сформулировать в виде вопроса: напечатает машина Мa число b или не напечатает? Иначе говоря, для любой данной формальной системы аксиом можно всем утверждениям системы приписать определенные гёделевы номера, после чего найти такое число a, при котором машина Мa будет печатать гёделевы номера всех доказуемых утверждений данной системы и никаких других номеров печатать не будет. Поэтому, для того чтобы узнать, доказуемо или недоказуемо данное утверждение в исходной системе аксиом, мы берем его гёделев номер b и задаемся вопросом: напечатает ли машина Мa число b или не напечатает? Значит, если бы у нас существовал какой-то эффективный алгоритм, позволяющий определять, какие машины печатают те или иные числа, то мы вполне могли бы решить, какие утверждения доказуемы в той или иной системе аксиом. В этом, собственно, и заключалось бы осуществление мечты Лейбница. Более того, вопрос — какие машины печатают те или иные числа, может быть сведен к вопросу — какие числа печатает универсальная машина U, потому что вопрос, напечатает ли машина Мa число b, равносилен вопросу, напечатает ли машина U число а* b. Поэтому полное познание машины U означает полное познание всех машин, а следовательно, и всея математических систем. И наоборот, любой вопрос том, напечатает ли некая машина заданное число; может быть сведен к вопросу о том, доказуемо ли тo или иное утверждение в определенной математической системе. Таким образом, полное познание всех формальных математических систем означает полное познание нашей универсальной машины.
      Итак, главный вопрос, стоящий перед нами, можно сформулировать следующим образом. Пусть V — множество чисел, которые может напечатать универсальная машина U (это множество иногда называют универсальным множеством). Разрешимо множество V или нет? Если оно разрешимо, то мечта Лейбница осуществима; если же нет, то его стремления никогда не смогут быть реализованы. Поскольку V эффективно перечислимо (ведь оно генерируется машиной U), то вопрос сводится к тому, существует ли некая машина Ма, которая сможет напечатать дополнение V, а именно множество V'. Иначе говоря, существует ли такая машина Ма, которая печатает те и только те числа, которые машина U не печатает? На этот вопрос можно дать исчерпывающий ответ лишь на основании утверждений 1 и 2, о которых мы упоминали выше.
      Теорема L. Множество V' не является эффективно перечислимым: для любой заданной машины Ма либо существует какое-то число, принадлежащее множеству V, которое машина Ма не может напечатать, либо машина Ма напечатает по крайней мере одно число, которое принадлежит не множеству V', а множеству V.
      Сумеет ли читатель доказать теорему L?
      Рассмотрим также следующий частный случай. Пусть у нас имеется утверждение о том, что машина М5 перечислила множество V'. Чтобы опровергнуть это утверждение, достаточно отыскать некоторое число n, показав при этом, что либо оно принадлежит множеству V', но не может быть напечатано машиной М5, либо оно не принадлежит множеству V, но машина М5 может его напечатать. Сумеете ли вы найти такое число n?
      Я приведу решение этой задачи сразу, а не в конце главы, — по существу, это решение просто повторяет доказательство Гёделя.
      Итак, возьмем произвольное число а. Согласно утверждению 2, машина Ма напечатает число х*х, если и только если машина М2а напечатает число х. Но, согласно утверждению 1, машина М2а напечатает число х, если и только если универсальная машина U напечатает число 2а*х, или, что то же самое, если число 2а*х принадлежит множеству V. Следовательно, машина Ма напечатает число х*х, если и только если число 2а*х входит в V. В частности (положив х равным 2а), машина Ма напечатает число 2а*2а, если и только если число 2а*2а принадлежит множеству V. Итак, либо (1): машина Ма напечатает число 2а*2а, и число 2а*2а принадлежит множеству V; либо (2): машина Ма не напечатает число 2а*2а, и число 2а*2а принадлежит множеству V.
      Если выполнено условие (1), то машина Ма напечатает число 2а*2а, которое входит не в V, а в V; это означает, что машина Ма не генерирует множество V, потому что она может напечатать по крайней мере одно число 2а*2а, которое не входит в множество V. Если же выполняется (2), то мы опять получаем, что машина Ма не генерирует множество V поскольку число 2а*2а принадлежит множеству V, а машина Ма это число напечатать не может. Итак, в обоих случаях машина Ма не генерирует множество V. В силу произвольности выбора а это означает, что никакая машина не может перечислить множество V, и, следовательно, это множество не является эффективно перечислимым.
      Конечно, в частном случае а = 5 число n окажется равным 10*10.
      Но все же какое это имеет отношение к мечтам Лейбница? Строго говоря, мы не можем ни доказать, ни опровергнуть возможность осуществления лейбницевых надежд, поскольку они никогда точно не формулировались. Ведь во времена Лейбница не существовало строгого определения понятий «вычислительная машина» или «генерирующая машина»; соответствующие точные определения были получены лишь в нашем веке. Подобных определений имеется много (их вводили Гёдель, Эрбран, Клини, Черч, Тьюринг, Пост, Смаллиан, Марков и многие другие), однако было проверено, что все они эквивалентны между собой. И если под словом «разрешимо» понимать разрешимость в соответствии с любым из этих эквивалентных определений, то мечта Лейбница оказывается неосуществимой по той простой причине, что сами машины можно перенумеровать таким образом, что утверждения 1 и 2 обязательно будут выполняться. Тогда по теореме L множество V, генерируемое универсальной машиной, оказывается неразрешимым — оно будет лишь полу разрешимо. Следовательно, не существует никакой «чисто механической» процедуры, с помощью которой можно было бы узнать, какие утверждения доказуемы в той или иной системе аксиом, а какие нет. Таким образом, любая попытка изобрести некий хитроумный «механизм» для решения всех математических задач обречена на провал.
      Это означает, что, выражаясь пророческими словами известного логика Эмиля Поста (1944), математическое мышление является и всегда будет оставаться по сути своей сугубо творческим процессом. Или, как остроумно заметил математик Пол Розенблум, — человеку никогда не избавиться от необходимости пользоваться своим умом, сколько бы ума он не приложил к этому.