Máquina de Turing não-determinística
Origem: Wikipédia, a enciclopédia livre.
Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.
[editar] Definição
Uma máquina de Turing comum possui uma função de transição que, dado um estado e um símbolo na posição de execução da fita, especifica um novo símbolo a ser escrito na posição de execução da fita, a direção para o qual a fita deve mover-se e um novo estado para o sistema. Uma máquina de Turing não-determinística difere-se pois mais de uma ação pode ser aplicável dado um estado e um símbolo.
Existem diversos métodos para decidir qual caminho tomar, por exemplo, escolhendo a transição com maior potencial para levar a um estado desejado. Assim como uma máquina de Turing determinística possui um caminho de execução, a versão não-determinística possui uma árvore de execução. Se algum ramo da árvore leva a um estado desejado com a condição de sucesso do sistema, é definido que a máquina aceitou a estrada de dados.
