Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.08.2022


13.08.2022


13.08.2022


13.08.2022


12.08.2022





Яндекс.Метрика





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

16.07.2022

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

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

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

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