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.