До сих пор мы придерживались той точки зрения, что различные алгоритмы осуществляются на различных машинах Тьюринга, отличающихся набором команд, внутренним и внешним алфавитами. Однако можно построить универсальную машину Тьюринга, способную в известном смысле выполнять любой алгоритм, а значит, способную выполнять работу любой машины Тьюринга.
В универсальной машине Тьюринга, как и во всякой Тьюринговой машине, информация изображается символами, расположенными одновременно на магнитной ленте. При этом универсальная машина Тьюринга может располагать лишь фиксированным конечным внешним алфавитом. Между тем она должна быть приспособлена к приему в качестве исходной информации всевозможных состояний устройства управления и конфигураций, в которых могут встречаться буквы из разнообразных алфавитов со сколь угодно большим числом различных букв.
Это достигается путем кодирования конфигурации и программы любой данной машины Тьюринга в символах входного (внешнего) алфавита универсальной машины. Само кодирование должно выполняться следующим образом:
1) различные буквы должны заменяться различными кодовыми группами, но одна и та же буква должна заменяться всюду, где бы она ни встречалась, одной и той же кодовой группой;
2) строки кодовых записей должны однозначным образом разбиваться на отдельные кодовые группы;
3) должна иметь место возможность распознать, какие кодовые группы соответствуют различным сдвигам, т. е. каждой из букв Л, П, С в отдельности, и различать кодовые гру 2>Таким образом, если какая-либо машина Тьюринга Т решает некоторую задачу, то и универсальная машина Тьюринга способна решить эту задачу при условии, что кроме кодов исходных данных этой задачи на ее ленту будет подан код программы машины Т. Задавая универсальной машине Тьюринга Тu изображение программы любой данной машины Тьюринга Тn и изображение любого ее входного слова xn, получим изображение выходного слова уn, в которое машина Тn переводит слово xn.
Если же алгоритм, реализуемый машиной Тn, не применим к слову xn, то алгоритм, реализуемый универсальной машиной Тu, также не применим к слову, образованному из изображения xn и программы машины Тn.
Таким образом, машина Тьюринга Тn может рассматриваться как одна из программ для универсальной машины Tu.
В связи с существованием универсальной тьюринговой машины таблицы соответствия, описывающие различные состояния устройства управления машины, имеют двоякое назначение:
1) для описания состояний устройства управления специальной машины Тьюринга, реализующей соответствующий алгоритм;
2) для описания программы, подаваемой на ленту универсальной машины Тьюринга, при реализации соответствующего алгоритма.
Современные электронные вычислительные машины строятся как универсальные; в запоминающее устройство наряду с исходными данными поставленной задачи вводится также и программа ее решения.