Máquina de Turing probabilística
 | Este artigo não cita fontes confiáveis. (Julho de 2012) |
Em Teoria da Computabilidade, uma máquina de Turing probabilística é uma Máquina de Turing não determinística que escolhe aleatoriamente dentre as transições a cada ponto, de acordo com alguma distribuição de probabilidade.
No caso de probabilidades iguals para as transições, esse tipo de máquina pode ser definido como uma máquina de Turing determinística tendo uma instrução adicional "write" onde o valor de escrita é uniformemente ditribuído no alfabeto da máquina de Turing (geralmente, uma probabilidade igual de escrever um '1' ou um '0' na fita). Outra reformulação comum é simplesmente uma máquina de Turing determinística com uma fita adicional repleta de bits aleatórios, chamada fita aleatória.
Como consequência, uma máquina de Turing probabilística pode, ao contrário de uma máquina determinística, ter resultados estocásticos; numa dada entrada e instruções, ela pode ter diferentes tempos de execução ou pode até não parar; além disso, ela pode aceitar uma entrada numa execução e rejeitar a mesma entrada em outra.
Então, a noção de aceitação de uma cadeia por uma máquina de Turing probabilística pode ser definida de maneiras diferentes. Várias classes de tempo polinomial aleatórias que resultam de diferentes definições de aceitação incluem RP, Co-RP, BPP e ZPP. Se restringirmos a máquina para espaço logarítmico ao invés de tempo polinomial, nós obtemos as análogas RL, Co-RL, BPL e ZPL. Se nós reforçarmos ambas as restrições, nós obtemos RLP, Co-RLP, BPLP e ZPLP.
Computação probabilística também é crítica para a definição da maioria das classes de sistemas de provas interativos, nos quais a máquina verificadora depende de aleatoriedade para evitar ser prevista e enganada pela toda-poderosa máquina de prova. Por exemplo, a classe IP é igual a PSPACE, mas se aleatoriedade é removida do verificador, somos deixados apenas com NP, que não se tem certeza, porém acredita-se que é uma classe consideravelmente menor.
Uma das questões centrais da teoria da complexidade é se aleatoriedade adiciona poder; isto é, há algum problema que pode ser resolvido em tempo polinomial por uma máquina de Turing probabilística, mas não por uma máquina de Turing determinística. Ou podem máquinas de Turing simular com eficiência todas as máquinas de Turing probabilística com um atraso no máximo polinomial? Atualmente acredita-se abertamente que a última afirmação é o caso, o que implicaria em P = BPP. A mesma questão para espaço logarítmico ao invés de tempo polinomial (L = BPLP?) é até mais abertamente aceita como verdade. Por outro lado, o poder que aleatoriedade dá para sistemas de prova interativos e os algoritmos simples que ela cria para problemas difíceis, tal qual teste de primalidade em tempo polinomial e teste de conectividade de grafos em espaço logarítmico sugerem que aleatoriedade, de fato, pode adicionar poder. Um computador quântico é outro modelo computacional é outro modelo que é inerentemente probabilístico.
