Course.
Math 117b Winter 2019
1:00 - 2:25 TR, 387 LINDE

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

Office hours. Mondays 3-4PM (I will also hold office hours this Thursday (the 17th) 4-5 PM

A few words. In the beginning of the 20th century various paradoxes resulted to a crisis in the foundations of mathematics. Hilbert put forward a new proposal for the foundation of mathematics which has come to be known as Hilbert's Program. The goal of the program was to find complete and consistent axiomatizations for classical mathematical theories such as real analysis and arithmetic. Gödel's incompleteness theorems put a definite end to (at least the most ambitious parts of) this program.

In this course we will develop further some recursion theory from math 117a and provide applications in the broader setting of mathematics. We will prove Gödel's Incompleteness Theorems and it's variants and we will discuss examples of undecidable problems from logic, number theory, group theory, and combinatorics

Homework.
HW1. (Solutions),
HW2. (Solutions),
HW3. (Solutions),
HW4. (Solutions),
HW5. (Solutions),
HW6. (Solutions),
HW7. (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, 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.