Систему команд машины Тьюринга можно интерпретировать как описание работы некоторого устройства или как программу. До сих пор мы воспринимали машину Тьюринга как программу, выступая в роли некоторого устройства, интерпретирующего эту программу. Все ли одинаково выполняют эту интерпретацию? Не значит ли это, что существует некоторый алгоритм (машина Тьюринга), который выполняет те же действия, что и произвольная машина Тьюринга?
ТЕОРЕМА 2.2. Об универсальной машине Тьюринга.
Универсальная машина Тьюринга существует или любую вычислимую по Тьюрингу функцию можно реализовать на универсальной машине Тьюринга.
ДОКАЗАТЕЛЬСТВО.
A. ЛEMA О правой полуленте.
Для произвольной машины Тьюринга существует эквивалентная ей машина Тьюринга, которая работает только на правой полуленте.
ДОКАЗАТЕЛЬСТВО.
Доказательство основано на таком преобразовании системы команд исходной машины Тьюринга при котором любая команда вида приводит к смещению всего того, что записано на правой полуленте в право на одну ячейку с занесением в образовавшуюся ячейку знака заполнителя ленты, если эта команда приводит к выходу устройства доступа за границу полуленты.
Существует машина Тьюринга, выполняющая это преобразование системы команд исходной системы команд машины Тьюринга.
Окончание доказательства.
B. Пусть есть универсальная машина Тьюринга, реализующая систему команд любой другой машины Тьюринга . Мы должны не ленте записать , где знак показывает границу раздела полуленты, — строка, записанная на ленте после остановки машины Тьюринга . Если — начальная конфигурация машины Тьюринга , то есть вычислимая по Тьюрингу функция, построенная для множества строк в алфавите ленты машины Тьюринга .
C. В таком виде как в пункте В доказательства машина Тьюринга существовать не может. Необходимо выбрать алфавит такой, что бы он содержал всевозможные знаки алфавитов любой наперед неизвестной машины Тьюринга. Так как для любого знака можно привести знак, отличный от него, и конечное множество других, то мощность алфавита счетна, а следовательно универсальной машины Тьюринга не существует, так как она должна иметь конечный алфавит. Следовательно систему команд машины Тьюринга нельзя просто записать на ленту. Выход заключается в кодировании алфавитов машины Тьюринга в алфавите универсальной машины Тьюринга .
D. Проведем кодирование алфавитов некоторой машины Тьюринга в алфавите универсальной машины Тьюринга.
Пусть есть код, задающий отображение знаков моделируемой машины Тьюринга в стоки алфавита следующим образом.
Это преобразование взаимно однозначное.
E. Уточним постановку задачи построения универсальной машины Тьюринга. Необходимо записать на ленте следующее , где . Алфавит универсальной машины Тьюринга состоит из следующих знаков , где система команд машины Тьюринга предварительно преобразована для работы с правой полулентой.
F. При такой постановке задачи легко может быть построена универсальная машина Тьюринга при произвольных и , то есть построенная машина Тьюринга работает независимо от длины кодовых последовательностей и , так как поиск знака на левой полуленте не зависит от числа знаков, которыми закодированы .
Окончание доказательства.
Замечание. Шенноном доказана теорема о том, что существует универсальная машина Тьюринга, имеющая два состояния .
Замечание. Боброу и Минский показали, что не существует универсальной машины Тьюринга с двумя состояниями и двумя знаками алфавита.
