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

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

    Каждая конкретная машина Тьюринга M со своим набором исходных символов, состояний и правил способна вычислять лишь конкретную функцию fM. Тьюринг в дальнейшем предложил конструкцию универсальной машины U, способной вычислять любые функции. Для этого достаточно было создать машину, способную моделировать вычисления других машин.

    Сегодня при описании конкретной машины Тьюринга набор правил, которые определяют ее работу, интуитивно сразу понимают как некоторую программу по аналогии с программами для современных компьютеров. Это неправильное понимание. Машина Тьюринга не выполняет никакой программы. Она жестко выполняет лишь то, для чего предназначена. Просто с внешней точки зрения мы можем описать ее функционирование с помощью формализма, включающего эти правила, как можем в терминах машин Тьюринга описать жесткую последовательность действий, которые способен выполнять механический настольный арифмометр, не содержащий внутри никакой программы, а лишь шестеренки и настраиваемые рычажки. Идея Тьюринга как раз и заключалась в том, чтобы внешние описания отдельных машин превратить в программы, которые, как и исходные данные, размещаются на рабочей ленте и обрабатываются в соответствии с их предназначением.

    Тьюринг показал, как с помощью конечного набора символов алфавита можно закодировать любую машину M, т.е. используемый ею набор символов, набор внутренних состояний и список правил. Обозначим закодированную машину M как (M) , пусть машина M в применении ко входным данным n вычисляет функцию fM(n) . Тьюринг не просто высказал идею, а показал, как определить такую машину U, что, если на ее рабочей ленте размещен код (M) и данные n, то она сначала распознает код (M) , затем распознает входные данные n, и начинает применять к ним уже не свои правила, а правила машины M. Таким образом она вычисляет функцию fU((M),n) , результат которой совпадает с результатом вычисления функции fM(n) , т.е. fU((M),n)=fM(n) .

    Идеи, заключенные в универсальной машине Тьюринга, позволили получить целый ряд математических результатов, связанных со свойствами алгоритмов. В первую очередь это ограничительные теоремы существования алгоритмов для решения различных видов задач. В основе доказательства многих из них лежит модификация диагонального метода Кантора, когда на вход машины M подается ее собственный код (M) . С помощью этого метода оказалось возможным доказать, что проблема остановки не имеет решения.

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

  • Bibliography

  • Hodges A. Alan Turing and the Turing Machine // The Universal Turing Machine. A Half-Century Survey / Ed. by R. Herken. Hamburg; Berlin, 1988. P. 3–16.
  • Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.