AT24 - Redutibilidade-T

13 dezembro 2011, 11:00 • Amilcar Sernadas

Conclusão da aula anterior: lema técnico sobre produtividade; equivalência entre criatividade e completude-m (teorema de Myhill).

Introdução à computabilidade relativa e à redutibilidade-T: resultados básicos.

Introdução à teoria da complexidade: objecto, problemas e notação básica.