Une machine probabiliste de Turing peut-elle résoudre le problème d'arrêt?

Un ordinateur doté d'un flux infini de bits vraiment aléatoires est plus puissant qu'un ordinateur sans un. La question est: est-elle suffisamment puissante pour résoudre le problème de l'arrêt?

Autrement dit, un ordinateur probabiliste peut-il déterminer si un programme déterministe s'arrête ou non ?

Exemple d'un ordinateur probabiliste faisant quelque chose de déterministe ne peut pas: Considérez un petit programme (moins d'un kilo-octet de longueur) qui produit une chaîne avec une complexité de Kolmogorov supérieure à un gigaoctet. La complexité de Kolmogorovd'une chaîne est la longueur du programme déterministe le plus court produisant cette chaîne. Ainsi, par définition, un programme déterministe ne peut pas produire une chaîne dont la complexité est supérieure à sa propre longueur. Cependant, si on lui donne un flux infini de bits vraiment aléatoires, un petit programme est capable de réaliser la tâche avec 99,99999 ...% de succès en faisant simplement écho, disons, 10 milliards de bits aléatoires et en espérant que la complexité de Kolmogorov de ces bits est suffisamment élevée . Par conséquent, la production d'une chaîne de complexité Kolmogorov supérieure est dans l'horizon de possibilité du programme probabiliste, mais pas du tout possible pour le programme déterministe.

Cela dit, je me demande s'il est possible d'utiliser des bits vraiment aléatoires pour scier le problème d'arrêt. Par exemple, un algorithme peut générer aléatoirement des théorèmes et les prouver / réfuter / rejeter jusqu'à ce qu'il en sache assez pour prouver / réfuter qu'un programme déterministe donné s'arrête.

edit: Je viens de réaliser que certaines des choses que j'ai écrites étaient totalement absurdes, désolé pour cela. Maintenant, j'ai changé la preuve et rendu la définition de la machine probabiliste que j'utilise plus précise.

Je ne sais pas si je comprends bien votre définition de la machine de Turing probabiliste: c'est une machine avec une bande supplémentaire sur laquelle une chaîne incompressible infinie est écrite, et à côté de cela, elle agit exactement comme une machine déterministe? Si nous réparons la chaîne incompressible, la classe que nous obtenons ne semble pas être intéressante.

Je pense que nous pouvons définir une machine de Turing probabiliste de plusieurs manières. Je vais utiliser une définition qui semble assez naturelle (et pour laquelle ma preuve fonctionne;) Définissons une machine probabiliste comme ça: elle obtient une bande supplémentaire sur laquelle une chaîne infinie est écrite, on dit que cette machine décide un langage si pour chaque x ∈ L il s'arrête et accepte avec probabilité > $L$$x \in L$ , lorsque la probabilité est prise sur ces chaînes aléatoires supplémentaires, et pour chaquex∉L,elle s'arrête et rejette avec une probabilité>$>\frac{1}{2}$$x \not \in L$ .$>\frac{1}{2}$

Nous allons maintenant montrer que s'il existe une telle machine probabiliste qui résout le problème d'arrêt pour les machines déterministes, nous pourrions l'utiliser pour construire une machine déterministe H qui résout le problème d'arrêt pour les machines déterministes - et nous savons qu'une telle machine ne peut exister.$P$$H$

Supposons qu'un tel existe. On peut construire une machine déterministe M qui prend en entrée une machine probabiliste R avec une entrée x , qui$P$$M$$R$$x$

• s'arrête et accepte si et seulement si accepte x (c'est-à-dire que R arrête et accepte x sur plus de la moitié des chaînes aléatoires).$R$$x$$R$$x$
• s'arrête et rejette si et seulement si rejette x (c'est-à-dire que R arrête et rejette x sur plus de la moitié des chaînes aléatoires).$R$$x$$R$$x$
• boucles sinon

Fondamentalement, sera pour tout i ∈ 1 , 2 , . . . simuler R sur l'entrée x et sur chaque chaîne de 0 , 1 i comme préfixe de la chaîne sur la bande aléatoire de R. À présent:$M$$i \in 1, 2, ...$$R$$x$${{0,1}}^i$$R$

