Entender os limites do que é computável na teoria e na prática. Dominar os conceitos, técnicas e resultados fundamentais da teoria da computabilidade. Conhecer diversos modelos de computação e entender a sua equivalência. Conhecer as noções básicas da teoria da complexidade.