Abstract:In studying the theory of computation we seek to determine what can and cannot be computed, how quickly, with how much memory, and on what type of computation model. The subject has obvious connections with engineering practice, and, as many sciences, it also has purely philosophical aspects.

Topics:
0. Introduction
1. Regular Languages
2. Context-free Languages
3. The Church-Turing Thesis
4. Decidability
5. Reducibility
6. Advanced Topics in Computability Theory
7. Time Complexity

Textbook:Introduction to the Theory of Computation , Michael Sipser, PWS Publishing Company, 1997, 新月書局代理