Роджер Пенроуз - Новый ум короля: О компьютерах, мышлении и законах физики
42
Существует немало других известных в математике способов записи пар, троек и большего количества чисел в виде одного числа, но они менее удобны для наших целей. Например, формула ½((а + Ь)² + 3а + b) однозначно представляет пару (а, Ь) как одно натуральное число. Проверьте сами!
43
В изложенном выше я не вводил никакой метки для начала последовательности чисел (или инструкций и т. п.). Это совершенно не требуется для входных данных, поскольку все начинается в тот момент, когда считана первая единица. Однако для конечного результата может понадобиться что-то дополнительное, поскольку априори никто не может сказать, как долго придется двигаться по ленте, чтобы добраться до первой (т. е. самой левой!) единицы. Хотя при движении налево может встретиться длинная строка нулей, нет никаких гарантий, что еще дальше не встретится единица. В этом случае применимы различные подходы. Можно было бы всегда использовать специальную отметку (допустим, 6, записанную при помощи процедуры «сокращения»), чтобы указывать начало и завершение окончательного ответа. Но для простоты я в своем изложении буду придерживаться другой точки зрения, согласно которой мы всегда «знаем», сколько в действительности ленты обработало наше устройство (например, можно представить, что оно оставляет своего рода «след»), так что не обязательно просматривать ленту до бесконечности, чтобы убедиться в том, что весь ответ считан.
44
Один из способов записи информации с двух лент на одну — вставить записи одной из них между записями другой. При этом нечетные отметки на новой ленте могут соответствовать отметкам первой ленты, тогда как четные — отметкам второй. Аналогичная схема работает и для четырех, и для большего числа лент. «Неэффективность» этой процедуры обусловлена тем, что считывающему устройству пришлось бы «прыгать» взад-вперед по ленте, оставляя на ней маркеры как на четных местах, так и на нечетных, с тем чтобы фиксировать свое положение в каждый момент.
45
В согласии с предложенным здесь описанием, эта блок-схема была бы скорее частью «устройства», нежели внешнего окружения — «ленты». На ленте мы до сих пор отображали только числа А, В, А — В, и т. п Однако в дальнейшем нам потребуется также возможность описания и самого устройства в линейной одномерной форме. Как мы увидим далее в связи с универсальной машиной Тьюринга, есть тесная взаимосвязь между свойствами конкретного «устройства» и свойствами возможных «данных» (или «программы») для него. Поэтому удобно в обоих случаях придерживаться одномерной формы записи.
46
Эта процедура имеет отношение только к методу, который позволяет интерпретировать запись на ленте как натуральное число. Она не изменяет номера наших конкретных машин Тьюринга, таких как EUC и XN + 1.
47
Если Tn определена некорректно, то U будет действовать так, как если бы число, отвечающее n, обрывалось сразу по достижении последовательности из четырех или более единиц в двоичной записи n. Остаток выражения будет считан уже как число m, после чего устройство начнет совершать некие бессмысленные вычисления! От этого свойства можно при желании избавиться, если представлять n в расширенной двоичной форме. Я решил не делать этого, чтобы еще больше не усложнять описание несчастной универсальной машины Тьюринга!
48
Я благодарен Давиду Дойчу за то, что он нашел десятичную форму двоичного представления u, которое я привожу ниже. Я признателен ему также за проверку того факта, что это двоичное значение и действительно задает универсальную машину Тьюринга! Двоичная запись и выглядит следующим образом:
10000000010111010011010
00100101010110100011010
00101000001101010011010
00101010010110100001101
00010100101011010010011
10100101001001011101010
00111010101001001010111
01010100110100010100010
10110100000110100100000
10101101000100111010010
10000101011101001000111
01001010100001011101001
01001101000010000111010
10000111010100001001001
11010001010101101010010
10110100000110101010010
11010010010001101000000
00110100000011101010010
10101011101000010011101
00101010101010101110100
00101010111010000101000
10111010001010011010010
00010100110100101001001
10100100010110101000101
11010010010101110100101
00011101010010100100111
01010101000011010010101
01011101010010001011010
10000101101010001001101
01010101000101101001010
10010010110101001001011
10101010010101110101001
01001101010100001110100
01001001010111010101001
01011101010100000111010
10010000011010101010010
11101010010101101000100
10001110100000001110100
10100101010101110100101
00100101011101000001010
11101000010001110100000
10101001110100001010011
10100000100010111010001
00001110100001001010011
10100010000101101000101
00101110100010100101101
00100000101101000101010
01001101000101010101110
10010000011101001001010
10101110101010100110100
10001010110100100100101
10100000001011010000010
00110100000100101101000
00000011010010100010111
01001010100011010010100
10101101000001001110100
10101001011010010011101
01000000101011101010000
00110101010001010101101
00101010110101000010101
11010100100101011101010
00100101101010010000101
11010000001110101001000
10110101001010011010101
00010111010100101001011
10101010000010111010101
00000101110100000011101
01010000101011101001010
10110101010000101110101
00010101011101010100100
10111010101010000111010
10000000111010010010000
11010010010001011010101
01010011101000000001011
01001000011010101010100
10111010010000110100100
01010101110100001000111
01000100001110100001101
00000001011010000010010
11101010100101010110100
01000100101110100000100
11101010100110100000101
01011010000100001110100
10000100011101010101010
10011101000010010011101
00010010000111010000101
00101101000010100001110
10101010101011101000100
10011010001001001101010
01010010111010001000101
01110100000001110100010
01001011101001101001001
00001011010101010011010
00101000101110100001101
01000010001011010100110
10101001010010110101010
01101001001010111010011
01001000001011010001010
10100011101001000010101
10100000010011010010001
00101110100100001101010
00001001011101001001010
01101001001010101101001
10100100101001011010011
01001010000010110100100
00011101010010011010101
01000010111010010100001
01110100101010101110101
00010010110100100111010
01010100010111010001001
11010100001011010010011
10100101010101011101001
00011101001010101001011
10100100011101010000010
10101110011010100000101
10100100111010100000010
11101001011010100000101
01101001010010111010100
00100101110100001101010
00100001011010100110101
00010001011010101010010
11101010001010010110100
01010101011101001000010
10110101000101110101001
00101010111010101001001
01110101000111010100011
10101001001001011101010
00111010100101000101110
10100010111010100001001
01110101000111010001010
00101110100101001011101
01001010100101110100101
01010101011010100001010
10101101000010011101000
01010101010111010101000
10101110101010001010111
01000000111010101000100
10111010000001110101010
01000101110101000000110
10100001011010000001110
10010000001011101010001
11010100100010101110101
00110101010100010101101
00000110101010100101010
11010000001001101010101
00100111010100110101010
10010010110101001101001
00100111010000011010101
01010010101101010001001
10100010100101010111010
00001101010101010100101
10100010001110100010101
01010101101000100011101
00001010111010001001000
01110100110100000001001
11010000001001011101000
10001010011101000000100
10111010010101010100101
10100001010101011101000
10010100101110100000100
01011101010100101101000
10001001110100000100101
01110100000010101011010
00010001110011110100001
00000111010000100100111
01000001010010111010000
01010010110100001000101
01110100001000100110100
01000011101011110100001
00100101110100001001001
01110100000001010111010
00010101000110100010010
11101000010000011101000
01001110100010000010111
01010100101101000100000
10111010000101010101110
10000001010101110100010
00010101110100010000101
01110100100000111010100
10010011010000001010111
01000100010010111010101
00001110101001010110100
10101010000110100000101
00110100000001110100000
10010011101001011010010
00101001011010101001101
00010100100101101010100
11010001010100010110011
01010010010111010101001
10100010101010101100110
10100010101011001101001
00010101010111010001000
11101001001010101010110
10010100101000110100100
00001011101000001101010
10010101010110100101010
11010010001000101110100
01010101101010000010101
10100010000011010010001
01011010000100111010100
10101010101110100101101
00100100010101100110100
10010010101011101001101
00100100101011010010110
10010010010010110100101
10100100101000101100110
10010010100101011101000
10101110100100101110011
01001001010100101110011
01001010001010101110100
01000111010000101001011
01001010001011101001010
00101011010001001110100
10100010010111010001001
11010010100100010111001
10100100010001110100010
01110100101001010101110
01101001010000011100110
10101010101101000000011
10100101010010101011101
00100011101001010100101
01110011010000101001001
10011010100000110100000
00111010010101010010101
11001101010001000011010
00000011101000100101010
10111010001000111010101
01010101010110100001001
11010010001001010111010
01010100010011010100000
00101101001001110101000
01010111010010000110101
00000001011010010001110
10100100101110100001101
01000010101011010100010
11101010000101001011101
01000101110101000101010
10111001101010001010110
100001101010001001010
Пытливый читатель, вооруженный эффективным домашним компьютером, быть может захочет проверить, используя данные в тексте предписания и применяя эту последовательность к номерам различных простых машин Тьюринга, что она и в самом деле соответствует универсальной машине Тьюринга! Некоторое уменьшение величины и может быть достигнуто за счет другого определения машины Тьюринга. Например, мы могли бы отказаться от использования команды STOP и вместо этого применять правило остановки после того, как машина повторно возвращается во внутреннее состояние 0 из какого-либо другого внутреннего состояния. Это не дало бы нам значительного выигрыша (а может, и вовсе никакого). Большую пользу принесло бы использование лент с иными, нежели только 0 и 1, отметками. В литературе встречаются описания очень компактных на вид машин Тьюринга, но эта компактность обманчива, поскольку она обусловлена чрезмерно сложным кодированием описаний машин Тьюринга вообще.
