Enthéorie de la complexité, unemachine de Turing probabiliste (ourandomisée) est unemachine de Turing qui peut utiliser duhasard. Ce genre de machine permet de définir des classes de complexité intéressantes et de donner un modèle de calcul pour lesalgorithmes probabilistes comme letest de primalité de Miller-Rabin.
Il existe différentes définitions équivalentes des machines deTuring probabilistes. Dans la suite tous les tirages sontindépendants etuniformes.
Un machine de Turing probabiliste, est une machine de Turing déterministe ayant deux bandes d'entrée : l'une qui contient lavraie 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.
Une machine de Turing probabiliste peut aussi être unemachine non déterministe qui choisit à chaque étape les transitions selon une certaineloi 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 classeRP, 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 etZPP.
On peut considérer que l'idée de faire des calculs basés sur du hasard a pour origine lesméthodes de Monte-Carlo enanalyse numérique et en statistiques[3]. Le principe de machine de Turing probabiliste date de 1955[4],[3].
(en)SanjeevArora et BoazBarak,Computational Complexity : A Modern Approach,Cambridge University Press,(ISBN 0-521-42426-7),chap. 7 (« Randomized Computation »)
