Sumários

17 Novembro 2017, 08:00 • Jorge Miguel Carvalho Gomes

Folha 7: exercício 6.

Folha 8: exercícios 1, 2, 3a), 3b) e 4a), 4b).

15 Novembro 2017, 08:00 • Ana Respicio

Folha 7: exercício 6. Folha 8: exercícios 1, 2, 3a), 3b) e 4a), 4b).

14 Novembro 2017, 11:00 • Jorge Miguel Carvalho Gomes

Folha 7: exercício 6.

Folha 8: exercícios 1, 2, 3a), 3b) e 4a), 4b).

14 Novembro 2017, 10:30 • Ana Respicio

Folha 7: exercício 6. Folha 8: exercícios 1, 2, 3a), 3b) e 4a), 4b).

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.