Redutibilidade. Decidibilidade

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.