Introduction to the Theory of Computation
This course covers the basic topics in the theory of computation from a
Programming language concepts; the computational power of a programming
language; metaprogramming; equivalence of languages of different styles,
leading to Church's thesis and the concept of a
reasonable complete programming language.
Computable and uncomputable functions; decidability; semidecidability;
the classes R and RE, reducions, Rice's theorem.
Models for complexity; time complexity, the classes P, EXP
and NP. NP-hardness and NPC.
The textbook that best matches the course is (not surprisingly) my own
Additional literature includes:
Computability and Complexity from a Programming
Neil D. Jones.
David Harel (also available in Hebrew, by Open