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

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

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

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

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

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

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

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

DADDCCRDAA;DADDCCRDAA;

Но тогда, если мы заменим каждый из семи символов «А» на 1, «С» на 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 . (книга «Золушка»)
Тьюринг А.М. «О вычислимых числах с применением к проблеме Entscheidungs », Proc. Рой. Соц. Лондон, 2 (42), 1936, стр. 230–265.