Computer Theory
Algorithms, sets, induction and cardinality. Turing machines. Recursive functions. Markov algorithms. The Church-Turing thesis. Undecidability. Intractable problems. Classes of intractable problems.
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.