Тема. Напишите универсальный имитатор машины Тьюринга. Входными данными будут: программа для машины Тьюринга, ее исходные данные и (по причине, которая будет объяснена позже) начальное состояние машины. Результатом должны быть трассировка работы машины и ее окончательное состояние. Поскольку машина Тьюринга вовсе не всегда останавливается, причем заранее нельзя предсказать, остановится она или нет (если вы не понимаете, почему это так, обратите внимание на проблему остановки), необходимо как-то контролировать объем печати имитатора и расходуемое им время. Проверьте имитатор на нескольких программах, аналогичных рассмотренным выше.
Хотя в нашем описании именами состояний были положительные целые числа, ваш имитатор должен допускать в качестве имени состояния произвольный идентификатор. В предыдущем примере мы могли бы назвать состояния Начало, ДвижениеВправо, Конец и Ошибка, тогда одна из команд могла бы иметь вид
ДвижениеВправо ø Конец ø Влево
Теперь у нас нет выделенного первого состояния, поэтому его должен указать пользователь.
Указания исполнителю. При разработке данной программы, как и любого имитатора, перед нами стоит проблема эффективности. Если на протяжении всего выполнения используются имена состояний, то постоянно требуемый поиск займет значительное время. Скорость выполнения будет наибольшей, если представить программу для машины Тьюринга в виде двумерного массива, индексами в котором будут состояния и литеры. Элементы массива содержат команду, которую нужно выполнить; элемент специального вида указывает, что соответствующая пятерка отсутствует. Тут, конечно, определенную трудность представляет незнание необходимого размера этого массива до того, как будут прочитаны исходные данные. Отметим также, что необходимо проверить непротиворечивость исходных данных, т. е, убедиться, что никакие две пятерки не начинаются одной и той же парой состояние-литера.
Трассировочная информация должна печататься после каждого изменения состояния. Она должна включать в себя: содержимое всей ленты до самого правого непробела или до головки, в зависимости от того, что находится правее, положение головки и текущее состояние. Вероятно, содержимое ленты следует напечатать на одной строке, а указатель головки и состояние — на следующей. Руководствуйтесь соображениями красоты и ясности. Алфавит ленты, т. е. множество символов, которые могут появляться на ленте, есть просто набор литер, встречающихся где-либо во второй или четвертой компоненте пятерки. Программа должна позволять использовать любую нормальную литеру, имеющуюся в вашей системе. В алфавит всегда входит пробел. Его непросто изобразить в исходных данных, а появляясь в выходной строке, пробелы могут вносить неразбериху. Проблему с вводом можно обойти, если, например, разделять пять компонент команды запятыми. Работа со значащими пробелами часто вызывает затруднения. В естественных языках пробелы осмысленны, но обычно лишь как разделители слов, а не как полноправные символы. Таким образом не существует какого-либо стандартного соглашения об употреблении пробелов в качестве символов.
Инструментовка. Эта задача представляет собой еще один случай, когда почти любой язык имеет как достоинства, так и недостатки; следует, однако, избегать интерпретативных языков ввиду малого размера внутреннего цикла.
Длительность исполнения. Одному исполнителю на 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.
Книга Хопкрофта и Ульмана — наилучший в своей области учебник для аспирантов первого года обучения. В ней содержатся все основные результаты о машинах Тьюринга, причем они излагаются в контексте других классов автоматов Книга полезна также своей обширной библиографией.