Этюды для программистов

13. Тур до Тьюрингу, или Моделирование машины Тьюринга

Задолго до появления первых универсальных цифровых вычислительных машин вопрос об ограничениях на вычисления, которые могли бы выполнять машины, заинтересовал Алана Тьюринга. Чтобы быть уверенным, что мощь его гипотетической машины не обусловлена каким-либо хитрым механизмом, Тьюринг исключил почти все возможности, которые существенны для реальных компьютеров. Осталась лишь программная память простого вида, не допускающая изменений во время выполнения, только один тип команд и простая лента для ввода и вывода. Тем не менее это устройство — машина Тьюринга, предмет обожания студентов-логиков в последние 40 лет — способно повторить все вычисления любого современного цифрового компьютера. Но какой мерзкой была бы задача промоделировать, скажем, IBM 370/155 на машине Тьюринга! К счастью, перед нами стоит куда более приятная обратная задача.

Машина Тьюринга состоит из устройства управления, которое с помощью головки связано с лентой ввода/вывода. Лента — это длинная полоска, разделенная на ячейки, каждая из которых может содержать одну литеру; лента простирается вправо до бесконечности (иными словами, на правом конце ленты находится небольшая фабрика, производящая по мере необходимости дополнительную ленту). Головка указывает на какую-то одну ячейку ленты и может читать содержимое ячейки, записывать и перемещаться вправо или влево. В начале работы исходные данные всегда заполняют левую часть ленты, а головка читает самую левую ячейку ленты. Когда головка, двигаясь вправо, достигает ячейки, которая не является частью исходных данных и никогда ранее не обозревалась головкой, считается, что в этой ячейке записан пробел, обозначаемый ø.

Устройство управления выполняет программу, подчиняясь строгим правилам. В любой момент времени устройство управления находится в некотором состоянии, которое записано в регистре текущее состояние. Состояния обозначаются положительными целыми числами. Каждая команда программы представляет собой пятерку, составленную из состояния, литеры, еще одного состояния, еще одной литеры и направления движения ленты. Цикл выполнения команды начинается с того, что устройство управления сравнивает текущее состояние и литеру на ленте под головкой с первыми двумя компонентами всех команд. По правилам программирования для машины Тьюринга в программе может быть не более одной пятерки с какой-либо определенной начальной парой состояние-литера (но может и не быть ни одной). Когда совпадение найдено, устройство управления выполняет три действия: в ячейку ленты под головкой записывается литера, являющаяся четвертой компонентой пятерки; головка передвигается на одну ячейку влево или вправо или остается на месте, как указано в пятой компоненте пятерки; текущее состояние заменяется на третью компоненту. После этого машина готова к следующему циклу. По соглашению, работа начинается в состоянии 1 при описанном выше состоянии ленты. Машина останавливается, если в цикле выполнения не удается найти совпадения с текущей парой состояние-литера или если головка выходит за левый край ленты; при этом результатом работы считается все, что остается на ленте после остановки. Отметим, что программа может содержать лишь конечное число команд, так что для любой программы осмысленно только конечное число состояний и литер.

Для пояснения изложения полезно привести пример. Пусть мы хотим написать программу для машины Тьюринга, которая будет строить сумму двух целых чисел. Целое число п будет изображаться на ленте n последовательными значками * (отсутствие звездочек соответствует нулю), два исходных числа будут разделены запятой, и если исходные данные представляют n + m, то результатом должны быть n + m звездочек, расположенных у левого края ленты. Так, чтобы вычислить 7 + 4, следует записать в качестве исходных данных

*******,****

результатом должно быть

***********

Структура программы проста. Сначала головка движется вправо в поисках запятой (не забывайте, что первоначально головка стоит над крайней левой ячейкой исходных данных). Запятая заменяется звездочкой, и головка продолжает движение, отыскивая пробел, ограничивающий справа исходные данные. Головка возвращается на одну ячейку назад и записывает пробел на место находящейся там звездочки, после чего программа завершается. Легко видеть, что при построении суммы одна звездочка добавляется в середине и одна убирается с правого края. Программа приведена в табл. 13.1.

Таблица 13.1. Программа для машины Тьюринга
Старое состояние	Старая литера	Новое состояние	Новая литера	Перемещение
1	*	1	*	Вправо
1	,	2	*	»
1	ø	4	ø	На месте
2	*	2	*	Вправо
2	,	4	ø	На месте
2	ø	3	ø	Влево
3	*	3	ø	На месте
4	ø	4	ø	» »