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) Hyperbolic groups. Hyperbolic groups are finitely generated. Hyperbolic groups have decidable word problem. There exist hyperbolic groups whose generalized word problem.

3) 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

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

5) 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 (1), 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.


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


Date Description


Due Date Homework Solutions