Рэймонд Смаллиан - Принцесса или тигр?

Предположим теперь, что множество А эффективно перечислимо, но неразрешимо. В таком случае у нас имеется машина М i , которая генерирует множество А, но не окажется машины, которая генерировала бы дополнение А. Допустим, что мы опять хотим узнать, входит ли в А некоторое заданное число — скажем, число 10. Лучшее, что мы можем сделать в таком случае — запустить машину М i и надеяться на удачу! Теперь наши шансы узнать ответ составляют лишь 50 %. Если число 10 действительно входит в множество А, то в конце концов мы обязательно это узнаем, поскольку рано или поздно машина М i напечатает это число. Если же число 10 в А не входит, то машина М i никогда этого числа не напечатает, однако сколько бы мы ни ждали, у нас никогда не будет уверенности, что через какое-то время машина все-таки не напечатает число 10. Итак, если число 10 принадлежит множеству А, то рано или поздно мы узнаем об этом; если же число 10 не принадлежит А, то мы никогда не будем знать об этом наверняка (во всяком случае, если ограничимся наблюдением за машиной М i ). Такое множество А можно с основанием называть полуразрешимым .

Первое важное свойство генерирующих машин заключается в том, что можно сконструировать так называемую универсальную машину U, назначение к торой — систематически наблюдать за поведением во машин M 1, М 2, М 3…, М n … и, как только машина М х напечатает число у, сразу же сообщить нам об этом. Но каким образом это сделать? Очень просто — напечатать некоторое число, скажем для данных x и у напечатать x*y, то есть число, как и ранее, состоящее из цепочки единиц длиной х, за которой следует цепочка нулей длиной у. Итак, основная команда для машины U такова: когда машина М х напечатает число у, то напечатать число x * y .

Допустим, например, что машина М a запрограммирована на генерирование множества нечетных чисел, а машина М b — на генерирование множества четных чисел. Тогда машина U будет печатать числа а *1, а *3, а *5 и т. д., а также числа b *2, b *4, b *8 и т. д., однако она никогда не напечатает число а *4 (поскольку машина М a никогда не напечатает число 4) или число b*3 (поскольку машина М b никогда не напечатаем число 3).

Далее, поскольку машина U имеет свою собственную программу, то, следовательно, она входит в семейство программируемых машин M 1, М 2…, М n … Это значит, что существует некоторая машина М k , номер программы которой k совпадает с номером программы машины U, причем машина М k и есть сама машина U! (В строгой научной статье я указал бы, что это за число k. )

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

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

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

Утверждение 2.Для каждого числа а машина М 2 a печатает число х, если и только если машина М 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, о которых мы упоминали выше.