¿Por qué los números computables (en el sentido de Turing) son enumerables?

¿Por qué los números computables (en el sentido de Turing) son enumerables? Debe ser muy obvio, pero actualmente no lo estoy viendo.

$n$$n$

Supongamos que hay una enumeración recursiva de máquinas de Turing que producen números computables. Puede usar la diagonalización para obtener un nuevo número computable que no sea parte de esta enumeración recursiva.

Es tentador enumerar números computables enumerando máquinas de Turing, pero no todas las máquinas de Turing corresponden a un número computable, y en general decidir si una máquina de Turing detiene todas las entradas (y mucho menos la salida 0 o 1) no es computable. Sin embargo, es posible enumerar todos los números computables eficientes, digamos aquellos cuyo tiempo de ejecución es polinómico, utilizando máquinas de Turing con reloj.

Si por enumerable, quiere decir que hay una biyección con los números naturales (es decir, contables), entonces no, los números computables no son enumerables.

Definamos el problema con mayor precisión: una "Máquina de Turing de impresión de números (NPTM)" es una Máquina de Turing que, para cada transición de estado, puede no imprimir nada o puede imprimir cualquier dígito decimal, el signo menos o el punto. Esto es suficiente para imprimir representaciones decimales de números reales.

Definamos un número real computable como cualquier número real que puede imprimirse con una representación arbitrariamente larga, con tiempo suficiente, por un NPTM que comienza desde una cinta vacía. Digamos también que un NPTM determinado calcula un número si se detiene después de imprimir un número real bien formado (en cuyo caso, el número tiene una representación decimal finita) o, en un tiempo finito, imprimirá un número bien formado con un punto decimal, y siempre aumentará la precisión del número imprimiendo más dígitos, dado cada vez más tiempo.

Esta condición posterior es necesaria porque, si tenemos una máquina que, por ejemplo, imprime una secuencia infinita de algún dígito, digamos 1111111111111111111..., no se puede decir que esté calculando ningún número real, porque los números reales solo tienen una representación infinita a la derecha lado del punto decimal. Por otro lado, si la máquina imprime 3.14y luego deja de imprimir, pero nunca se detiene, no se puede decir que esté calculando ningún número real simplemente porque la precisión del número no aumenta, por lo tanto, esta máquina en particular no lo construirá. más lejos.

Estos son ejemplos de NPTM que calcula algún número. Un NPTM que:

• impresiones 1, luego se detiene. Calcula el número 1.
• impresiones 1.0, luego se detiene. También calcula el número 1.
• imprime 1.0000000y sigue imprimiendo ceros para siempre. Este también calcula el número 1.
• impresiones 3.14, luego se detiene. Calcula el número 3.14.
• 3.14159$\pi$$\pi$
• impresiones -42., y luego se detiene. Calcula el número -42.

Y estos son ejemplos de NPTM que no calculan ningún número. Un NPTM que:

• imprime 123123123y luego sigue imprimiendo la secuencia 123para siempre. No está calculando un número porque esta secuencia infinita no representa ningún número real.
• imprime 1.0.0y luego se detiene. No es porque esta secuencia finita no esté bien formada.
• imprime ....-..---y luego se detiene. No es porque este tampoco sea un número real bien formado.
• nunca imprime nada, pero tampoco se detiene tampoco. No se está construyendo ningún número.
• nunca imprime nada e inmediatamente se detiene. No se construyó ningún número.
• imprime 3.14, no se detiene, pero nunca imprime nada más tampoco. No está calculando un número porque su precisión no aumenta con el tiempo.

Tienes la idea. Luego tenemos dos clases de NPTM: las que calculan un número real y las que no.

El problema con encontrar alguna enumeración para los números computables es que, incluso si los NPTM son contables, no podemos tener un procedimiento que separe un tipo de NPTM de otro.

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

Para "probar" que los números computables son contables, uno podría verse tentado a definir dicha función a partir del conteo del NPTM (y esto es lo que la gente hizo a menudo, cuando creen que los números computables son contables). Algo como esto:

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

Bueno, nosotros no. Considere una máquina que imprime inmediatamente 1.0y luego deja de imprimir y trata de resolver una instancia del problema de correspondencia de correos . Si resuelve el problema, se detiene, entonces la máquina simplemente calculó el número uno. Pero ese problema es indecidible, por lo que nunca puede detenerse, y si nunca se detiene, nunca calcula un número real. ¡Pero no podemos saber si alguna vez se detendrá, porque el problema de Detener también es indecidible! Entonces, dado que no hay forma de saber si esta máquina en particular, y muchas otras máquinas infinitas, computa o no algún número real, no podemos construir / definir nuestra función biyectiva de esta manera.

La manera ingenua de definir la biyección falla, y no es muy difícil demostrar que no hay forma de hacerlo. Como sugirió Yuval Filmus, se puede utilizar la diagonalización.