Show The Graduate Center Menu

Topics in Theoretical Computer Science: Computable Model Theory

Instructor: Professor Russell Miller

  • Office:  GC 4432

  • Phone: 718-997-5853 (QC), or 212-817-8142 (GC)

I expect to be at the Grad Center on Tuesdays by 5 pm (often sooner),and all day on Fridays. It is often possible for me to come on on other daysif students want to discuss the course material, so feel free to ask. I teach at Queens College on TuTh 10:30 am -- 1:30 pm.

Tentative Schedule

  • Tuesday, September 3 : Turing machines and computable functions

  • Tuesday, September 10 : (no class)

  • Tuesday, September 17 : Computably enumerable sets

  • Tuesday, September 24 : Recursion Theorem

  • Tuesday, October 1 : 1-reducibility and Σ1-completeness

  • Tuesday, October 8 : Turing reducibility and Turing degrees

  • Tuesday, October 15 :  (no class -- Monday schedule)

  • Tuesday, October 22 : Limit Lemma & Modulus Lemma

  • Tuesday, October 29 : Arithmetical hierarchy & standard Σn-complete sets

  • Tuesday, November 5 : (no class)

  • Tuesday, November 12 : Introduction to computable model theory

  • Tuesday, November 19 : Computable linear orders

  • Tuesday, November 26 : Computable algebraic fields

  • Tuesday, December 3 : Computable categoricity

  • Tuesday, December 10 : Computable fields with transcendentals

  • first rescheduled class : Classic undecidability results: Hilbert's Tenth Problem and/or the Word Problem for finitely presented groups

  • second rescheduled class : Computable groups


For the second half of the course, there is no standard textbook available which covers these topics.  For the first half, the canonical reference is Soare (1987), which is now out of print and being rewritten by the author. All of the books listed below could be useful, and I will not require any single one of them for the course.  For any student with potential interest in continuing the study of this topic beyond this course, though, it would be smart to procure one of these.

  • Lerman, M., Degrees of Unsolvability (Springer-Verlag, 1983)

  • Rogers, H., Theory of Recursive Functions and Effective Computability (McGraw-Hill, 1967)

  • Soare, R.I., Recursively Enumerable Sets and Degrees (Springer-Verlag, 1987)

  • Soare, R.I., Computability Theory and Applications, preprint

Course Topics

This course is intended to introduce students to the disciplines of computable model theory and computable algebra, in which one applies the techniques of computability theory to questions from the rest of mathematics. An extremely fruitful interplay between these topics has developed over the past fifty years. It can be seen as part of computer science (since we are asking about the feasibility of writing programs to solve mathematical problems), and also as part of mathematical logic (since all computability results are in some sense proofs, and all non-computability results demonstrate the independence of the given problem from one of the basic axiom systems for mathematics).

Computability theory explores the theoretical limits of algorithmic computation. We make this concept exact by defining Turing machines, and examining for which subsets of N such a machine can or cannot compute the characteristic function. Thus we define computable and noncomputable sets. We also extend the definition to encompass an oracle Turing machine, which enables us to assign levels of difficulty (the so-called Turing degrees) to the noncomputable sets and, using these degrees, to rank them according to our ability to compute one such set from another.

No previous knowledge of computability or Turing machines is assumed; the first half of the course will be spent familiarizing everyone with these notions and the concepts that follow from them. The second half of the schedule is more tentative: many topics are available to us, and we can go in the direction of the participants' interests, whatever those may be. All the branches listed below (computable linear orders, computable fields, etc.) are current areas of research, but others are also available: computable differential fields, for example, or computable Boolean algebras, or computable analysis, or computability for uncountable structures. Students should feel free to request particular topics.

This area of mathematical logic is known by two distinct names: computability theory, and recursion theory. It is one of the four main branches of mathematical logic, along with model theory, set theory, and proof theory, and is a highly active area of current research, both by established scholars and at the doctoral level. It entered the realm of logic when the notion arose that proof-checking should be an automatic process, feasible even by machine, a notion integral to Gödel's Incompleteness Theorem. It is closely related to theoretical computer science, particularly to computational complexity, which uses stricter definitions of feasibility but many similar notions of reducibility.

The pace of the course will depend on the background and interests of the participants, but a tentative schedule appears below. This is subject to change during the semester. Prof. Miller will be out of town for workshops during the weeks of September 10 and November 5, so we will discuss how to reschedule those two classes to suit everyone's convenience.

Learning Goals

The first goal is for students to acquire a good working knowledge of rigorous computability theory.  The material we cover during the first part of the course, properly understood, provides a springboard either for the study of pure computability theory (as in Soare's textbook, for example), or for applying it to other areas of logic and mathematics.

The second goal is for students to get a feeling for the ways in which computability can be applied to mathematics in general.  Of course, this goal in its entirety would be far too broad for a one-semester course, but the examples we study should help interested students start to take their own steps in this direction.