Новый ум короля: О компьютерах, мышлении и законах физики - Пенроуз Роджер. Страница 23
110111001,
как двоичное представление натурального числа (в десятичной форме это 441). Однако такая процедура даст нам только нечетные числа (их двоичное представление оканчивается на 1), тогда как нам нужна возможность представления всех натуральных чисел. Поэтому мы воспользуемся следующим несложным приемом — будем удалять последнюю единицу (которая принимается просто за маркер, обозначающий конец выражения) и считывать оставшуюся часть как двоичное число [46]. Тогда в последнем примере получим двоичное число
11011100,
которое соответствует десятичному числу 220. Эта процедура имеет то преимущество, что нуль также представляется непустой лентой, а именно:
… 0000001000000….
Рассмотрим, как действует машина Тьюринга Tn на некоторую (конечную) строку нулей и единиц на ленте, которая подается в устройство справа. Удобно рассматривать эту строку как двоичное представление некоторого числа, например m, в соответствии с приведенной выше схемой. Предположим, что после определенного числа шагов машина Tn в конце концов останавливается (т. е. доходит до команды STOP). Строка двоичных цифр, которые машина выписала к этому моменту на левой части ленты, и будет искомым результатом вычислений. Считывая эту последовательность в соответствии с той же схемой так же как двоичное представление некоторого числа, получим новое число, скажем, р. Тогда мы можем записать соотношение, выражающее тот факт, что результатом действия n-й машины Тьюринга Tn на число m является число p, следующим образом:
Tn(m)=p .
Взглянем на это соотношение с несколько иной точки зрения. Мы будем считать, что это выражение описывает некоторую специфическую операцию, которая применяется к паре чисел m и n для того, чтобы получить p. (Это означает: для заданных двух чисел n и m мы можем найти значение p, если введем m в n-ю машину Тьюринга.) Эта специфическая операция является полностью алгоритмической. Поэтому она может быть выполнена одной конкретной машиной Тьюринга U; иными словами, U, совершая действие над парой (n, m ), дает в результате p. Поскольку машина U должна производить операцию над обоими числами n и m, чтобы получить ответ, выражаемый одним числом p, то нам нужно придумать способ для записи пары (n, m) на одной ленте. С этой целью предположим, что n записывается в стандартной двоичной форме и заканчивается последовательностью 111110. (Вспомним, что двоичный номер всякой корректно определенной машины Тьюринга, — это последовательность символов, состоящая только из сочетаний вида 0, 10, 110, 1110 и 11110, поэтому он нигде не содержит более четырех единиц подряд. Таким образом, если Tn — корректно определенная машина, то появление последовательности 111110 действительно будет означать конец записи номера n.) Все, что следует за ней, должно быть просто записью числа m на ленте в соответствии с приведенными выше правилами (т. е. двоичное число m и строка 1000… непосредственно за ним). Таким образом, с этой второй частью ленты машина Tn и должна производить предполагаемые действия.
Если в качестве примера мы возьмем n =11 и m =6, то на ленте, вводимой в мащину U, мы будем иметь последовательность
000101111111011010000..
Она образована из следующих составляющих:
… 0000 (пустое начало ленты)
1011 (двоичное представление одиннадцати)
111110 (обозначает окончание числа n )
110 (двоичное представление шести)
10000… (остаток ленты)
То, что машина Тьюринга U должна была бы делать на каждом очередном шагу процедуры, выполняемой Tn над m — это исследовать структуру последовательности цифр в выражении n с тем, чтобы можно было произвести соответствующие изменения цифр числа m (т. е. «ленты» машины Tn ). В принципе, реализация такой машины не вызывает существенных затруднений (хотя и довольно громоздка на практике). Список ее собственных команд должен был бы просто содержать правила для чтения подходящей команды из «списка», закодированного в числе n, на каждом этапе выполнения действий над цифрами, считанными с «ленты», как они фигурируют в числе m. Можно предположить, что при этом совершалось бы значительное количество прыжков взад-вперед по ленте между цифрами, составляющими n и m, и выполнение процедуры было бы чрезвычайно медленным. Тем не менее, список команд подобной машины, несомненно, можно составить, и такая машина называется нами универсальной машиной Тьюринга. Обозначая ее действие на пару чисел (n, m ) через U(n, m ), мы получаем:
U(n, m ) = Тn(m )
при любых (n, m ), для которых Tn — корректно определенная машина Тьюринга [47]. Машина U, в которую первым вводится число n, в точности имитирует n-ю машину Тьюринга!
Поскольку U — машина Тьюринга, то она сама будет иметь номер. То есть, для некоторого числа u имеем
U = Tu.
Сколь велико u ? В сущности, мы можем положить, что u в точности равно следующему числу:
u =7244855335339317577
198395039615711237
952360672556559631
108144796606505059
404241090310483613
632359365644443458
382226883278767626
556144692814117715
017842551707554085
657689753346356942
478488597046934725
739988582283827795
294683460521061169
835945938791885546
326440925525505820
555989451890716537
414896033096753020
431553625034984529
832320651583047664
142130708819329717
234151056980262734
686429921838172157
333482823073453713
421475059740345184
372359593090640024
321077342178851492
760797597634415123
079586396354492269
159479654614711345
700145048167337562
172573464522731054
482980784965126988
788964569760906634
204477989021914437
932830019493570963
921703904833270882
596201301773727202
718625919914428275
437422351355675134
084222299889374410
534305471044368695
876405178128019437
530813870639942772
823156425289237514
565443899052780793
241144826142357286
193118332610656122
755531810207511085
337633806031082361
675045635852164214
869542347187426437
544428790062485827
091240422076538754
264454133451748566
291574299909502623
009733738137724162
172747723610206786
854002893566085696
822620141982486216
989026091309402985
706001743006700868
967590344734174127
874255812015493663
938996905817738591
654055356704092821
332221631410978710
814599786695997045
096818419062994436
560151454904880922
084480034822492077
304030431884298993
931352668823496621
019471619107014619
685231928474820344
958977095535611070