Новый ум короля: О компьютерах, мышлении и законах физики

Рассмотрим, как действует машина Тьюринга  T_nна некоторую (конечную) строку нулей и единиц на ленте, которая подается в устройство справа. Удобно рассматривать эту строку как двоичное представление некоторого числа, например m, в соответствии с приведенной выше схемой. Предположим, что после определенного числа шагов машина  T_nв конце концов останавливается (т. е. доходит до команды STOP). Строка двоичных цифр, которые машина выписала к этому моменту на левой части ленты, и будет искомым результатом вычислений. Считывая эту последовательность в соответствии с той же схемой так же как двоичное представление некоторого числа, получим новое число, скажем, р. Тогда мы можем записать соотношение, выражающее тот факт, что результатом действия n-ймашины Тьюринга  T_nна число mявляется число p, следующим образом:

T_n(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, поэтому он нигде не содержит более четырех единиц подряд. Таким образом, если  T_n— корректно определенная машина, то появление последовательности 111110 действительно будет означать конец записи номера n.) Все, что следует за ней, должно быть просто записью числа mна ленте в соответствии с приведенными выше правилами (т. е. двоичное число mи строка 1000… непосредственно за ним). Таким образом, с этой второй частью ленты машина  T_nи должна производить предполагаемые действия.

Если в качестве примера мы возьмем n=11 и m=6, то на ленте, вводимой в мащину U, мы будем иметь последовательность

000101111111011010000..

Она образована из следующих составляющих:

… 0000 (пустое начало ленты)

1011 (двоичное представление одиннадцати)

111110 (обозначает окончание числа n)

110 (двоичное представление шести)

10000… (остаток ленты)

То, что машина Тьюринга Uдолжна была бы делать на каждом очередном шагу процедуры, выполняемой  T_nнад m— это исследовать структуру последовательности цифр в выражении nс тем, чтобы можно было произвести соответствующие изменения цифр числа m(т. е. «ленты» машины T_n). В принципе, реализация такой машины не вызывает существенных затруднений (хотя и довольно громоздка на практике). Список ее собственных команд должен был бы просто содержать правила для чтения подходящей команды из «списка», закодированного в числе n, на каждом этапе выполнения действий над цифрами, считанными с «ленты», как они фигурируют в числе m. Можно предположить, что при этом совершалось бы значительное количество прыжков взад-вперед по ленте между цифрами, составляющими nи m, и выполнение процедуры было бы чрезвычайно медленным. Тем не менее, список команд подобной машины, несомненно, можно составить, и такая машина называется нами универсальноймашиной Тьюринга. Обозначая ее действие на пару чисел (n, m) через U( n, m), мы получаем:

U( n, m) = Т_n( m)

при любых ( n, m), для которых  T_n— корректно определенная машина Тьюринга [47]. Машина U, в которую первым вводится число n, в точности имитирует n-ю машину Тьюринга!

Поскольку U— машина Тьюринга, то она сама будет иметь номер. То есть, для некоторого числа uимеем

U= T_u.

Сколь велико 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