La probabilidad de universalidad es una medida de probabilidad abstrusa en la teoría de la complejidad computacional que se refiere a las máquinas universales de Turing .
Una máquina de Turing es un modelo básico de computación . Algunas máquinas de Turing pueden ser específicas para realizar cálculos particulares. Por ejemplo, una máquina de Turing podría tomar una entrada que comprenda dos números y luego producir una salida que sea el producto de su multiplicación . Otra máquina de Turing podría tomar una entrada que es una lista de números y luego dar una salida que son esos números ordenados en orden.
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 (TM) es una máquina de Turing universal (o UTM) si, dada cualquier otra TM, existe alguna entrada (o "encabezado") de modo que la primera TM dada esa entrada "encabezado" se comportará para siempre como la segunda TM.
Surge entonces una interesante cuestión matemática y filosófica . Si a una máquina de Turing universal se le da una entrada aleatoria (para una definición adecuada de aleatorio ), ¿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 entrada de la misma (como una cadena binaria ) tiene el prefijo de una cadena binaria aleatoria. Más formalmente, es la medida de probabilidad de los reales (secuencias binarias infinitas) que tienen la propiedad de que cada segmento inicial de ellos preserva la universalidad de la máquina de Turing dada. Esta noción fue introducida por el informático Chris Wallace y fue discutida explícitamente por primera vez en un artículo impreso de Dowe [1] (y 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 un 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 paseos aleatorios [4] y una prueba en Barmpalias y Dowe (2012). Una vez que uno tiene un UTM sin prefijo con una probabilidad de universalidad distinta de cero, se deduce inmediatamente que todos los UTM sin prefijo tienen una probabilidad de universalidad distinta de cero. Además, porque el supremo del conjunto de probabilidades de universalidad es 1 y porque el conjunto { metro/2 norte | 0 < n & 0 < m < 2 n } es denso en el intervalo [0, 1], construcciones adecuadas de UTM (por ejemplo, si U es un UTM, defina un UTM U 2 por U 2 (0 s ) se detiene para todos cadenas s , U 2 (1 s ) = U ( s ) para todo s) da 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 se caracterizaron completamente 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 algorítmicamente aleatorios . Más específicamente, es aleatorio de Martin-Löf en relación con la tercera iteración del problema de detención . En otras palabras, son aleatorios en relación con conjuntos nulos que pueden definirse con cuatro cuantificadores en aritmética de Peano . Viceversa, dado un número tan altamente aleatorio [ se necesita aclaración ] (con propiedades de aproximación apropiadas), existe una máquina de Turing con probabilidad de universalidad de ese número.
Las probabilidades de universalidad están muy relacionadas con la constante de Chaitin , que es la probabilidad de parada de una máquina universal sin prefijos. En cierto sentido, son complementarias a las probabilidades de detención de las máquinas universales en relación con la tercera iteración del problema de detención . En particular, la probabilidad de universalidad puede verse como la probabilidad de que una máquina con Oracle no se detenga en la tercera iteración del problema de detención. Viceversa, la probabilidad de no detenerse 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 algo natural de un número altamente aleatorio (en el sentido de la teoría algorítmica de la información ). En el mismo sentido, la constante de Chaitin proporciona un ejemplo concreto de un número aleatorio (pero para una noción mucho más débil de aleatoriedad algorítmica).