Operações com linguagens Turing decidíveis e Turing reconhecíveis.
17 Novembro 2021, 09:30 • André Souto
Operações com linguagens decidívies e Turing reconhecíveis.
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 de problemas em grafos e de problemas sobre máquinas de Turing. Noção de máquina de Turing universal.
Estudar a secção 3.2 e 3.1 do Sipser.