Принцесса или тигр? - [72]
Можно заметить, что наша универсальная машина М>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?
Рассмотрим также следующий частный случай. Пусть у нас имеется утверждение о том, что машина М>5 перечислила множество V̅. Чтобы опровергнуть это утверждение, достаточно отыскать некоторое число n, показав при этом, что либо оно принадлежит множеству V̅, но не может быть напечатано машиной М>5, либо оно не принадлежит множеству V, но машина М>5 может его напечатать. Сумеете ли вы найти такое число n?
Я приведу решение этой задачи сразу, а не в конце главы, — по существу, это решение просто повторяет доказательство Гёделя.
Итак, возьмем произвольное число а. Согласно утверждению 2, машина М>a напечатает число x*x, если и только если машина М>2a напечатает число х. Но, согласно утверждению 1, машина М>2a напечатает число х, если и только если универсальная машина U напечатает число 2а*х, или, что то же самое, если число 2а*х принадлежит множеству V. Следовательно, машина М>a напечатает число x*x, если и только если число 2
