, М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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69