Номер описания

Числа описания — это числа, которые возникают в теории машин Тьюринга . Они очень похожи на числа Гёделя и иногда называются «числами Гёделя» в литературе. При наличии некоторой универсальной машины Тьюринга каждой машине Тьюринга, при наличии ее кодировки на этой машине, может быть назначен номер. Это номер описания машины. Эти числа играют ключевую роль в доказательстве Алана Тьюринга неразрешимости проблемы остановки и также очень полезны в рассуждениях о машинах Тьюринга.

Допустим, у нас есть машина Тьюринга M с состояниями q ₁ , ... q _R , с ленточным алфавитом с символами s ₁ , ... s _m , с пробелом, обозначенным s ₀ , и переходами, дающими текущее состояние, текущий символ и выполненные действия (которые могут заключаться в перезаписи текущего символа ленты и перемещении головки ленты влево или вправо, или, может быть, вообще не перемещать ее), и следующее состояние. В соответствии с оригинальной универсальной машиной, описанной Аланом Тьюрингом, эта машина будет закодирована в качестве входных данных следующим образом:

1. Состояние q _i кодируется буквой «D», за которой следует буква «A», повторенная i раз ( унарный код).
2. Символ ленты s _j кодируется буквой «D», за которой следует буква «C», повторяющаяся j раз.
3. Переходы кодируются путем указания состояния, входного символа, символа для записи на ленту, направления движения (обозначаемого буквами «L», «R» или «N» для движения влево, вправо или отсутствия движения) и следующего состояния для перехода, при этом состояния и символы кодируются, как указано выше.

Таким образом, входные данные UTM состоят из переходов, разделенных точками с запятой, поэтому ее входной алфавит состоит из семи символов: «D», «A», «C», «L», «R», «N» и «;». Например, для очень простой машины Тьюринга, которая попеременно печатает 0 и 1 на своей ленте вечно:

1. Состояние: q ₁ , символ ввода: пробел, действие: печать 1, перемещение вправо, следующее состояние: q ₂
2. Состояние: q ₂ , входной символ: пробел, действие: печать 0, перемещение вправо, следующее состояние: q ₁

Если обозначить пробел как s ₀ , «0» как s ₁ и «1» как s ₂ , то машина будет закодирована UTM следующим образом:

DADDCCRDAA;DAADDCRDA;

Но тогда, если бы мы заменили каждый из семи символов 'A' на 1, 'C' на 2, 'D' на 3, 'L' на 4, 'R' на 5, 'N' на 6 и ';' на 7, мы бы получили кодировку машины Тьюринга как натурального числа: это номер описания этой машины Тьюринга в универсальной машине Тьюринга. Таким образом, простая машина Тьюринга, описанная выше, имела бы номер описания 313322531173113325317. Существует аналогичный процесс для любого другого типа универсальной машины Тьюринга. Обычно нет необходимости фактически вычислять номер описания таким образом: суть в том, что каждое натуральное число может быть интерпретировано как код для максимум одной машины Тьюринга, хотя многие натуральные числа могут не быть кодом для какой-либо машины Тьюринга (или, говоря другими словами, они представляют машины Тьюринга, которые не имеют состояний). Тот факт, что такой номер всегда существует для любой машины Тьюринга, как правило, важен.

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

Используя технику, похожую на диагональный аргумент Кантора , можно продемонстрировать такую ​​невычислимую функцию, например, что проблема остановки в частности неразрешима. Во-первых, обозначим через U(e, x) действие универсальной машины Тьюринга при заданном номере описания e и входе x, возвращающем 0, если e не является номером описания допустимой машины Тьюринга. Теперь предположим, что существует некий алгоритм, способный решить проблему остановки, т. е. машина Тьюринга TEST(e), которая при заданном номере описания некоторой машины Тьюринга вернет 1, если машина Тьюринга останавливается на каждом входе, или 0, если есть некоторые входы, которые заставят ее работать вечно. Объединив выходы этих машин, можно построить другую машину δ(k), которая возвращает U(k, k) + 1, если TEST(k) равен 1, и 0, если TEST(k) равен 0. Из этого определения δ определяется для каждого входа и, естественно, должна быть полностью рекурсивной. Поскольку δ построено из того, что мы предположили, также является машинами Тьюринга, то у него тоже должно быть число описания, назовем его e. Таким образом, мы можем снова передать число описания e в UTM, и по определению δ(k) = U(e, k), поэтому δ(e) = U(e, e). Но поскольку TEST(e) равно 1, по нашему другому определению δ(e) = U(e, e) + 1, что приводит к противоречию. Таким образом, TEST(e) не может существовать, и таким образом мы решили проблему остановки как неразрешимую.

• Число Гёделя
• Универсальная машина Тьюринга
• Церковная цифра
• Проблема остановки

• Джон Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли. ISBN 0-201-44124-1.(книга Золушка)
• Тьюринг, А. М. «О вычислимых числах с приложением к проблеме численного решения », Proc. Roy. Soc. London, 2(42), 1936, стр. 230–265.