Una computadora que recibe un flujo infinito de bits verdaderamente aleatorios es más poderosa que una computadora sin una. La pregunta es: ¿es lo suficientemente potente como para resolver el problema de detención?
Es decir, ¿puede una computadora probabilística determinar si un programa determinista se detiene o no ?
Ejemplo de una computadora probabilística que hace algo que una determinista no puede: Considere un programa pequeño (de menos de un kilobyte de longitud) que genera una cadena con una complejidad de Kolmogorov mayor que un gigabyte. La complejidad de Kolmogorovde una cadena es la longitud del programa determinista más corto que produce esa cadena. Por lo tanto, por definición, un programa determinista no puede producir una cadena cuya complejidad sea mayor que su propia longitud. Sin embargo, si se le da un flujo infinito de bits verdaderamente aleatorios, un pequeño programa es capaz de lograr la tarea con 99.99999 ...% de éxito simplemente repitiendo, digamos, 10 mil millones de bits aleatorios y esperando que la complejidad Kolmogorov de esos bits sea lo suficientemente alta. . Por lo tanto, producir una cadena de complejidad superior de Kolmogorov está dentro del horizonte de posibilidades del programa probabilístico, pero no es posible en absoluto para el programa determinista.
Dicho esto, me pregunto si es posible usar bits realmente aleatorios para cortar el problema de detención. Por ejemplo, un algoritmo podría generar teoremas al azar y probar / refutar / descartarlos hasta que sepa lo suficiente como para probar / refutar que un determinado programa determinista se detiene.
fuente
Respuestas:
editar: Acabo de darme cuenta de que algunas de las cosas que escribí no tenían sentido, lo siento. Ahora cambié la prueba e hice la definición de máquina probabilística que estoy usando más precisa.
No sé si entiendo bien su definición de máquina probabilística de Turing: ¿es una máquina con una cinta adicional en la que se escribe una cadena infinitamente incompresible, y además actúa como una máquina determinista? Si arreglamos la cadena incompresible, la clase que obtenemos no parece ser interesante.
Creo que podemos definir una máquina de Turing probabilística de varias maneras. Usaré una definición que parece bastante natural (y para la cual funciona mi prueba;) Definamos una máquina probabilística como esa: obtiene una cinta adicional en la que se escribe una cadena infinita, decimos que esta máquina decide un lenguaje si es para cada x ∈ L se detiene y acepta con probabilidad > 1L x ∈ L > 12 x ∉ L > 12
fuente
Depende de lo que quieras decir con un algoritmo probabilístico que determina algún predicado.
Existe un algoritmo trivial probabilístico P tal que, para una máquina de Turing determinista M ,
Por lo tanto, el algoritmo probabilístico P resuelve el problema de detención para las máquinas de Turing deterministas en este sentido. (Aquí " M se detiene" significa " M se detiene en la entrada vacía").
Sin embargo, si fortalece el requisito de alguna manera sensata, es poco probable que pueda resolver el problema de detención para las máquinas deterministas de Turing. Por ejemplo,
Por lo tanto, un algoritmo probabilístico no puede resolver el problema de detención de las máquinas deterministas de Turing en estos sentidos.
fuente
Creo que este era el significado del comentario de Raphael.
fuente
de Leeuw, K., Moore, EF, Shannon, CE y Shapiro, N. Computabilidad por máquinas probabilísticas, estudios de autómatas, págs. 183–212. Anales de estudios matemáticos, no. 34. Princeton University Press, Princeton, NJ, 1956.
G. Sacks, Grados de insolubilidad, Princeton University Press, 1963.
fuente