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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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