|
Стр. 215 мы ни ждали, у нас никогда не будет уверенности, что через какое-то время машина все-таки не напечатает число 10. Итак, если число 10 принадлежит множеству А, то рано или поздно мы узнаем об этом; если же число 10 не принадлежит А, то мы никогда не будем знать об этом наверняка (во всяком случае, если ограничимся наблюдением за машиной М,). Такое множество А можно с основанием называть полуразрешимым. Первое важное свойство генерирующих машин заключается в том, что можно сконструировать так называемую универсальную машину U, назначение к торой — систематически наблюдать за поведением во машин m1, М2, М3, ... , Мn, ... и, как только машина Мх напечатает число у, сразу же сообщить нам об этом. Но каким образом это сделать? Очень просто— напечатать некоторое число, скажем для данных х и у напечатать х* у, то есть число, как и ранее, состоящее из цепочки единиц длиной х, за которой следует цепочка нулей длиной у. Итак, основная команда для машины U такова: когда машина М* напечатает число у, то напечатать число х* у. Допустим, например, что машина Ма запрограммирована на генерирование множества нечетных чисел, а машина Мb—на генерирование множества четных чисел. Тогда машина U будет печатать числа а*1, а*3, а*5 и т.д., а также числа b*2, b*4, b*8 и т.д., однако она никогда не напечатает число а*4 (поскольку машина Ма никогда не напечатает число 4) или число b*3 (поскольку машина Мb никогда не напечатаем число 3). Далее, поскольку машина U имеет свою собственную программу, то, следовательно, она входит в семейство программируемых машин М1 М2, ..., Мn, ... . Это значит, что существует некоторая машина Мь номер программы которой k совпадает с номером программы машины U, причем машина М* и есть сама машина U! (В строгой научной статье я указал бы, что это за число k.) Можно заметить, что наша универсальная машина Mk наблюдает в числе прочих и за своим собственным поведением. Поэтому, как только машина Мk напечата Стр. 216 ет число n, она должна напечатать число k* n, а значит, и число k* (k* n), а также и число k* [k* (k* n)] и т. д. Другой важной особенностью этих машин является то, что, имея произвольную машину Мa, мы всегда можем запрограммировать другую машину Mb, таким образом, чтобы она печатала в точности такие числа х, при которых машина Мa, печатает числа х * х. (Машина Mb, так сказать, «следит» за машиной Мa и действует но такой команде: напечатать число х после того, как машина Мa напечатает число х* х.) Можно, наконец, закодировать программы так, что для каждого а таким числом b окажется число 2а; тогда для каждого а машина М2а будет печатать в точности такие числа х, при которых машина Мa печатает числа х*х. Представим себе, что мы так и устроили, и запишем два основных утверждения, на которые будем опираться в дальнейшем. — 135 —
|