¿Existe una función computable tal que:
- Para todos los
Donde es un número real indiscutible.
La única referencia a esta pregunta que he encontrado fue la respuesta a esta pregunta : /math//a/1052579/168764 , donde parece que la función se mantendría, pero no tengo idea de cómo demostrar eso El límite de esta función es un número real indiscutible.
computability
cjnash
fuente
fuente
Respuestas:
Considere la codificación de número real del (casi) problema de detención, es decir, donde si la máquina i-ésima de Turing (en relación con el orden lexicográfico) se detiene en la entrada vacía, y contrario. Denotemos este número por .r i = 1 r i = 0 R0. r1r2. . . ryo= 1 ryo=0 R
Ahora, considere la máquina que en la entrada simula todas las máquinas de Turing de longitud en la entrada vacía para pasos, y devuelve donde si la máquina -ésima de Turing se detiene en la entrada vacía en menos de pasos, y caso contrario. Claramente para todos se cumple que , y no es demasiado difícil de demostrar que converge a . El punto clave es que la tasa de convergencia no es computable, lo que significa que dadoM n <n n 0.r1^. ..r2n−1^ ryo^= 1 yo norte ryo^= 0 norte METRO( n ) < R { M( n ) }n ∈ N R ϵ , No se puede calcular el índice de este tipo que más allá de que la serie es -cerca de .ϵ R
fuente