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

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

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

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