Computer Theory

Syllabus: 

Algorithms, sets, induction and cardinality. Turing machines. Recursive functions. Markov algorithms. The Church-Turing thesis. Undecidability. Intractable problems. Classes of intractable problems.

Bibliography

Mandatory: 

•    Brainerd, W. S., & Landweber, L. H. (1974). Theory of Computation. John Wiley & Sons. 
•    Diverio, T. A., & Menezes, P. B. (1999). Computer Theory: Universal Machines and Computability. Sagra-Luzzatto. 
•    Epstein, R. L., & Carnielli, W. A. (2008). Computability: Computable Functions Logic and the Foundations of Math. Advanced Reasoning Forum. 

Complementary: 

•    Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2001). Introduction to Automata Theory, Languages and Computation (2nd ed.). Addison Wesley. 
•    Sipser, M. (2007). Introduction to Computer Theory. Thomson Pioneer. 
•    Sipser, M. (2006). Introduction to the Theory of Computation. Cengage Learning. 
•    Gurari, E., & Gurari, E. (1989). An introduction to the theory of computation (Vol. 338). Computer Science Press Rockville. 
•    Manna, Z. (2003). Mathematical theory of computation. Courier Dover Publications.