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

Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т. п.; обозначим этот машинный алфавит как ${\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 кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата

Для улучшения этой статьи по информационным технологиям желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.