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.