Sumários

9 Dezembro 2016, 08:00 • Alexandre Miguel dos Santos Martins Pinto

Folha 9: exercícios 1, 2, 3, 4, 5, 6, 11a

7 Dezembro 2016, 09:30 • Ana Respicio

Redutibilidade.

Teorema 5.22, Sipser. Prova. Corolário 5.23, Sipser.
Decidibilidade.

Teorema 4.22, Sipser. Prova.

Corolário 4.23, Sipser. Prova.

Problemas indecidíveis da Teoria da Computação.

HALT_TM é indecidível (Sipser, Teorema 5.1). Prova.

7 Dezembro 2016, 08:00 • Ana Respicio

Folha 8 - exercícios 4, 5, 7 e 8.

6 Dezembro 2016, 11:00 • Alexandre Miguel dos Santos Martins Pinto

Folha 8:

Exercícios 4, 5, 7, 8.

6 Dezembro 2016, 10:30 • Ana Respicio

Folha 8 - exercícios 4, 5, 7 e 8.