Sumários
Aula Teórica 15
5 novembro 2013, 13:00 • Maria Paula Antunes Abrantes Gouveia
Revisões e esclarecimento de dúvidas.
Aula Teórica 14
31 outubro 2013, 12:30 • Maria Paula Antunes Abrantes Gouveia
Demonstração de que a linguagem \(E_{TM}\) (problema da linguagem vazia) não é decidível. Noção de redução de uma linguagem a outra linguagem.
Decidibilidade e diagonalização: exercícios.
29 outubro 2013, 14:30 • João Rasga
Resolucão dos exercícios da aula 5: 2.2.b, 2.2.c, 3.1.a e 3.1.b. Resolução do exercício 2.e da aula 6.
Aula Teórica 13
29 outubro 2013, 13:00 • Maria Paula Antunes Abrantes Gouveia
Sequências de hailstone e conjectura de Collatz. Demonstração de que a linguagem \(HALT_{TM}\) (problema da paragem) não é decidível. Demonstração que a linguagem \(EQ_{TM}\) (problema da igualdade de linguagens) não é decidível, assumindo como provado que o problema \(E_{TM}\) (problema da linguagem vazia) não é decidível.
Aula Teórica 12
24 outubro 2013, 12:30 • Maria Paula Antunes Abrantes Gouveia
Demonstração de que a linguagem \(A_{TM}\) é semi-decidível mas não é decidível. Demonstração de que a linguagem complementar de \(A_{TM}\) não é semi-decidível.