Course.
Math 117c Spring 2019
1:00 - 2:25 TR, 225 LINDE

Instructor.
Aristotelis Panagiotopoulos
Office. 102 Linde
panagio at caltech.edu

Office hours. Mondays 3-4PM (Please contact me if this time is not convenient for you)

This is going to be a topics course in computability. Among others we will cover:

• the word problems for groups;
• quantifier elimination and decidable theories;
• computational complexity;
• dependence of P=NP from oracles;
• The Paris Harrington theorem and the independence of Ramsey theoretic statements from Peano arithmetic;
• recursion theoretic forcing and undefinability of definability.

Time permitting we will also cover some basic effective descriptive set theory.

Homework.
HW1. (Solutions),
HW2. (Solutions),
HW3. (Solutions),
HW4. (Solutions),
HW5. (Solutions),
HW6.
HW7. FINAL

Books and notes. The will be no textbook for this course. I will be posting notes on a weekly (more or less) basis. That being said these notes will be brief and will not include every single detail so I advise to keep your own personal notes. As in math 117a and b, a useful list of books on computability theory have been reserved in the library:

H. Hermes, Enumerability, Decidability, Computability, Springer-Verlag, 1970.
Y. Manin, A Course in Mathematical Logic for Mathematicians, Springer, 2010.
M. Carey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
Handbook of Mathematical Logic, J. Barwise, Ed., North-Holland, 1977.
M. Machtey and P. Young, An Introduction to the General Theory of Algorithms, North-Holland, 1978.
A. Yasuhara, Recursive Function Theory and Logic, Academic Press, 1971.
G. Boolos, J. Burgess and R. Jeffrey, Computability and Logic, Cambridge Univ. Press, 2002.
N. Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge Univ. Press, 1980. M. Davis, Computability and Unsolvability, Dover, 1985.
E. Engeler, Introduction to the Theory of Computation, Academic Press, 1973.
M. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
B. Trakhtenbrot, Algorithms and Automatic Computing Machines, D.C. Heath, 1963.
A. Malcev, Algorithms and Recursive Functions, Noordhoff, 1970.
H. Lewis and C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1997.
H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press, 1987.
G. Tourlakis, Theory of Computation, Wiley, 2012.
H. Enderton, Computability Theory, Academic Press, 2011.
M. Sipser, Introduction to the Theory of Computation, Course Technology, 2005.
M. Davis, R. Sigal and E. Weyuker, Computability, Complexity and Languages, Morgan Kaufmann, 1994.
R. Weber, Computability Theory, Amer. Math. Society, 2012.
D. Bridges, Computability: A Mathematical Sketchbook, Springer, 1994.

Home. Back to my website.