Sumários

Classes P, NP e NP-completude

22 Novembro 2017, 08:00 • Ana Respicio

Folha 10 - exercícios 2,3,4,5 e 6.

Linguagens decidíveis e linguagens não decidíveis. Diagonalização.

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

Folha 10.

Decidibilidade

21 Novembro 2017, 09:30 • Ana Respicio

O problema da igualdade das linguagens geradas por duas GIC não é computacionalmente resolúvel.

Qualquer linguagem independente do contexto é decidível. Prova.
Relação entre classes de linguagens e os respetivos modelos computacionais.
O problema de aceitação por uma máquina de Turing não é computacionalmente resolúvel. 
A liguagem A_TM é Turing-reconhecível. Prova.
Estudar: Sipser cap 4.Praticar: Folha de exercícios 8.

Máquinas de Turing e decidibilidade

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

Folha 7: exercício 6.

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

Máquinas de Turing e decidibilidade

17 Novembro 2017, 11:30 • Jorge Miguel Carvalho Gomes

Folha 7: exercício 6.

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