Machine de Turing probabiliste

En théorie de la complexité, une machine de Turing probabiliste (ou randomisée) est une machine de Turing qui peut utiliser du hasard. Ce genre de machine permet de définir des classes de complexité intéressantes et de donner un modèle de calcul pour les algorithmes probabilistes comme le test de primalité de Miller-Rabin.

Différentes définitions

Il existe différentes définitions équivalentes des machines de Turing probabilistes. Dans la suite tous les tirages sont indépendants et uniformes.

Avec une bande d'aléas

Un machine de Turing probabiliste, est une machine de Turing déterministe ayant deux bandes d'entrée : l'une qui contient la vraie entrée du problème et l'autre contient une série de bits aléatoires^[1]. Les transitions peuvent dépendre de cette seconde bande, ce qui équivaut à faire des choix aléatoires pendant une exécution de la machine.

Machine non déterministe avec probabilité de transition

Une machine de Turing probabiliste peut aussi être une machine non déterministe qui choisit à chaque étape les transitions selon une certaine loi de probabilité. On peut même restreindre cette définition à une machine choisissant à chaque pas entre deux transitions avec une probabilité 1/2 pour chacune^[2].

Acceptation et classes de complexité

Les conditions d'acceptation sont plus complexes que pour une machine de Turing classique : elles dépendent le plus souvent de la probabilité d'acceptation et de rejet sur une exécution. (Pour le formalisme avec bande d'aléas, ces probabilités sont celles d'acceptation alors que l'on n'a pas encore tiré les bits aléatoires.)

Par exemple, pour une machine traitant un problème de la classe RP, si le mot n'est pas dans le langage la machine le rejettera toujours et s'il est dans le langage, elle l'acceptera avec une probabilité d'au moins 1/2.

Les différentes conditions d'acceptation et de rejet, ainsi que des conditions sur le temps de calcul permettent de définir une grande famille de classes de complexité, dont les plus courantes sont celles en temps polynomial : RP, co-RP, BPP et ZPP.

Histoire

On peut considérer que l'idée de faire des calculs basés sur du hasard a pour origine les méthodes de Monte-Carlo en analyse numérique et en statistiques^[3]. Le principe de machine de Turing probabiliste date de 1955^[4],[3].

Notes et références

1. Thèse de Jean-Sébastien Coron, section Machines de Turing étendues
2. (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7.1 (« Probabilistic Turing Machine »)
3. (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), « Introduction: Computation model and complexity classes (Notes) »
4. Karel De Leeuw, Edward F. Moore, Claude E. Shannon et Norman Shapiro, « Computability by probabilistic machines », Automata studies, vol. 34,‎ 1955, p. 183-198

Bibliographie

(en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009 (ISBN 0-521-42426-7), chap. 7 (« Randomized Computation »)

Voir aussi

• Machine de Turing non déterministe

• Portail de l'informatique théorique