Enumeradores e operações com linguagens decidíveis e Turing reconhecíveis.
19 Novembro 2019, 09:30 • André Souto
Prova de como simular uma máquina de Turing multifita e não determinista numa máquina de Turing.
Noção de máquina enumeradora.
Prova que uma máquina enumeradora reconhece L se e só se L é Turing reconhecível.
O 10º problema de Hilbert e a tese de Church Turing.
Noção de algoritmo e descrição de alto nível de uma máquina de Turing.
Noção de codificação para inputs de máquinas de Turing.
Exemplos de codificação em grafos e máquina que decide a linguagem dos grafos conexos.
Estudar a secção 3.2 e 3.1 do Sipser.