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 ), мы получаем: