Máquina de Turing Não Ambígua

Na computação teórica, uma máquina de Turing é um máquina teórica que é usada no experimento mental para examinar as capacidades e limitações de computadores. Uma máquina de Turing não ambígua é um tipo especial de máquina de Turing não determinística, a qual, de certa forma, é semelhante a uma máquina de Turing determinística.

Definição Formal

Uma máquina de Turing não determinística é representada formalmente por uma 6-tupla, $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$. Um máquina de Turing não ambígua é uma máquina de Turing não determinística, tal que, para toda entrada w = a₁a₂ ... a_n, existe no máximo uma sequência de configurações c₀,c₁, ..., c_m com as seguintes condições:

1. c₀ é a configuração inicial da entrada w
2. c_i+1 é o sucessor do c_i e
3. c_m é uma configuração de aceitação.

Em outras palavras, se w é aceita por M, há exatamente uma computação de aceitação.

Expressividade

Uma máquina de Turing (determinística) é uma máquina de Turing não ambígua. De fato, para cada entrada, há exatamente uma computação possível.

Por um lado, uma máquina de Turing não ambígua tem a mesma expressividade de uma máquina de Turing. De fato, ela é um subconjunto das máquinas de Turing não determinísticas, que tem a mesma expressividade das máquinas de Turing.

Por outro lado, a classe de complexidade "tempo polinomial não-determinístico não-ambíguo" é supostamente menos expressiva do que a classe "tempo polinomial não-determinístico".

Referências

Lane A. Hemaspaandra and Jorg Rothe, Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets, SIAM J. Comput., 26(3), 634–653, 2006.