MA554: Computability and complexity Grenoble INP | ESISAR | 2010
Most of this material is a translation and compilation of other material.

Theory and practical sessions by Alejandro Díaz-Caro

Lecture notes: PDF (TeX)

Exercise sheets

  • Exercise sheet 1 Grammars and automata. PDF (TeX)
  • Exercise sheet 2 Turing machines. PDF (TeX)
  • Exercise sheet 3 Decidability. PDF (TeX)
  • Exercise sheet 4 Primitive recursive functions. PDF (TeX)
  • Exercise sheet 5 Recursive functions. PDF (TeX)
  • Exercise sheet 6 Review (TP1). PDF (TeX)
  • Exercise sheet 7 Complexity. Give the complexity of all the TM's designed in Exercise sheet 2
  • Exercise sheet 8 Review (TP2). To finish TP1

Corrections of the TP. PDF (TeX)