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

Тьюринг представлял внешние данные и объем для хранения информации в виде «ленты» с нанесенными на нее метками. Устройство по мере необходимости могло обращаться к этой ленте, «считывать» с нее информацию и перемещать ее вперед или назад в ходе выполнения операций. Помимо этого, устройство могло ставить новые метки на ленту и стирать с нее старые, что позволяло использовать одну и ту желенту и как внешнюю память (то есть «черновик»), и как источник входных данных. На самом деле, не стоило бы проводить явное различие между этими двумя понятиями, поскольку во многих операциях промежуточные результаты вычислений могут играть роль новых исходных данных. Вспомним, что при использовании алгоритма Евклида мы раз за разом замещали исходные числа ( Аи В) результатами, полученными на разных этапах вычислений. Сходным образом та же самая лента может быть использована и для вывода окончательного результата («ответа»). Лента будет двигаться через устройство туда-сюда до тех пор, пока выполняются вычисления. Когда, наконец, все вычисления закончены, устройство останавливается, и результат вычислений отображается на части ленты, лежащей по одну сторону от устройства. Для определенности будем считать, что ответ всегда записывается на части ленты, расположенной слева от устройства, а все исходные числовые данные и условия задачи — на части ленты, расположенной справа от него.

Меня всегда несколько смущало представление о конечном устройстве, которое двигает потенциально бесконечную ленту вперед и назад. Неважно, насколько легок материал ленты — сдвинуть бесконечнуюленту все-таки будет трудно! Вместо этого я предпочитаю представлять себе эту ленту как некое окружение, по которому может перемещаться наше конечное устройство. (Конечно же, в современных электронных устройствах ни «лента», ни само «устройство» не должны в обычном смысле физически «перемещаться», но представление о таком «движении» позволяет достичь известной наглядности.) При таком подходе устройство получает все входные данные из этого окружения, использует его в качестве «черновика» и, наконец, записывает в него конечный результат.

В представлении Тьюринга «лента» состоит из бесконечной в обоих направлениях линейной последовательности квадратов. Каждый квадрат либо пуст, либо помечен [41]. Использование помеченных и пустых квадратов означает, что мы допускаем разбиение нашего «окружения» (т. е. ленты) на части и возможность его описания множеством дискретныхэлементов (в противоположность непрерывному описанию). Это представляется вполне разумным, если мы хотим, чтобы наше устройство работало надежно и совершенно определенным образом. В силу используемой математической идеализации мы допускаем (потенциальную) бесконечность «окружения», однако в каждом конкретномслучае входные данные, промежуточные вычисления и окончательный результат всегда должны быть конечными. Таким образом, хотя лента и имеет бесконечную длину, на ней должно быть конечное число непустых квадратов. Другими словами, и с той, и с другой стороны от устройства найдутся квадратики, после которых лента будет абсолютно пустой. Мы обозначим пустые квадраты символом « 0», а помеченные — символом « 1», например:

Нам нужно, чтобы устройство «считывало» информацию с ленты. Мы будем считать, что оно считывает по одномуквадрату за раз и смещается после этого ровно на одинквадрат влево или вправо. При этом мы не утрачиваем общности рассуждений: устройство, которое читает за один раз nквадратов или перемещается на kквадратов, легко моделируется устройством, указанным выше. Передвижение на kквадратов можно построить из к перемещений по одному квадрату, а считывание nквадратов за один прием сводится к запоминанию результатов nоднократных считываний.

Что именно может делать такое устройство? Каким образом в самом общем случае могло бы функционировать устройство, названное нами «механическим»? Вспомним, что число внутренних состоянийнашего устройства должно быть конечным. Все, что нам надо иметь в виду помимо этого — это то, что поведение нашего устройства полностью определяется его внутренним состоянием и входными данными. Входные данные мы упростили до двух символов — « 0»и « 1». При заданном начальном состоянии и таких входных данных устройство должно работать совершенно определенным образом: оно переходит в новое состояние (или остается в прежнем), заменяет считанный символ 0или 1тем же или другим символом 1или 0, передвигается на один квадрат вправо или влево, и наконец, оно решает, продолжить вычисления или же закончить их и остановиться.

Чтобы явно определить операции, производимые нашим устройством, для начала пронумеруем его внутренние состояния, например: 0,1,2,3,4,5. Тогда действия нашего устройства, или машины Тьюринга, полностью определялись бы неким явным списком замен, например:

0 0 -> 0 0R

0 1 -> 13 1L

1 0 -> 65 1R

1 1 -> 1 0R

2 0 -> 0 1R.STOP

2 1 -> 66 1L

3 0 -> 37 0R

• •

• •

• •

210 0 -> 3 1L

• •

• •

• •

2581 -> 0 0R.STOP

2590 -> 97 1R