5. Машины Тьюринга

Непосредственный анализ человеческих воможностей в области вычисления привел Поста [1] и Тьюринга [1] к введению определенного типа машин, которые должны имитировать действия человека-вычислителя.

Представим себе ленту, разделенную на ячейки и продолжимую в обоих направлениях сколь угодно далеко. Мы можем печатать на ней знаки возможно оставляя некоторые ячейки пустыми:

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

1 Напечатать а и перейти в состояние

2 Сдвинуться на одну ячейку влево и перейти в состояние

3 Сдвинуться на одну ячейку вправо и перейти в состояние

4 Остановиться.

Машина начинает работу в состоянии с начальными данными, напечатанными на ленте, и работает шаг за шагом в соответствии с приведенными правилами до тех пор, пока не остановится. Результат вычисления — это надпись, оставшаяся на ленте после того, как машина остановилась. Может случиться, что она никогда не остановится.

Мы говорим, что лента обозревается в стандартной позиции, если машина обозревает самый правый символ, напечатанный на ленте. Лента, изображенная выше, обозревается в стандартной позиции

Машина только что описанного типа называется машиной Тьюринга. Она следующим образом определяет частичную теоретико-числовую функцию (при не уменьшающем общности предположении, что Запустим машину, обозревающую в начальном состоянии число в стандартной позиции.

Если машина в конце концов останавливается, обозревая некоторое натуральное число в стандартной позиции, то это натуральное число и есть значение, принимаемое рассматриваемой функцией для аргумента Мы покажем, что вычисление, осуществляемое машиной Тьюринга, может быть с тем же успехом выполнено в канонической системе.

Если дана машина Тьюринга, мы можем найти частично рекурсивную функцию такую, что тогда и только тогда, когда рассматриваемая машина Тьюринга, запущенная в стандартной позиции, где она обозревает натуральное число в конце концов останавливается, обозревая натуральное число в стандартной позиции.

Следующая система Поста определяет искомую частично рекурсивную функцию:

знаки

вспомогательные знаки

переменные

производящие схемы

Для каждой конструкции первого типа мы добавляем схему

Аналогично инструкция второго типа порождает схему

инструкция третьего типа — схемы

инструкция четвертого типа — схемы

в зависимости от того, равно ли нулю или единице. Для инструкция типа 4 вообще не порождает схем.

Мы закончим этот пункт, приведя некоторые соображения в пользу того, что все возможные виды механических вычислений могут быть выполнены на машинах Тьюринга.

Должно быть ясно, что мы не наложим существенных ограничений, допустив, что производим наши вычисления обычным образом с помощью записей чернилами на листах бумаги. Эти листы мы берем настолько большими, чтобы те части наших вычислений, которые мы можем окинуть взглядом, умещались на

одном листе бумаги, лежащем перед нами. Результаты наших предшествующих усилий мы складываем в стопку около стола. Для числа конфигураций на бумаге, находящейся перед нами, которые мы способны отчетливо различить, должна иметься конечная граница, так как иначе нашлись бы сколь угодно мало различающиеся конфигурации. Наше действие в любой определенный момент должно определяться конфигурацией на бумаге перед нами и нашим состоянием ума. В расчет нужно принимать лишь конечное число состояний ума, так как в противном случае среди этих состояний были бы сколь угодно близкие, и это привело бы нас в замешательство. Далее, чтобы не запутаться в стопке бумаг, находящейся рядом с нами, мы пользуемся закладкой для указания положения в стопке того листа, который лежит перед нами. В зависимости от того, что написано на бумаге, лежащей перед нами, и состояния нашего ума мы предпринимаем действия двух возможных типов. Либо мы пишем что-нибудь на бумаге перед нами, либо мы кладем эту бумагу назад в стопку на место закладки и вынимаем из стопки другой лист для исследования. Снизу и сверху стопки подкладывается чистая бумага. Расстояние от закладки до листа, который мы собираемся вынуть, должно определяться конфигурацией на листе, лежащем перед нами, и нашим состоянием ума и тем самым имеет конечную границу. Сделав размер листов достаточно большим, мы можем допустить, что, меняя лист, лежащий перед нами, мы всегда кладем на его место один из соседних листов. Таким образом, ход вычисления разбит на последовательность элементарных действий того типа, который способна выполнять машина Тьюринга.