¿Puede una función computable converger a un número no computable?

18

¿Existe una función computable tal que:F:norteQ

  • Para todos lostnorte:0 0F(t)<X
  • limtF(t)=X

Donde X 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.

cjnash
fuente
Creo que esta respuesta que escribí hace tres años responde a su pregunta: math.stackexchange.com/a/1267124/161559
kasperd
2
Los números que se pueden obtener como el límite se llaman reales de izquierda a izquierda, en caso de que desee buscar más sobre sus propiedades. X
Arno
tal vez también math.stackexchange.com/a/462835/128985 que da esa función, creo (a menos que tenga la lógica al revés)
Philip Oakley

Respuestas:

31

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=1ri=0R

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 dadoMn<nn0.r1^...r2norte-1^ryo^=1yonorteryo^=0 0norteMETRO(norte)<R{METRO(norte)}nortenorteRϵ, No se puede calcular el índice de este tipo que más allá de que la serie es -cerca de .ϵR

Ariel
fuente
El que mencionó es cualquier número real o es un número real computable? (¿Hace alguna diferencia?)ϵ
Pedro A
1
No hay ningún problema de computabilidad aquí, pero como estamos hablando de una entrada a una máquina de Turing, debe tener alguna representación finita, por lo que podemos pensar en como un pequeño número racional. ϵ
Ariel