Машина тьюринга как универсальный исполнитель

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

Если попытаться сформулировать, что значит один исполнитель имитируется с помощью другого, то получится следующее. Говорят, что формальный исполнитель А имитирует формального исполнителя В, если:

— каждому объекту, над которым выполняет действия исполнитель В, однозначно соответствует объект, над которым выполняет действия исполнитель А (имитация среды исполнителя);

— каждому допустимому действию исполнителя В над тем или иным объектом среды однозначно сопоставлено допустимое действие исполнителя А над соответствующим объектом его среды (имитация действий);

— каждая инструкция, составленная для исполнителя В и приводящая при ее исполнении к определенному результату (т.е. к определенному состоянию среды исполнителя и него самого), может быть преобразована имитацией допустимых действий в инструкцию для исполнителя А, исполнение которой приводит к соответствующему результату в среде исполнителя А.

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

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

Примеры машины тьюринга

Д опустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова¹