Saídas/resultados da Máquina de Turing

Ao se submeter uma entrada, por meio da fita, a Máquina de Turing a analisará de acordo com sua função de transição, e poderá assumir um dos seguintes estados de parada:

1. Aceitação: a cadeia submetida foi analisada e considerada aceita/válida pela máquina. Isto acontece quando a cadeia pertence à linguagem;

2. Rejeição: a cadeia submetida foi analisada e considerada rejeita/inválida pela máquina. Isto pode acontecer quando a cadeia não pertence à linguagem;

3. Loop: a cadeia submetida causou um loop infinito na máquina, seu processamento jamais cessará, não assumindo, assim, nenhum dos estados de parada anteriores. Isto pode acontecer quando a cadeia não pertence à linguagem.

O conjunto das cadeias aceitas pela máquina compoem a linguagem aceita por ela. Faz sentido, né? Os estados de parada de aceitação e rejeição são nulos quando se usa a Máquina de Turing para processamentos de funções e procedimentos. Afinal de contas, a máquina está sendo usada como um processador e não como um reconhecedor.