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

Aristotelis Panagiotopoulos
Office. 102 Linde
panagio at

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:

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

HW1. (Solutions),
HW2. (Solutions),
HW3. (Solutions),
HW4. (Solutions),
HW5. (Solutions),

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.