Variantes das máquinas de Turing
20 Novembro 2018, 09:30 • André Souto
Variantes das máquinas de Truing:
- Stay.
- Multi-fita.
- Fita duplamente infiinta.
- Não deterministica.
Prova que todas são equivalentes ao modelo de fita simples e portanto reconhecem/decidem as mesmas linguagens.
Os enumeradores.
Prova de equivalência entre enumeradores e máquinas de Turing de fita simples.
Operações com linguagens decidíveis e com linguagens reconhecíveis.
Estudar secção 3.2 do Sipser.