Ma 117c:  Computability Theory (Spring 2016-17)


Registration for Spring term opens Thursday, February 23, 2016.

This page was last updated:  .






TR 10:30 - 11:55, 159 Sloan.


Martino Lupini
260 Sloan


There are no TAs for this course       


By appointment.



The grade will be assigned base on a final presentation given by each student on a topic related with the subject of the course, such as one of the following:

1)  Residually finite groups. Residually finite finitely presented groups have decidable word problem. There exist residually finite recursively presented groups with undecidable word problem. Algbraically closed groups. A finitely generated group has decidable word problem if and only if it embeds into every algebraically closed group. See Reference (1), Chapter IV Section 4 and Section 8.

2) Wang tiles. The problem of determining whether, given a finite set of Wang tiles, there exists a tiling of the entire plane, is undecidable. See Reference 5

3) Decidability of homeomorphism of compact manifolds. See Chapter 2 of Reference 4.

4) Z is definable in Q in the language of rings. The complete theory of Q is undecidable. See Reference 6.

Inspiration for othe possible topics can be found in Reference 3.


Lecture 1: Semi-Thue process. The word problem for a semi-Thue process. Review of deterministic and nondeterministic Turing machines. Reduction from the halting problem of a Turing machine to the word problem of the corresponding semi-Thue process. Thue processes, and algebraic interpretation. See Reference (2), Chapter 7, Section 1 and 2.

Lecture 2: Reduction from the halting problem of a deterministic Turing machine to the word problem of the corresponding Thue process. Group presentations. The word problem for groups. See Reference (1), Chapter 7, Section 3 and Reference (2), Chapter II, Section 1 and 2.

Lecture 3: Review of constructions from group theory: free products, amalgamated free products, and HNN extensions. Britton's lemma for HNN extensions. The notion of bening subgroup. Bening subgroups are closed under intersections and products. See Reference (2),  Chapter IV, Section 1, Section 2, and Section 7.

Lecture 4:  Review of the Nielsen--Schreier theorem, and Nielsen-reduced sets of generators. Proof the Higman embedding theorem continued: the Higman rope trick. See Reference (2), Chapter I, Section 2, and Chapter IV, Section 7.

Lecture 5: Proof of the Higman embedding theorem continued: the "principal lemma"; see Reference (2), Chapter IV, Section 7.

Lecture 6: Conclusion of the proof of the Higman embedding theorem.

Lecture 7: Undecidability of the Post correspondence problem.

Lecture 8: Formal grammars, context-free grammars, leftmost derivations. Undecidability of the ambiguity problem for context-free grammars. Undecidability of the mortality problem for finite sets of integer matrices.

Lecture 9: The notion of quantifier elimination. A criterion for quantifier elimination. The theory of dense linar orders with no end points has quantifier elimination. A semantic characterization of sentences equivalent to quantifier-free sentences. The isomorphism condition and the submodel condition for a theory.

Lecture 10: The isomorphism condition and the submodel condition for a theory imply quantifier elimination. The theory of algebraically closed fields has quantifier elimination. The theory of algebraically closed fields of a fixed characteristic is complete and decidable.

Lecture 11: Real closed fields. Axioms for real closed fields. The theory of real closed fields is complete, decidable, and has quantifier elimination. Proof of Hilbert's 17th problem (Artin's theorem) for rational functions over the real field using quantifier elimination of the theory of real closed fields. See Reference 7, Theorem 8.4.4 and Reference 8, Section 3.

Lecture 12: Divisible torsion-free abelian groups. The theory of divisible torsion-free abelian groups is complete, decidable, and has quantifier elimination. The same holds for ordered divisible torsion-free abelian groups. The notion of k-categorical theory for a cardinal k. See Reference 9, Section 2.2 and Section 3.1.

Lecture 13: The Cayley graph of a finitely generated group. The normal subgroup lemma. Hyperbolic groups. Isoperimetric inequality for hyperbolic groups. Hyperbolic groups are finitely presented and have decidable word problem. See Reference 2, Chapter V Section 1, and Reference 10, Sections 2,3,5

Lecture 14: The generalized word problem. Small cancellation condition C'(1/6). Rips' theorem: there is a finitely presented group satisfying the smalle cancellation condition C'(1/6) with undecidable generalized word problem. A group satisfying the small cancellation condition C'(1/6) is hyperbolic (sketch). See Reference 11, Reference 2, Chapter V, Section 2, and Reference 10, Section 6.


There is no official textbook for this course. Here is a list of recommended references.

1) Davis, Sigal, Weyuker. Computability, complexity, and languages. Fundamentals of theoretical computer science. Second edition. Computer Science and Scientific Computing. Academic Press, Inc., Boston, MA, 1994. xx+609 pp. ISBN: 0-12-206382-1 

2) Lyndon, Schupp. Combinatorial group theory. 

3) Poonen. Undecidable problems: a sampler

4) Weinberger. Computers, rigidity, and moduli

5) Ollinger. Two-by-two substitution systems and the undecidability of the domino problem 

6) Robinson. Definability and decision problems in arithmetic

7) Hodges. Model theory

8) Marker. Quantifier Elimination and Applications. Notes available at

9) Marker. Model Theory: An Introduction

10) S.M. Gersten. Introduction to hyperbolic and automatic groups. Available at

11) E. Rips. Subgroups of small cancellation groups


Date Description


Due Date Homework Solutions