Resumen:
El trabajo de Martin-Löf, Chaitin, Kolmogorov, Solovay y otros permitió tener una definición matemática de número real aleatorio. Chaitin encontró un ejemplo natural de número aleatorio: Ω, la probabilidad de detección de una máquina universal autodelimitante (también llamada máquina universal de Chaitin, MUC). Además de ser aleatorio, este número tiene la propiedad de ser aproximable en el límite desde abajo, propiedad que en la literatura se denomina real recursivamente enumerable (r. e.). Recientemente Slaman, a partir del trabajo de Calude y otros, ha demostrado que la clase de reales aleatorios r. e. coincide con la de los Ωnumbers, es decir que todo real aleatorio r. e. es la probabilidad de detección de alguna máquina universal auto limitante. Surge entonces el interés por estudiar reales aleatorios fuera de esta clase. En este trabajo demostraremos que la probabilidad de que una MUC lea sólo una porción finita de su cinta de programa, aun disponiendo de tiempo infinito, es un número aleatorio no r. e. Veremos que es totalmente impredecible, aun disponiendo de un oráculo para el problema de la detención. Esto puede resultar de interés en el contexto de una teoría de complejidad algorítmica de conjuntos.
Citación:
---------- APA ----------
Daicz, Sergio. (2000). Una nueva versión de la probabilidad de detención. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000800_Daicz
---------- CHICAGO ----------
Daicz, Sergio. "Una nueva versión de la probabilidad de detención". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2000.https://hdl.handle.net/20.500.12110/seminario_nCOM000800_Daicz
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000800_Daicz.pdf
Distrubución geográfica
