Máquina de Turing não-determinística
Com máquinas de Turing não determinísticas é possível ter ramificações ocorrendo execuções em “paralelo” a partir de uma determinada configuração.
A aceitação de uma entrada acontece quando ao menos 1 ramificação alcance o estado final.
Para a máquina de Turing abaixo:
Faça a simulação da entrada abbab:
Referências
https://drive.google.com/file/d/11oZdzUJnB8H3a6oEBC4uQIyhmzjN0CTq/view?usp=drive_link