Loading AI tools
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.
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].
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.
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].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
