Probabilidad de universalidad

La probabilidad de universalidad es una medida de probabilidad abstrusa en la teoría de la complejidad computacional que concierne a las máquinas de Turing universales .

Una máquina de Turing es un modelo básico de computación . Algunas máquinas de Turing pueden estar diseñadas para realizar cálculos específicos. Por ejemplo, una máquina de Turing podría recibir como entrada dos números y producir como salida el producto de su multiplicación . Otra máquina de Turing podría recibir como entrada una lista de números y producir como salida esos números ordenados .

Una máquina de Turing que tiene la capacidad de simular cualquier otra máquina de Turing se llama universal ; en otras palabras, se dice que una máquina de Turing (MT) es una máquina de Turing universal (o MTU) si, dada cualquier otra MT, existe alguna entrada (o "encabezado") tal que la primera MT dada esa entrada "encabezado" se comportará siempre como la segunda MT.

Surge entonces una interesante cuestión matemática y filosófica . Si a una máquina de Turing universal se le proporciona una entrada aleatoria (para una definición adecuada de aleatoriedad ), ¿qué probabilidad hay de que siga siendo universal para siempre?

Dada una máquina de Turing sin prefijos , su probabilidad de universalidad es la probabilidad de que siga siendo universal incluso cuando cada una de sus entradas (como una cadena binaria ) está precedida por una cadena binaria aleatoria. Formalmente, es la medida de probabilidad de los números reales (secuencias binarias infinitas) que poseen la propiedad de que cada segmento inicial de los mismos preserva la universalidad de la máquina de Turing dada. Esta noción fue introducida por el científico informático Chris Wallace y se discutió explícitamente por primera vez en un artículo de Dowe ^{[ 1 ]} (y en un artículo posterior ^{[ 2 ]} ). Sin embargo, también aparecen discusiones relevantes en un artículo anterior de Wallace y Dowe ^{[ 3 ] .}

Aunque originalmente se sospechaba que la probabilidad de universalidad de una UTM (UTM) era cero, existen pruebas relativamente simples de que el supremo del conjunto de probabilidades de universalidad es igual a 1, como una prueba basada en caminatas aleatorias ^{[ 4 ]} y una prueba en Barmpalias y Dowe (2012). Una vez que se tiene una UTM sin prefijo con una probabilidad de universalidad distinta de cero, se deduce inmediatamente que todas las UTM sin prefijo tienen una probabilidad de universalidad distinta de cero. Además, debido a que el supremo del conjunto de probabilidades de universalidad es 1 y debido a que el conjunto { ⁠ m / 2 ⁿ ⁠ | 0 < n & 0 < m < 2 ⁿ } es denso en el intervalo [0, 1], construcciones adecuadas de UTM (por ejemplo, si U es una UTM, defina una UTM U ₂ por U ₂ (0 s ) se detiene para todas las cadenas s , U ₂ (1 s ) = U ( s ) para todo s) dan que el conjunto de probabilidades de universalidad es denso en el intervalo abierto (0, 1).

La probabilidad de universalidad fue estudiada y caracterizada exhaustivamente por Barmpalias y Dowe en 2012. ^{[ 5 ]} Vistas como números reales , estas probabilidades fueron completamente caracterizadas en términos de nociones de la teoría de la computabilidad y la teoría de la información algorítmica . Se demostró que cuando la máquina subyacente es universal, estos números son altamente aleatorios algorítmicamente . Más específicamente, son aleatorios de Martin-Löf en relación con la tercera iteración del problema de la parada . En otras palabras, son aleatorios en relación con conjuntos nulos que pueden definirse con cuatro cuantificadores en la aritmética de Peano . Recíprocamente, dado un número tan altamente aleatorio (con propiedades de aproximación apropiadas) hay una máquina de Turing con una probabilidad universal de ese número.

Las probabilidades de universalidad están estrechamente relacionadas con la constante de Chaitin , que representa la probabilidad de parada de una máquina universal sin prefijos. En cierto modo, son complementarias a las probabilidades de parada de las máquinas universales en relación con la tercera iteración del problema de parada . En particular, la probabilidad de universalidad puede considerarse como la probabilidad de no parada de una máquina con oráculo en la tercera iteración del problema de parada. A la inversa, la probabilidad de no parada de cualquier máquina sin prefijos con este oráculo altamente no computable es la probabilidad de universalidad de alguna máquina sin prefijos.

La probabilidad de universalidad proporciona un ejemplo concreto y, en cierto modo, natural de un número altamente aleatorio (en el sentido de la teoría de la información algorítmica ). Del mismo modo, la constante de Chaitin proporciona un ejemplo concreto de un número aleatorio (aunque para una noción mucho más débil de aleatoriedad algorítmica).

• Probabilidad algorítmica
• Historia de la aleatoriedad
• Teorema de incompletitud
• Inferencia inductiva
• complejidad de Kolmogorov
• Longitud mínima del mensaje
• La teoría de la inferencia inductiva de Solomonoff

• Barmpalias, G. y Dowe DL (2012). "Probabilidad de universalidad de una máquina sin prefijos". Philosophical Transactions of the Royal Society A . 370 (1): 3488–3511 (Número temático 'Los fundamentos de la computación, la física y la mentalidad: el legado de Turing' compilado y editado por Barry Cooper y Samson Abramsky). Bibcode : 2012RSPTA.370.3488B . CiteSeerX 10.1.1.221.6000 . doi : 10.1098/rsta.2011.0319 . PMID 22711870 . S2CID 2092954 .   
• Dowe, DL (5 de septiembre de 2008). "Prólogo sobre CS Wallace" . Computer Journal . 51 (5): 523– 560. doi : 10.1093/comjnl/bxm117 .(y aquí ).
• Dowe, DL (2011), " MML, modelos gráficos de redes bayesianas híbridas, consistencia estadística, invariancia y unicidad" , Handbook of the Philosophy of Science - (HPS Volumen 7) Philosophy of Statistics, PS Bandyopadhyay y MR Forster (eds.), Elsevier, pp901-982.
• Wallace, CS y Dowe, DL 1999 Longitud mínima del mensaje y complejidad de Kolmogorov . Computer J. 42, 270–283.
• Hernandez-Orallo, J. y Dowe, DL (2013), "Sobre las capacidades cognitivas potenciales en el reino de las máquinas", Minds and Machines , vol. 23, número 2, pp. 179-210 (y aquí )
• Barmpalias, G. (junio de 2015), diapositivas de la charla Archivada el 7 de enero de 2016 en Wayback Machine titulada ``Aleatoriedad, probabilidades y máquinas Archivada el 7 de enero de 2016 en Wayback Machine en la Décima Conferencia Internacional sobre Computabilidad, Complejidad y Aleatoriedad Archivada el 30 de agosto de 2015 en Wayback Machine ( CCR 2015 Archivada el 30 de agosto de 2015 en Wayback Machine ) conferencia, 22-26 de junio de 2015, Heidelberg, Alemania.
• Cristian S. Calude, Michael J. Dinneen y Chi-Kou Shu. Calculando un atisbo de aleatoriedad .

• Ming Li y Paul Vitányi (1997). Una introducción a la complejidad de Kolmogorov y sus aplicaciones . Springer. Capítulo de introducción (texto completo ).
• Cristian S. Calude (2002). Información y aleatoriedad: una perspectiva algorítmica , segunda edición. Springer. ISBN 3-540-43466-6
• R. Downey y D. Hirschfeldt (2010), Aleatoriedad algorítmica y complejidad , Springer-Verlag.