• si pour préfixes de longueuriRarrêtés et acceptés sans essayer de lire plus deibits de la bande aléatoire,Ms'arrête et accepte$>\frac{1}{2}$$i$ $R$$i$$M$
• si pour préfixes de longueuriRarrêtés et rejetés sans essayer de lire plus deibits de la bande aléatoire,Ms'arrête et rejette$>\frac{1}{2}$$i$ $R$$i$$M$
• sinon exécute la simulation avec i : = i + 1 .$M$$i := i+1$

Nous devons maintenant nous convaincre que si accepte (rejette) x avec une probabilité p > $R$$x$ , puis pour certainsjen'accepterai (rejet) pour>$p >\frac{1}{2}$$i$ préfixes de longueuride la chaîne aléatoire sans essayer de lire plus deibits de la bande aléatoire. C'est technique, mais assez facile - si nous supposons le contraire, alors la probabilité d'accepter (de rejeter) approchep>$>\frac{1}{2}$$i$$i$ commejevaisà l'infini, donc pour certainsi,il devra êtrep>$p >\frac{1}{2}$$i$$i$ .$p >\frac{1}{2}$

Maintenant, nous définissons simplement notre machine déterministe résolvant le problème d'arrêt (c'est-à-dire décider si une machine déterministe donnée N accepte un mot donné x ) a comme H ( N , x ) = M ( P ( N , x ) ) . Notez que M ( P ( N , x ) ) s'arrête toujours, car décider d'un langage par nos machines probabilistes a été défini de telle manière que l'un de ces deux se produit toujours:$H$$N$$x$$H(N,x) = M(P(N,x))$$M(P(N, x))$

• la machine s'arrête et accepte plus de la moitié des chaînes aléatoires
• la machine s'arrête et rejette pendant plus de la moitié des chaînes aléatoires.

Cela dépend de ce que vous entendez par un algorithme probabiliste qui détermine un prédicat.

Il existe un algorithme probabiliste trivial P tel que, pour une machine de Turing déterministe M ,

• P ( M ) accepte avec une probabilité non nulle si M s'arrête,
• P ( M ) n'accepte jamais si M ne s'arrête pas, et
• P ( M ) arrête avec une probabilité de 1 pour chaque M .

Par conséquent, l'algorithme probabiliste P résout le problème d'arrêt pour les machines de Turing déterministes dans ce sens. (Ici, « M s'arrête» signifie « M s'arrête sur l'entrée vide».)

Cependant, si vous renforcez l'exigence d'une manière sensée, il est peu probable que vous puissiez résoudre le problème d'arrêt des machines déterministes de Turing. Par exemple,

• Si vous avez besoin que P ( M ) s'arrête toujours au lieu de simplement avec la probabilité 1 , alors il est clair que P peut être simulé par un algorithme déterministe. (Voir Wikipedia pour une explication de la différence entre «toujours» et «avec probabilité 1».)
• Si vous rendez les limites d'erreur strictes en exigeant que P ( M ) s'arrête et donnez la bonne réponse avec une probabilité strictement supérieure à 1/2 pour chaque M (c'est-à-dire, vous ne vous souciez pas si P ( M ) ne s'arrête pas ou ne s'arrête pas et donner la mauvaise réponse dans le reste des cas), alors P peut être simulé par un algorithme déterministe en utilisant l'argument énoncé dans la réponse de Karolina Sołtys .

Par conséquent, un algorithme probabiliste ne peut pas résoudre le problème d'arrêt des machines déterministes de Turing dans ces sens.

$P$$P$$P$

Je pense que c'était le sens du commentaire de Raphaël.

$A\subseteq\mathbb N$$A$

de Leeuw, K., Moore, EF, Shannon, CE et Shapiro, N. Computability by probabilistic machines, Automata studies, pp. 183–212. Annales d'études mathématiques, non. 34. Princeton University Press, Princeton, NJ, 1956.

G. Sacks, Degrees of Unsolvability, Princeton University Press, 1963.