117b – Unsolvable problems – Lecture 3

At the beginning of the course we built (recursively in ) two incomparable sets . It follows that  and  have degrees intermediate between  and . The construction required that we fixed finite initial segments of and  during an inductive construction and so it is not clear whether they are c.e. or not. (A c.e. construction would add elements to a set and we would not have complete control on what is kept out of the set, so we would not be able to “fix” an initial segment of the set being constructed, as this requires that we keep some elements out of it).

Post asked whether there is an intermediate c.e. degree and this was solved by Friedberg and Muchnik using what is now called a finite injury priority construction. We showed this construction; again, 2 incomparable sets and are built and the construction explicitly shows they are c.e. This implies they are not recursive and have degree strictly below .

117b – Unsolvable problems – Lecture 2

We discussed briefly Church’s and Trakhtenbrot’s theorems: The set of logically valid sentences and the set of sentences valid in all finite models are undecidable. More precisely: If is a language that contains either a binary symbol or the language of arithmetic, then the set of theorems of reduces to the set of validities of , so this set is (r.e. and) undecidable. For the same , we can axiomatize the behavior of a given Turing machine on a given input (by a similar argument to the association of a semi-Thue system to each Turing machine) in such a way that this axiomatization has a finite model iff the machine converges on this input, thus the halting problem reduces to the complement of the set of finite validities, so this last set is (co-r.e. and) undecidable.

We defined Post correspondence systems and showed that the problem of determining whether such a system admits a solution is unsolvable. Two applications to the theory of formal languages follow: There is no algorithm to test whether 2 given context-free grammars have disjoint languages, and there is no algorithm to test whether a given context-free grammar is ambiguous.

117b – Unsolvable problems – Lecture 1

We defined semi-Thue processes and showed (Post, 1947) that for each e there is a semi-Thue process such that the word problem for is Turing-above the halting problem for .

We then proceeded to define Thue processes and showed that they give rise to semigroups. It follows (Post; Markov) that there is a presentation of a semigroup with an unsolvable word problem.

It is easy to modify a Thue process so the semigroup it generates is indeed a group. A modification of the arguments for semigroups shows (Novikov; Boone) that the word problem for groups is unsolvable. In fact (Adjan,Rabin) if is a class of groups closed under isomorphisms and subgroups which neither contains nor is disjoint from the class of finitely presented groups, then there is no algorithm that determines from a given group presentation whether it is in .

Additional references:

• Modular machines, the word problem for finitely presented groups, Collins’ theorem, by Aanderaa, Cohen. In Word problems II. The Oxford book, Adjan, Boone, Higman, eds. North-Holland (1980), 1-16. 
• Modular machines and the Higman-Clapham-Valiev embedding theorem,  by Aanderaa, Cohen. In Word problems II. The Oxford book, Adjan, Boone, Higman, eds. North-Holland (1980), 17-28. 

117b – Homework 8

Due Tuesday, March 13 at noon.