6 votos

¿Una paradoja relacionada con los reales computables?

Sea O un ordenamiento computable de todos los reales computables en ⟨0,1) (por ejemplo, primero por la longitud de los programas que los computan y luego lexicográficamente). (no importa que aparezcan allí más de una vez).
Parece que es posible producir un real computable no en este ordenamiento por argumento diagonal, utilizando un algoritmo determinista para producir el dígito no coincidente.

¿Cuál es el error en este razonamiento?

6voto

Chris Eagle Puntos 25852

El error es que la ordenación computable que quieres no existe. Puedes ordenar fácilmente los programas como sugieres, pero como no puedes determinar computacionalmente qué programas definen realmente los números reales, eso no ayuda.

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