Принцесса или тигр? - [71]

, то напечатать число n + 1. Машине В мы задаем только одну команду: (1) если машина А напечатала число n, то напечатать число n + 1. Какие числа будет генерировать машина А, а какие — машина В? Ответ: машина А будет генерировать множество нечетных чисел, а машина В — множество четных чисел.

Теперь представим себе, что программа для генерирующей машины записывается не на естественном языке, а кодируется в виде некоторого целого числа (представляющего собой цепочку цифр); кодирование можно осуществить так, чтобы каждое положительное целое число представляло собой номер определенной программы. Пусть М_n — это машина, программа которой имеет кодовый номер n. Расположим теперь все генерирующие машины в виде бесконечной последовательности М₁, М₂…, М_n… (М₁ — это машина с номером программы 1, М₂ — машина с номером программы 2 и т. д.)

Для любого множества чисел А (естественно, имеется в виду множество положительных целых чисел) и для любой машины M мы будем говорить, что машина M генерирует множество А, или, иначе, машина M перечисляет множество А, если каждое число, входящее в множество А, в конце концов будет напечатано машиной M, и в то же время ни одно число, не входящее в А, этой машиной напечатано не будет. Множество А мы будем называть эффективно перечислимым (иногда говорят — рекурсивно перечислимым), если существует хотя бы одна машина М_i которая перечисляет множество А. Кроме того, мы будем говорить, что множество А разрешимо (или рекурсивно), если существуют одна машина М_i, которая перечисляет само множество А, и другая машина М_j которая перечисляет множество всех чисел, не входящих в А. Таким образом, множество А является разрешимым том и только том случае, если и A, и его дополнение A̅ являются эффективно перечислимыми.

Предположим, что множество А — разрешимо и у нас имеются машина М_i, которая генерирует А, и машина М_j которая генерирует дополнение A̅. Тогда оказывается, что существует эффективный способ, позволяющий определять, входит ли некоторое число n в множество А или нет. Допустим, к примеру, нас интересует, входит ли в множество А число 10. Мы приводим в действие обе машины одновременно и ждем. Если число 10 принадлежит множеству А, то рано или поздно это число будет напечатано машиной М_i, так что мы сразу узнаем, что число 10 входит в А. Если же число 10 не принадлежит множеству А, то в конце концов это число напечатает машина М_j — тем самым мы сразу узнаем, что число 10 не входит в А. Таким образом, в конечном итоге мы обязательно выясним, принадлежит ли число 10 множеству А или нет. (Понятно, что сказать заранее, сколько нам придется ждать, невозможно; нам известно лишь, что через какой-то конечный промежуток времени мы непременно узнаем ответ.)

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

Первое важное свойство генерирующих машин заключается в том, что можно сконструировать так называемую универсальную машину U, назначение к торой — систематически наблюдать за поведением во машин M₁, М₂, М₃…, М_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₁, М₂…, М_n… Это значит, что существует некоторая машина