A tese de Church-Turing.
14 Novembro 2017, 09:30 • Ana Respicio
O 10º problema de Hilbert e a sua influência na Teoria da Computação.
A tese de Church-Turing.
O resultado fundamental da Teoria da Computação.
A linguagem dos polinómios só com uma variável e que têm raiz inteira é decidível.
Codificar objetos como strings. Exemplos. Codificação de um grafo.
O problema de determinar se um grafo não orientado é conexo é decidível. Prova.
Hierarquia de Chomsky.
Decidibilidade. Problemas decidíveis e linguagens decidíveis.
A_AFD é decidível. Prova.Aprender: Sipser, caps 3 e 4.
Praticar: Folhas de exercícios 7 e 8.