Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
Предположим, что множество А—разрешимо и у нас имеются машина М;, которая генерирует А, и машина Мкоторая генерирует дополнение А. Тогда оказывается, что существует эффективный способ, позволяющий определять, входит ли некоторое число п в множество А или нет. Допустим, к примеру, нас интересует, входит ли в множество А число 10. Мы приводим в действие обе машины одновременно и ждем. Если число 10 принадлежит множеству А, то рано или поздно это число будет напечатано машиной Мі, так что мы сразу узнаем, что число 10 входит в А. Если же число 10 не принадлежит множеству А, то в конце концов это число напечатает машина М;-—тем самым мы сразу узнаем, что число 10 не входит в А. Таким образом, в конечном итоге мы обязательно выясним, принадлежит ли число 10 множеству А или нет. (Понятно, что сказать заранее, сколько нам придется ждать, невозможно; нам известно лишь, что через какой-то конечный промежуток времени мы непременно узнаем ответ.)
Предположим теперь, что множество А эффективно перечислимо, но неразрешимо. В таком случае у нас имеется машина Мі, которая генерирует множество А, но не окажется машины, которая генерировала бы дополнение А. Допустим, что мы опять хотим узнать, входит ли в А некоторое заданное число — скажем, число 10. Лучшее, что мы можем сделать в таком случае — запустить машину Мі и надеяться на удачу! Теперь наши шансы узнать ответ составляют лишь 50%. Если число 10 действительно входит в множество А, то в конце концов мы обязательно это узнаем, поскольку рано или поздно машина М( напечатает это число. Если же число 10 в А не входит, то машина М; никогда этого числа не напечатает, однако сколько бы
мы ни ждали, у нас никогда не будет уверенности, что через какое-то время машина все-таки не напечатает число 10. Итак, если число 10 принадлежит множеству А, то рано или поздно мы узнаем об этом; если же’ число 10 не принадлежит А, то мы никогда не будем знать об этом наверняка (во всяком случае, если ограничимся наблюдением за машиной М,). Такое множество А можно с основанием называть полуразре-шимым.
Первое важное свойство генерирующих машин заключается в том, что можно сконструировать так называемую универсальную машину 17, назначение которой—систематически наблюдать за поведением всех машин М|, М2, Мз, ... , М„, ... и, как только машина Мх напечатает число у, сразу же сообщить нам об этом. Но каким образом это сделать? Очень просто— напечатать некоторое число, скажем для данных х и у напечатать х * у, то есть число, как и ранее, состоящее из цепочки единиц длиной х, за которой следует цепочка нулей длиной у. Итак, основная команда для машины и такова: когда машина Мх напечатает число у, то напечатать число х* у.
Допустим, например, что машина Ма запрограммирована на генерирование множества нечетных чисел, а машина Мь—на генерирование множества четных чисел. Тогда машина 17 будет печатать числа а*1, а*Ъ, а*5 и т. д., а также числа Ь*2, Ь*4, Ь*8 и т. д., однако она никогда не напечатает число а*4 (поскольку машина Ма никогда не напечатает число 4) или число Ь* 3 (поскольку машина Мь никогда не напечатает число 3).*
Далее, поскольку машина 17 имеет свою собственную программу, то, следовательно, она входит в семейство программируемых машин Ми М2, ..., М„, ... . Это значит, что существует некоторая машина Мк, номер программы которой к совпадает с номером программы машины 17, причем машина Мк и есть сама машина 17! (В строгой научной статье я указал бы, что это за число к.)
Можно заметить, что наша универсальная машина Мк наблюдает в числе прочих и за своим собственным поведением. Поэтому, как только машина Мк напечата-
216
ет число п, она должна напечатать число к* п, а значит, и число к* (к* п), а также и число к* [к* (к* и)] и т. д.
Другой важной особенностью этих машин является то, что, имея произвольную машину Ма, мы всегда можем запрограммировать другую машину Мь таким образом, чтобы она печатала в точности такие числа х, при которых машина Ма печатает числа х *х. (Машина Мь, так сказать, «следит» за машиной Ма и действует по такой команде: напечатать число х после того, как машина Ма напечатает число х* х.) Можно, наконец, закодировать программы так, что для каждого а таким числом Ь окажется число 2а; тогда для каждого а машина М2а будет печатать в точности такие числа х, при которых машина Ма печатает числа х*х. Представим себе, что мы так и устроили, и запишем два основных утверждения, на которые будем опираться в дальнейшем.
Утверждение 1. Универсальная машина и печатает число х* у, если и только если машина Мх печатает число у.
Утверждение 2. Для каждого числа а машина М2а печатает число х, если и только если машина Ма печатает число х * х.
Вот теперь мы подходим к самому главному. Оказывается, что любую формальную математическую задачу можно сформулировать в виде вопроса: напечатает машина Ма число Ь или не напечатает? Иначе говоря, для любой данной формальной системы аксиом можно всем утверждениям системы приписать определенные гёделевы номера, после чего найти такое число а, при котором машина Ма будет печатать гёделевы номера всех доказуемых утверждений данной системы и никаких других номеров печатать не будет. Поэтому, для того чтобы узнать, доказуемо или недоказуемо данное утверждение в исходной системе аксиом, мы берем его гёделев номер Ь и задаемся вопросом: напечатает ли машина Ма число Ъ или не напечатает? Значит, если бы у нас существовал какой-то эффективный алгоритм, позволяющий определять, какие машины печатают те или иные числа, то мы вполне могли бы решить, какие утверждения доказуемы в той или иной системе аксиом. В этом, собственно, и заключалось бы осуществле-
