Màquina de Turing probabilística

En teoria de la complexitat, s'utilitzen Màquines de Turing probabilística per definir diferents classes de complexitat.

Una 'Màquina de Turing probabilística és una màquina de Turing, en concret de la forma no determinista, que selecciona aleatòriament entre les transicions disponibles a cada punt amb idèntica probabilitat per cada alternativa.

Alternativament, es pot definir també com una màquina de Turing determinista amb una instrucció addicional "escriure" on el valor de l'escriptura està uniformement distribuït en l'alfabet de la màquina.

Com a conseqüència, una màquina de Turing probabilística pot (a diferència d'una màquina de Turing) tenir un resultat estocàstic: donada una entrada i un programa per la màquina, pot executar el programa en temps variables d'execució, o pot no parar, o més encara, pot acceptar una entrada en una execució, i no acceptar-la en la següent.

Es desprèn que l'acceptació d'una cadena d'entrada d'una màquina de Turing probabilística pot ser definida de diferents maneres. I a aquestes formes d'acabar corresponen diferents classes de complexitat que inclouen RP, Co-RP, BPP i ZPP. Al restringir-se la màquina a usar tan sols espai logarítmic en lloc de temps polinòmic, es pot definir les classes anàlogues RL, Co-RL, BPL i ZPL. En incloure ambdues restriccions s'obtenen les classes RLP, Co-RPL, BPLP i ZPLP.

Els computadors quàntics són un altre model de càlcul que és inherentment probabilístic.