Универсальная машина Тьюринга

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

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

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

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

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

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

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

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

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

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

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