Принцесса или тигр?

Можно заметить, что наша универсальная машина М_k наблюдает в числе прочих и за своим собственным поведением. Поэтому, как только машина М_k напечатает число n, она должна напечатать число k*n, а значит, и число k*(k*n), а также и число k*[k*(k* n)] и т. д.

Другой важной особенностью этих машин является то, что, имея произвольную машину М_a, мы всегда можем запрограммировать другую машину М_b таким образом, чтобы она печатала в точности такие числа х, при которых машина М_a печатает числа х*х. (Машина М_b, так сказать, «следит» за машиной М_a и действует но такой команде: напечатать число x после того, как машина М_a напечатает число x*x.) Можно, наконец, закодировать программы так, что для каждого а таким числом b окажется число 2а; тогда для каждого а машина М_2a будет печатать в точности такие числа х, при которых машина М_a печатает числа x*x. Представим себе, что мы так и устроили, и запишем два основных утверждения, на которые будем опираться в дальнейшем.

Утверждение 1. Универсальная машина U печатает число x*у, если и только если машина М_x печатает число у.

Утверждение 2. Для каждого числа а машина М_2a печатает число х, если и только если машина М_a печатает число x*x.

Вот теперь мы подходим к самому главному. Оказывается, что любую формальную математическую задачу можно сформулировать в виде вопроса: напечатает машина М_a число b или не напечатает? Иначе говоря, для любой данной формальной системы аксиом можно всем утверждениям системы приписать определенные гёделевы номера, после чего найти такое число a, при котором машина М_a будет печатать гёделевы номера всех доказуемых утверждений данной системы и никаких других номеров печатать не будет. Поэтому, для того чтобы узнать, доказуемо или недоказуемо данное утверждение в исходной системе аксиом, мы берем его гёделев номер b и задаемся вопросом: напечатает ли машина М_a число b или не напечатает? Значит, если бы у нас существовал какой-то эффективный алгоритм, позволяющий определять, какие машины печатают те или иные числа, то мы вполне могли бы решить, какие утверждения доказуемы в той или иной системе аксиом. В этом, собственно, и заключалось бы осуществление мечты Лейбница. Более того, вопрос — какие машины печатают те или иные числа, может быть сведен к вопросу — какие числа печатает универсальная машина U, потому что вопрос, напечатает ли машина М_a число b, равносилен вопросу, напечатает ли машина U число а*b. Поэтому полное познание машины U означает полное познание всех машин, а следовательно, и всея математических систем. И наоборот, любой вопрос том, напечатает ли некая машина заданное число; может быть сведен к вопросу о том, доказуемо ли то или иное утверждение в определенной математической системе. Таким образом, полное познание всех формальных математических систем означает полное познание нашей универсальной машины.

Итак, главный вопрос, стоящий перед нами, можно сформулировать следующим образом. Пусть V — множество чисел, которые может напечатать универсальная машина U (это множество иногда называют универсальным множеством). Разрешимо множество V или нет? Если оно разрешимо, то мечта Лейбница осуществима; если же нет, то его стремления никогда не смогут быть реализованы. Поскольку V эффективно перечислимо (ведь оно генерируется машиной U), то вопрос сводится к тому, существует ли некая машина М_a, которая сможет напечатать дополнение V, а именно множество V̅. Иначе говоря, существует ли такая машина М_a, которая печатает те и только те числа, которые машина U не печатает? На этот вопрос можно дать исчерпывающий ответ лишь на основании утверждений 1 и 2, о которых мы упоминали выше.

Теорема L. Множество V̅ не является эффективно перечислимым: для любой заданной машины М_a либо существует какое-то число, принадлежащее множеству V̅, которое машина М_a не может напечатать, либо машина М_a напечатает по крайней мере одно число, которое принадлежит не множеству V̅, а множеству V.

Сумеет ли читатель доказать теорему L?

Рассмотрим также следующий частный случай. Пусть у нас имеется утверждение о том, что машина М₅ перечислила множество V̅. Чтобы опровергнуть это утверждение, достаточно отыскать некоторое число n, показав при этом, что либо оно принадлежит множеству V̅, но не может быть напечатано машиной М₅, либо оно не принадлежит множеству V, но машина М₅ может его напечатать. Сумеете ли вы найти такое число n?

Я приведу решение этой задачи сразу, а не в конце главы, — по существу, это решение просто повторяет доказательство Гёделя.