304
правки
Изменения
Нет описания правки
Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.
== Ссылки ==
* Alan Turing, On computable numbers, with an application to the Entscheidungsproblem.
* F. C. Hennie and R. E. Stearns. Two-tape simulation of multitape Turing machines [http://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf (1)]
* Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach [http://www.cs.princeton.edu/theory/index.php/Compbook/Draft (1)]
