Variantes das máquinas de Turing
13 Novembro 2019, 09:30 • André Souto
As máquinas de Turing que terminam para todo o input.
Noção de linguagem Turing-decidível.
Exemplos de máquinas de Turing.
Variantes das máquinas de Turing:
- Stay;
- Multifita;
- Fita infinita para a esquerda;
- Não determinista.
Prova que todos os modelos apresentados são equivalentes `à máquina de Turing original.
Estudar secção 3.1 e 3.2 do Sipser.