Machine de Turing probabiliste

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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é[modifier | modifier le code]

Les conditions d'acceptation sont plus complexe 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 la langage la machine le rejettera toujours et s'il est dans le langage, elle l'acceptera avec une probabilité au moins 1/2.

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

Voir aussi[modifier | modifier le code]

Sources[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  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 »)