Почему вычислимые числа (в смысле Тьюринга) перечислимы?

Почему вычислимые числа (в смысле Тьюринга) перечислимы? Это должно быть очень очевидно, но я сейчас просто не вижу этого.

$n$$n$

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

Заманчиво перечислять вычислимые числа путем перечисления машин Тьюринга, но не каждая машина Тьюринга соответствует вычислимому числу, и в общем случае решение о том, останавливается ли машина Тьюринга для всех входов (не говоря уже о выходе 0 или 1), не вычислимо. Тем не менее, можно использовать все эффективные вычислимые числа, скажем, те, чье время выполнения является полиномиальным, с использованием синхронизированных машин Тьюринга.

Если под перечислимым вы имеете в виду, что существует биекция с натуральными числами (то есть счетными), то нет, вычислимые числа не перечислимы.

Давайте определим проблему более точно: «Числовая печатная машина Тьюринга (NPTM)» - это машина Тьюринга, которая для каждого перехода состояния может ничего не печатать или может печатать любую десятичную цифру, знак минуса или точку. Этого достаточно, чтобы напечатать десятичные представления действительных чисел.

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

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

Это примеры NPTM, которые вычисляют некоторое число. NPTM, который:

• печатает 1, затем останавливается. Вычисляет номер 1.
• печатает 1.0, затем останавливается. Он также вычисляет номер 1.
• печатает 1.0000000, и печатает нули навсегда. Этот также вычисляет номер 1.
• печатает 3.14, затем останавливается. Вычисляет число 3.14.
• 3.14159$\pi$$\pi$
• печатает -42., а затем останавливается. Вычисляет число -42.

И это примеры NPTM, которые не вычисляют любое число. NPTM, который:

• печатает, 123123123а затем продолжает печатать последовательность 123навсегда. Не вычисляет число, потому что эта бесконечная последовательность не представляет никакого действительного числа.
• печатает 1.0.0и затем останавливается. Не потому, что эта конечная последовательность не очень хорошо сформирована.
• печатает ....-..---и затем останавливается. Не потому, что это не очень правильно сложенное реальное число.
• никогда ничего не печатает, но и никогда не останавливается. Там нет числа строится.
• никогда ничего не печатает и сразу останавливается. Число не было построено.
• печатает 3.14, не останавливается, но и никогда ничего не печатает. Не вычисляет число, потому что его точность не увеличивается со временем.

У тебя есть идея. Тогда у нас есть два класса NPTM: те, которые вычисляют некоторое действительное число, и те, которые этого не делают.

Проблема с нахождением некоторого перечисления для вычислимых чисел состоит в том, что, даже если сами NPTM счетны, у нас не может быть процедуры, которая отделяет один тип NPTM от другого.

$S$$F: \mathbb{N} \rightarrow S$

Чтобы «доказать», что вычислимые числа являются исчисляемыми, можно испытать искушение определить такую ​​функцию из подсчета NPTM (и это часто делают люди, считая, что вычислимые числа являются счетными). Что-то вроде этого:

$E_\text{NPTM}: \mathbb{N} -> \text{NPTM}$$E_\text{Computabe}: \mathbb{N} \rightarrow \text{Computable}$

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

Наивный способ определить биекцию потерпел неудачу, и не очень трудно доказать, что нет никакого способа сделать это вообще. Как предположил Ювал Фильмус, можно использовать диагонализацию.