Máquina de Turing Probabilística - Probabilistic Turing machine

Máquinas de Turing
Máquina
Equivalentes da máquina de Turing Exemplos de máquina de Turing Galeria da máquina de Turing
Variantes
Máquina de Turing Alternada Máquina de Turing Neural Máquina de Turing não determinística Máquina de Quantum Turing Máquina Pós-Turing Máquina de Turing Probabilística Máquina de Turing somente leitura Máquinas de Turing móveis corretas somente leitura Máquina de Turing Multitape Máquina de Turing Multi-track Máquina de Turing Simétrica Máquina de Turing Total Máquina de Turing inequívoca Máquina universal de Turing Máquina zeno
Ciência
Alan Turing Categoria: Máquina de Turing
v t e

Na ciência da computação teórica , uma máquina de Turing probabilística é uma máquina de Turing não determinística que escolhe entre as transições disponíveis em cada ponto de acordo com alguma distribuição de probabilidade . Como consequência, uma máquina de Turing probabilística pode - ao contrário de uma máquina de Turing determinística - ter resultados estocásticos ; ou seja, em uma dada entrada e máquina de estado de instrução, ele pode ter diferentes tempos de execução ou pode não parar de todo; além disso, pode aceitar uma entrada em uma execução e rejeitar a mesma entrada em outra execução.

No caso de probabilidades iguais para as transições, as máquinas de Turing probabilísticas podem ser definidas como máquinas de Turing determinísticas com uma instrução de "escrita" adicional, onde o valor da escrita é uniformemente distribuí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 adicionada cheia de bits aleatórios chamada de "fita aleatória".

Um computador quântico é outro modelo de computação que é inerentemente probabilístico.

Descrição

Uma máquina de Turing probabilística é um tipo de máquina de Turing não determinística em que cada passo não determinístico é um "cara ou coroa", ou seja, em cada passo há dois próximos movimentos possíveis e a máquina de Turing seleciona probabilisticamente qual movimento tomar.

Definição formal

Uma máquina de Turing probabilística pode ser definida formalmente como a 7 tupla , onde ${\ displaystyle M = (Q, \ Sigma, \ Gamma, q_ {0}, A, \ delta _ {1}, \ delta _ {2})}$

• ${\ displaystyle Q}$ é um conjunto finito de estados
• ${\ displaystyle \ Sigma}$ é o alfabeto de entrada
• ${\ displaystyle \ Gamma}$ é um alfabeto de fita, que inclui o símbolo em branco ${\ displaystyle \ sqcup}$
• ${\ displaystyle q_ {0} \ in Q}$ é o estado inicial
• ${\ displaystyle A \ subseteq Q}$ é o conjunto de estados de aceitação (finais)
• ${\ displaystyle \ delta _ {1}: Q \ times \ Gamma \ to Q \ times \ Gamma \ times \ {L, R \}}$é a primeira função de transição probabilística. é um movimento uma célula para a esquerda na fita da máquina de Turing e é um movimento uma célula para a direita.${\ displaystyle L}$${\ displaystyle R}$
• ${\ displaystyle \ delta _ {2}: Q \ times \ Gamma \ to Q \ times \ Gamma \ times \ {L, R \}}$ é a segunda função de transição probabilística.

Em cada etapa, a máquina de Turing aplica probabilisticamente a função de transição ou a função de transição . Essa escolha é feita independentemente de todas as escolhas anteriores. Desta forma, o processo de seleção de uma função de transição em cada etapa do cálculo se assemelha a um lançamento de moeda. ${\ displaystyle \ delta _ {1}}$${\ displaystyle \ delta _ {2}}$

A seleção probabilística da função de transição em cada etapa introduz erro na máquina de Turing; isto é, cordas que a máquina de Turing deve aceitar podem em algumas ocasiões ser rejeitadas e cordas que a máquina de Turing deve rejeitar podem em algumas ocasiões ser aceitas. Para acomodar isso, diz-se que uma linguagem é reconhecida com probabilidade de erro por uma máquina de Turing probabilística se: ${\ displaystyle L}$${\ displaystyle \ epsilon}$${\ displaystyle M}$

1. uma string em implica que${\ displaystyle w}$${\ displaystyle L}$${\ displaystyle {\ text {Pr}} [M {\ text {aceita}} w] \ geq 1- \ epsilon}$
2. uma string não significa que${\ displaystyle w}$${\ displaystyle L}$${\ displaystyle {\ text {Pr}} [M {\ text {rejeita}} w] \ geq 1- \ epsilon}$

Classes de complexidade

Como resultado do erro introduzido pelo uso de sorteios probabilísticos de moeda, a noção de aceitação de uma corda por uma máquina de Turing probabilística pode ser definida de diferentes maneiras. Uma dessas noções que inclui várias classes importantes de complexidade permite uma probabilidade de erro de 1/3. Por exemplo, a classe de complexidade BPP é definida como a classe de linguagens reconhecidas por uma máquina de Turing probabilística em tempo polinomial com uma probabilidade de erro de 1/3. Outra classe definida usando essa noção de aceitação é BPL , que é o mesmo que BPP, mas coloca a restrição adicional de que as linguagens devem ser solucionáveis ​​no espaço logarítmico .

As classes de complexidade decorrentes de outras definições de aceitação incluem RP , co-RP e ZPP . Se a máquina estiver restrita ao espaço logarítmico em vez do tempo polinomial, as classes de complexidade RL , co-RL e ZPL análogas são obtidas. Ao aplicar ambas as restrições, RLP , co-RLP , BPLP e ZPLP são produzidos.

A computação probabilística também é crítica para a definição da maioria das classes de sistemas de prova interativos , nos quais a máquina verificadora depende da aleatoriedade para evitar ser predita e enganada pela máquina provadora todo-poderosa. Por exemplo, a classe IP é igual a PSPACE , mas se a aleatoriedade for removida do verificador, ficamos com apenas NP , que não é conhecido, mas amplamente considerado uma classe consideravelmente menor.

Uma das questões centrais da teoria da complexidade é se a aleatoriedade adiciona poder; isto é, há um 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 as máquinas de Turing determinísticas podem simular com eficiência todas as máquinas de Turing probabilísticas com, no máximo, uma desaceleração polinomial? Sabe-se que P ⊆ BPP , visto que uma máquina de Turing determinística é apenas um caso especial de uma máquina de Turing probabilística. No entanto, é incerto se (mas amplamente suspeita que) BPP ⊆ P , implicando que BPP = P . A mesma questão para o espaço de log em vez do tempo polinomial ( L = BPLP ?) É ainda mais amplamente considerada verdadeira. Por outro lado, o poder aleatório dá aos sistemas de prova interativos, bem como os algoritmos simples que ele cria para problemas difíceis, como teste de primalidade em tempo polinomial e teste de conexão de gráfico de espaço logarítmico, sugere que a aleatoriedade pode adicionar poder.

Veja também

• Algoritmo Randomizado

Notas

Referências

• Arora, Sanjeev ; Barak, Boaz (2016). Complexidade computacional: uma abordagem moderna . Cambridge University Press. pp. 123–142. ISBN 978-0-521-42426-4.
• Sipser, Michael (2006). Introdução à Teoria da Computação (2ª ed.). EUA: Thomson Course Technology. pp. 368–380. ISBN 978-0-534-95097-2.

links externos

• Site do NIST sobre máquinas de Turing probabilísticas