¿Puede una máquina de Turing probabilística resolver el problema de detención?

29

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.

Joey Adams
fuente
3
@downvoter: Esto no debería haber recibido un voto negativo sin un comentario.
Dave Clarke
3
¿Qué impide que una TM determinista enumere todos los casos? Aquí, verificar una conjetura es el problema, no adivinarse a sí mismo. Tenga en cuenta también que realmente no puede decir que es estrictamente más poderoso si crea el resultado deseado solo con una probabilidad . p<1
Raphael
1
"un programa determinista no puede producir una cadena cuya complejidad sea mayor que su propia longitud". Es suficiente que alguna otra máquina determinista emita la misma salida. Tenga en cuenta que los TM deterministas pueden simular no solo los probabilísticos, sino incluso los TM no deterministas (con un número arbitrario de alternancias).
Kaveh
Ayer estaba a punto de decir, mirando a Kaveh et al., Esta era una pregunta demasiado básica para este sitio (la misma pregunta para NTM es un resultado básico en cada primer curso de teoría). Dado que me costó bastante formalizar la "TM probabilística", me alegro de no haberlo hecho.
Raphael
1
Y vea las respuestas aclaratorias a mi pregunta anterior relacionada con TCS: cstheory.stackexchange.com/questions/1263/…
Joseph O'Rourke,

Respuestas:

22

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 > 1LxL>12xL>12

PH

PMRx

  • RxRx
  • RxRx
  • bucles de lo contrario

Mi1,2,...Rx0,1iR

  • >12i RiM
  • >12i RiM
  • Mi:=i+1

Rxp>12i>12iip>12iip>12

HNxH(N,x)=M(P(N,x))M(P(N,x))

  • la máquina se detiene y acepta más de la mitad de cadenas aleatorias
  • la máquina se detiene y rechaza más de la mitad de cadenas aleatorias.
Karolina Sołtys
fuente
>2i1S(Q)
1
Tenga en cuenta que si no requiere que P se detenga siempre, es trivial construir incluso una máquina de Turing determinista P que acepte si y solo si la máquina de Turing determinista dada se detiene.
Tsuyoshi Ito
¿Cuál es tu suposición? No puede negar una máquina de Turing probabilística a menos que se garantice que finalmente se detenga.
Tsuyoshi Ito
La probabilidad de detención se toma sobre la cadena adicional Y las palabras de entrada, ¿o qué?
M. Alaggan
1
@Mohammad ALAGGAN: No, esa parte es correcta tal como está escrita: la probabilidad se toma solo sobre la cadena adicional (que especifica los resultados de los lanzamientos de monedas). Debido a que no estamos asumiendo ninguna distribución de probabilidad en la cadena de entrada, la probabilidad sobre la cadena de entrada no está bien definida. Incluso si se define una distribución de probabilidad en la cadena de entrada, la alta probabilidad de respuesta correcta sobre la cadena de entrada implica solo que el algoritmo es correcto para la mayoría de las entradas, que es diferente del requisito habitual en un algoritmo.
Tsuyoshi Ito
14

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 ,

  • P ( M ) acepta con probabilidad distinta de cero si M se detiene,
  • P ( M ) nunca acepta si M no se detiene, y
  • P ( M ) se detiene con probabilidad 1 para cada 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,

  • Si requiere que P ( M ) se detenga siempre en lugar de simplemente con probabilidad 1 , entonces está claro que P puede ser simulado por un algoritmo determinista. (Ver Wikipedia para una explicación de la diferencia entre "siempre" y "con probabilidad 1")
  • Si hace que los límites de error sean estrictos al requerir que P ( M ) se detenga y dé la respuesta correcta con una probabilidad estrictamente mayor que 1/2 por cada M (es decir, no le importa si P ( M ) no se detiene o se detiene y dar la respuesta incorrecta en el resto de los casos), entonces P puede ser simulado por un algoritmo determinista utilizando el argumento establecido en la respuesta de Karolina Sołtys .

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.

Tsuyoshi Ito
fuente
Perdone mi ignorancia, pero ¿cuál es la diferencia entre detener '' siempre '' y detener '' con probabilidad 1 ''?
Rob Simmons
1
@Rob: Creo que es un punto complicado. Considere una máquina de Turing probabilística simple que simplemente lanza una moneda repetidamente hasta que el resultado sea la cara. Esta máquina de Turing se detiene excepto cuando todos los lanzamientos de monedas resultan en colas. Por lo tanto, se detiene con probabilidad 1, pero no siempre se detiene.
Tsuyoshi Ito
Encontré una explicación de la diferencia entre "siempre" y "con probabilidad 1" en Wikipedia , y agregué el mismo enlace en la respuesta.
Tsuyoshi Ito
Si permite que P (M) falle al no detenerse, entonces no sé cómo puede hacer una simulación determinista. Por ejemplo, suponga que ejecuta su simulación determinista en un conjunto de cadenas de prefijos de longitud N, y después de un período de tiempo, <50% de los prefijos se han detenido y dado una respuesta. ¿Cómo sabe si las cadenas de prefijos restantes simplemente necesitan más tiempo para devolver una respuesta, o si todas están atrapadas en un bucle infinito como parte de la condición de falla? Si es lo primero, continúas esperando. Si es esto último, finaliza la ronda actual y corre de nuevo en todos los prefijos de longitud-N + 1.
Mike Battaglia
¡Pero esto es imposible de determinar, porque es el problema de detención! No tenemos forma de saber si la máquina Turing se detendrá en esas entradas o no.
Mike Battaglia
12

PPP

Creo que este era el significado del comentario de Raphael.

Bagazo
fuente
7

ANA

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.

Bjørn Kjos-Hanssen
fuente