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