Универсальная машина Тьюринга — Википедия

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

Формальное определение[править | править код]

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

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