117b – Unsolvable problems – Lecture 1

We defined semi-Thue processes and showed (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 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 {mathcal 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 {mathcal 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. 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: