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

систему. Однако, сделать это напрямую и попытаться читать ленту просто как двоичное число мы не сможем. Дело в том, что мы не имеем возможности сказать, когда кончается двоичное представление числа и начинается бесконечная последовательность нулей справа, которая отвечает пустой ленте. Нам нужен способ как-то обозначать конец двоичной записи числа. Более того, часто нам будет нужно вводить в машину несколько чисел, как, например, в случае с алгоритмом Евклида, когда требуется пара чисел[42]. Но в двоичном представлении мы не можем отличить пробелы между числами от нулей или строчек нулей, входящих в записи этих двоичных чисел. К тому же, помимо чисел нам может понадобиться и запись всевозможных сложных инструкций на той же ленте. Для того чтобы преодолеть эти трудности, воспользуемся процедурой, которую я буду в дальнейшем называть сокращением и согласно которой любая строчка нулей и единиц (с конечным числом единиц) не просто считывается как двоичное число, но замещается строкой из нулей, единиц, двоек, троек и т. д. таким образом, чтобы каждое число в получившейся строчке соответствовало числу единиц между соседними нулями в исходной записи двоичного числа. Например, последовательность

01000101101010110100011101010111100110

превратится в

Мы теперь можем считывать числа 2, 3, 4… как метки или инструкции определенного рода. Действительно, пусть 2 будет просто «запятой», указывающей на пробел между двумя числами, а числа 3, 4, 5… могли бы по нашему желанию символизировать различные инструкции или необходимые обозначения, как, например, «минус», «плюс», «умножить», «перейти в позицию со следующим числом», «повторить предыдущую операцию следующее число раз», и т. п. Теперь у нас есть разнообразные последовательности нулей и единиц, разделенные цифрами большей величины. Эти последовательности нулей и единиц будут представлять собой обычные числа, записанные в двоичной форме. Тогда записанная выше строка (при замене двоек «запятыми») примет вид:

(двоичное число 1001) запятая (двоичное число 11) запятая….

Используя обычные арабские числа «9», «3», «4», «0» для записи соответствующих двоичных чисел 1001, 11, 100 и 0, получаем новую запись всей последовательности в виде: 9, 3, 4 (инструкция 3) 3 (инструкция 4) 0.

Такая процедура дает нам, в частности, возможность указывать, где заканчивается запись числа (и тем самым отделять ее от бесконечной полосы пустой ленты справа), просто используя запятую в конце этой записи. Более того, она позволяет закодировать любую последовательность натуральных чисел, записанных в двоичной системе, как простую последовательность нулей и единиц, в которой для разделения чисел мы используем запятые. Посмотрим, как это сделать, на конкретном примере. Возьмем последовательность