Màquina de Turing provabilística

En Teoria de la complexitat computacional, s'utilisen Màquines de Turing provabilístiques per a definir diferents classes de complexitat.

Una Màquina de Turing provabilística és una Màquina de Turing, en concret de la forma no determinista, que selecciona aleatoriamente entre les transicions disponibles en cada punt en idèntica provabilitat per a cada alternativa.

Alternativament, es pot definir també com una màquina de Turing determinista en una instrucció adicional “escriure” a on el valor de l'escritura està uniformemente distribuït en l'alfabet de la màquina.

Com a conseqüència, una màquina de Turing provabilística pugues (a diferència d'una màquina de Turing) tindre un resultat estocàstic: Donada una entrada i un programa per a la màquina, pot eixecutar el programa en temps variables d'eixecució o pot no parar; més encara, pot acceptar una entrada en una eixecució i no acceptar-la en la següent.

Es desprén que l'acceptació d'una cadena d'entrada en una màquina de Turing provabilística pot ser definida de vàries formes. I a eixes formes de terminar corresponen diferents classes de complexitat que inclouen RP, Co-RP. BPP i ZPP. En restringir-se la màquina a solament usar espai logarítmic en lloc de temps polinòmic, es definixen les classes anàlogues RL, Co-RL, BPL, i ZPL. En incloure abdós restriccions s'obtenen les classes RLP, Co-RPL, BPLP i ZPLP.

Els computadors quàntics són un atre model de càlcul que és inherentemente provabilístic.

Vore també

• Màquina de Turing
• Màquina universal de Turing
• Màquina de Turing alternante
• Alan Turing