Cada máquina de Turing que escribe una secuencia infinita de 1 y 0 puede considerarse como representando un número real (computable) (y, por supuesto, cada máquina de Turing representa un número natural mediante su tabla de máquina, o programa). La cuestión es cuántos saltos de Turing necesitamos para construir una inyección de tales números computables en números naturales. números computables en números naturales. Dado que hay un número infinito de máquinas de Turing que computan un mismo número real computable, parece que necesitamos al menos un salto de Turing. ¿Es suficiente una sola vez? Si no, ¿cuántos? ¿Incluso transfinitas veces?
Respuesta
¿Demasiados anuncios?Creo que un salto de Turing es suficiente. Cada real computable podría ser representado por una máquina de Turing {0,1} por lo tanto no son más que el número total de programas de ordenador. Consideremos el mapa $f: \omega-K \mapsto \omega$ donde $K$ es el conjunto de programas que se detienen, es decir, el conjunto de los índices de todos los programas que se detienen. Entonces $f(x)=least \ e\in \omega$ tal que $\exists z \varphi_e(z)\neq \varphi_i(z) \forall i<e$ . Se trata de un $\Sigma_1^0$ pregunta puede responderse en $\emptyset'$ . Entonces es fácil ver que la construcción de f es recursiva en $K$ y también es inyectiva.