Машина Тьюринга: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 171:
{{Рамка}}
 
== Универсальная машина Тьюринга ==
 
Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т.п.; обозначим этот машинный алфавит как <math>\Sigma_1</math>. Тогда универсальной машиной Тьюринга ''U'' для класса машин с алфавитомсать). <math>\Sigma_2</math>Теорема ибыла ''k'' входными лентами называется машина Тьюринга с ''k+1'' входной лентойпредложена и алфавитомдоказана <math>\Sigma_1 \cup \Sigma_2</math> такая[[w:Тьюринг, что если подать на первые ''k'' лент входное значение, а на ''k+1'' — правильно записанный код некоторый машины Тьюринга <math>M_1</math>, то ''U'' выдаст тот же ответ, какой выдала бы на этих входных данных <math>M_1</math>, или будет работать бесконечно долго, если <math>M_1</math> на этихАлан|Тьюрингом]] данныхв не[[w:1947|1947]] остановитсяг.
'''Универсальной машиной Тью́ринга''' называют [[w:машина Тьюринга|машину Тьюринга]], которая может заменить собой любую машину Тьюринга. Получив на вход программу и входные данные, она вычисляет ответ, который вычислила бы по входным данным машина Тьюринга, чья программа была дана на вход.
 
=== Формальное определение ===
 
Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т.п.; обозначим этот машинный алфавит как <math>\Sigma_1</math>. Тогда универсальной машиной Тьюринга ''U'' для класса машин с алфавитом <math>\Sigma_2</math> и ''k'' входными лентами называется машина Тьюринга с ''k+1'' входной лентой и алфавитом <math>\Sigma_1 \cup \Sigma_2</math> такая, что если подать на первые ''k'' лент входное значение, а на ''k+1'' — правильно записанный код некоторый машины Тьюринга <math>M_1</math>, то ''U'' выдаст тот же ответ, какой выдала бы на этих входных данных <math>M_1</math>, или будет работать бесконечно долго, если <math>M_1</math> на этих данных не остановится.
 
Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (т.е. если исходная машина произвела ''t'' шагов, то универсальная произведёт не более ''ct<sup>2</sup>''). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана [[w:Тьюринг, Алан|Тьюрингом]] в [[w:1947|1947]] г.
{{Акмар}}