Máquina de Turing
Máquina de Turing é um modelo matemática e teórico que serve para provar o que pode ou não pode ser resolvido por um computador.
Se um problema puder ser resolvido por um algoritmo, uma Máquina de Turing consegue resolvê-lo (essa é a tese de Church-Turing).
- Fita (dados de entrada / memória)
- Cabeçote (move-se sequencialmente para esquerda ou direta, não há saltos)
Os possíveis resultados possíveis de serem obtidos com a execução da entrada são:
- Aceitação (atingiu o estado final e a leitura da fita se encerra)
- Rejeição
- Loop infinito
NOTE
Conforme a definição de aceitação em Máquinas de Turing, não faz sentido ter transições que saiam do estado final.