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

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

Формальное определение

Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т. п.; обозначим этот машинный алфавит как $\Sigma _{1}$. Тогда универсальной машиной Тьюринга U для класса машин с алфавитом $\Sigma _{2}$ и k входными лентами называется машина Тьюринга с k+1 входной лентой и алфавитом $\Sigma _{1}\cup \Sigma _{2}$ такая, что если подать на первые k лент входное значение, а на k+1 — правильно записанный код некоторой машины Тьюринга $M_{1}$, то U выдаст тот же ответ, какой выдала бы на этих входных данных $M_{1}$, или будет работать бесконечно долго, если $M_{1}$ на этих данных не остановится.

Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (то есть если исходная машина произвела t шагов, то универсальная произведёт не более ct²). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана Тьюрингом в 1947 г.

См. также

• Машина Поста
• JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата