Sumários
Máquinas de Turing e decidibilidade
17 Novembro 2017, 08:00 • Jorge Miguel Carvalho Gomes
Folha 7: exercício 6.
Máquinas de Turing e Decidibilidade
15 Novembro 2017, 08:00 • Ana Respicio
Folha 7: exercício 6. Folha 8: exercícios 1, 2, 3a), 3b) e 4a), 4b).
Máquinas de Turing e decidibilidade
14 Novembro 2017, 11:00 • Jorge Miguel Carvalho Gomes
Folha 7: exercício 6.
Máquinas de Turing e decidibilidade
14 Novembro 2017, 10:30 • Ana Respicio
Folha 7: exercício 6. Folha 8: exercícios 1, 2, 3a), 3b) e 4a), 4b).
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.