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

ANNOUNCEMENTS

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

This page was last updated:  .


COURSE DESCRIPTION

TBA


PREREQUISITES

TBA


SCHEDULE

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


INSTRUCTORS

Martino Lupini
HARRY BATEMAN INSTRUCTOR IN MATHEMATICS
260 Sloan
626-395-4346


TA's

There are no TAs for this course       


OFFICE HOURS

By appointment.


POLICIES

Grades

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.


TOPICS COVERED

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.


TEXTBOOKS

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


LECTURE NOTES

Date Description
   
   
   

HOMEWORK

Due Date Homework Solutions
     
     
     
     
     
     
     
     

EXAMS

 


READING