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

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

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

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

См. также

• JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата

Отрывок, характеризующий Универсальная машина Тьюринга

– Непременно надо перенести на кровать, здесь никак нельзя будет…
Больного так обступили доктора, княжны и слуги, что Пьер уже не видал той красно желтой головы с седою гривой, которая, несмотря на то, что он видел и другие лица, ни на мгновение не выходила у него из вида во всё время службы. Пьер догадался по осторожному движению людей, обступивших кресло, что умирающего поднимали и переносили.
– За мою руку держись, уронишь так, – послышался ему испуганный шопот одного из слуг, – снизу… еще один, – говорили голоса, и тяжелые дыхания и переступанья ногами людей стали торопливее, как будто тяжесть, которую они несли, была сверх сил их.
Несущие, в числе которых была и Анна Михайловна, поровнялись с молодым человеком, и ему на мгновение из за спин и затылков людей показалась высокая, жирная, открытая грудь, тучные плечи больного, приподнятые кверху людьми, державшими его под мышки, и седая курчавая, львиная голова. Голова эта, с необычайно широким лбом и скулами, красивым чувственным ртом и величественным холодным взглядом, была не обезображена близостью смерти. Она была такая же, какою знал ее Пьер назад тому три месяца, когда граф отпускал его в Петербург. Но голова эта беспомощно покачивалась от неровных шагов несущих, и холодный, безучастный взгляд не знал, на чем остановиться.
Прошло несколько минут суетни около высокой кровати; люди, несшие больного, разошлись. Анна Михайловна дотронулась до руки Пьера и сказала ему: «Venez». [Идите.] Пьер вместе с нею подошел к кровати, на которой, в праздничной позе, видимо, имевшей отношение к только что совершенному таинству, был положен больной. Он лежал, высоко опираясь головой на подушки. Руки его были симметрично выложены на зеленом шелковом одеяле ладонями вниз. Когда Пьер подошел, граф глядел прямо на него, но глядел тем взглядом, которого смысл и значение нельзя понять человеку. Или этот взгляд ровно ничего не говорил, как только то, что, покуда есть глаза, надо же глядеть куда нибудь, или он говорил слишком многое. Пьер остановился, не зная, что ему делать, и вопросительно оглянулся на свою руководительницу Анну Михайловну. Анна Михайловна сделала ему торопливый жест глазами, указывая на руку больного и губами посылая ей воздушный поцелуй. Пьер, старательно вытягивая шею, чтоб не зацепить за одеяло, исполнил ее совет и приложился к ширококостной и мясистой руке. Ни рука, ни один мускул лица графа не дрогнули. Пьер опять вопросительно посмотрел на Анну Михайловну, спрашивая теперь, что ему делать. Анна Михайловна глазами указала ему на кресло, стоявшее подле кровати. Пьер покорно стал садиться на кресло, глазами продолжая спрашивать, то ли он сделал, что нужно. Анна Михайловна одобрительно кивнула головой. Пьер принял опять симметрично наивное положение египетской статуи, видимо, соболезнуя о том, что неуклюжее и толстое тело его занимало такое большое пространство, и употребляя все душевные силы, чтобы казаться как можно меньше. Он смотрел на графа. Граф смотрел на то место, где находилось лицо Пьера, в то время как он стоял. Анна Михайловна являла в своем положении сознание трогательной важности этой последней минуты свидания отца с сыном. Это продолжалось две минуты, которые показались Пьеру часом. Вдруг в крупных мускулах и морщинах лица графа появилось содрогание. Содрогание усиливалось, красивый рот покривился (тут только Пьер понял, до какой степени отец его был близок к смерти), из перекривленного рта послышался неясный хриплый звук. Анна Михайловна старательно смотрела в глаза больному и, стараясь угадать, чего было нужно ему, указывала то на Пьера, то на питье, то шопотом вопросительно называла князя Василия, то указывала на одеяло. Глаза и лицо больного выказывали нетерпение. Он сделал усилие, чтобы взглянуть на слугу, который безотходно стоял у изголовья постели.