Archive for March, 2007

117b – Unsolvable problems – Lecture 3

March 12, 2007

At the beginning of the course we built (recursively in 0′) two incomparable sets A,B. It follows that A and B have degrees intermediate between 0 and 0′. The construction required that we fixed finite initial segments of A and B 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). 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 show this construction; again, 2 incomparable sets A and B are built and the construction explicitly shows they are c.e. This implies they are not recursive and have degree strictly below 0′.


117b – Unsolvable problems – Lecture 2

March 2, 2007

We briefly discuss 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 L is a language that contains either a binary symbol or the language of arithmetic, then the set of theorems of Q reduces to the set of validities of L, so this set is (r.e. and) undecidable. For the same L, 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 define Post correspondence systems and show 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

March 1, 2007

We define semi-Thue processes and show (Post, 1947) that for each e there is a semi-Thue process \Pi(\varphi_e) such that the word problem for \Pi(\varphi_e) is Turing-above the halting problem for \varphi_e.

We then proceed to define Thue processes and show 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 G 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 G.

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

March 1, 2007

Due Tuesday, March 13 at noon.

Homework 8