2 votos

Inyección de números computables en números naturales

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?

0voto

Jing Zhang Puntos 871

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.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X