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

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

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

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

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

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

***********

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

Чтобы изобразить состояние машины Тьюринга, можно напечатать все ячейки ленты, которые когда-либо рассматривались, и среди них — текущее состояние непосредственно слева от ячейки, находящейся под головкой в данный момент; такой способ мы будем считать стандартным. Мы получаем моментальный снимок; следующий пример показывает начало сложения 2 и 3:

1**,***

На рис. 13.1 показана последовательность моментальных снимков для всего вычисления. Отметим, что программа останавливается в состоянии 3, поскольку в ней не предусмотрены действия для пробела. Состояние 4 возникает только, если в исходных данных имеется ошибка; в этом случае машина попадает в бесконечный цикл. Убедитесь, что программа работает, если любое из исходных чисел (или оба) равно нулю.

Рисунок 13.1. Последовательность моментальных снимков.

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

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

Хотя в нашем описании именами состояний были положительные целые числа, ваш имитатор должен допускать в качестве имени состояния произвольный идентификатор. В предыдущем примере мы могли бы назвать состояния Начало, ДвижениеВправо, Конец и Ошибка, тогда одна из команд могла бы иметь вид

ДвижениеВправо ø Конец ø Влево

Теперь у нас нет выделенного первого состояния, поэтому его должен указать пользователь.

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

Трассировочная информация должна печататься после каждого изменения состояния. Она должна включать в себя: содержимое всей ленты до самого правого непробела или до головки, в зависимости от того, что находится правее, положение головки и текущее состояние. Вероятно, содержимое ленты следует напечатать на одной строке, а указатель головки и состояние — на следующей. Руководствуйтесь соображениями красоты и ясности. Алфавит ленты, т. е. множество символов, которые могут появляться на ленте, есть просто набор литер, встречающихся где-либо во второй или четвертой компоненте пятерки. Программа должна позволять использовать любую нормальную литеру, имеющуюся в вашей системе. В алфавит всегда входит пробел. Его непросто изобразить в исходных данных, а появляясь в выходной строке, пробелы могут вносить неразбериху. Проблему с вводом можно обойти, если, например, разделять пять компонент команды запятыми. Работа со значащими пробелами часто вызывает затруднения. В естественных языках пробелы осмысленны, но обычно лишь как разделители слов, а не как полноправные символы. Таким образом не существует какого-либо стандартного соглашения об употреблении пробелов в качестве символов.

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

Длительность исполнения. Одному исполнителю на 1 неделю.

Литература

Дэвис (Davis M.). Computability and Unsolvability, McGraw-Hill, New York, NY, 1958.

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

Хопкрофт, Ульман (Hopcroft J. E., Ullman J. D). Formal Languages and Their Relation to Automata. Addison-Wesley, Reading, MA, 1969.

Книга Хопкрофга и Ульмана — наилучший в своей области учебник для аспирантов первого года обучения. В ней содержатся все основные результаты о машинах Тьюринга, причем они излагаются в контексте других классов автоматов Книга полезна также своей обширной библиографией.

Минский (Minsky M. L.). Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs NJ, 1967.

Минский дает прекрасное, легко воспринимаемое введение в теорию автоматов. Это, вероятно, наиболее подходящая книга для первого знакомства с предметом.

* Трахтенброт Б. А. Алгоритмы и вычислительные автоматы. — М.: Советское радио, 1974.