J'ai lu l'article que je citais depuis. En fait ce que montrent les auteurs c'est que si la probabilité est un nombre calculable alors on peut émuler la machine de Turing probabiliste avec une machine de Turing déterministe. Par contre si la probabilité n'est pas un nombre calculable, il n'est pas possible de trouver de machine de Turing déterministe équivalente, on est donc dans la classe des machines avec oracle.Envoyé par Argyre
Pour comprendre comment une machine probabiliste peut être émulée par une machine de Turing :
La machine gère une table, il y a une entrée par règle de transition. A chaque entrée on associe le nombre de fois que chaque règle de transition est appelée. A chaque fois que la machine de turing appelle une règle, elle incrémente de 1 l'entrée correspondante dans la table. Cette table permet de calculer la probabilité d'appel à chaque règle, il suffit de prendre la valeur trouvée et de diviser par le nombre total d'appels aux règles.
Quand la machine a le choix entre deux règles, elle continue le programme sur le ruban en cours, et continue l'alternative sur un second ruban et ainsi de suite à chaque nouvelle alternative. On se retrouve ainsi avec N programmes tournant en paralèlle correspondant chacun à une alternative possible. Le processus de duplication cesse quand les valeurs prévues pour les probabilités sont atteintes. On a ainsi une machine équivalente à la machine probabiliste.
On peut aussi voir cette machine comme une machine calculant une probabilité. Ainsi il est nécessaire que la probabilité soit calculable pour que le raisonnement que je tiens au-dessus fonctionne. On comprend alors pourquoi il n'est pas possible de remplacer une machine de turing probabiliste équipée d'une probabilité non calculable par une machine de Turing déterministe.
Bien sûr les auteurs montrent tout ça de façon bien plus rigoureuse.
Finalement, ça n'apporte pas tellement d'eau au moulin. L'article traduit juste que si on introduit une donnée non calculable dans un algorithme, il peut générer des valeurs non calculables.
-----