110111001,

как двоичное представление натурального числа (в десятичной форме это 441). Однако такая процедура даст нам только нечетные числа (их двоичное представление оканчивается на 1), тогда как нам нужна возможность представления всех натуральных чисел. Поэтому мы воспользуемся следующим несложным приемом — будем удалять последнюю единицу (которая принимается просто за маркер, обозначающий конец выражения) и считывать оставшуюся часть как двоичное число[46]. Тогда в последнем примере получим двоичное число

11011100,

которое соответствует десятичному числу 220. Эта процедура имеет то преимущество, что нуль также представляется непустой лентой, а именно:

… 0000001000000….

Рассмотрим, как действует машина Тьюринга 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

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