We define *semi-Thue processes* and show (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 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*.*

### Like this:

Like Loading...

*Related*

This entry was posted on March 1, 2007 at 4:49 pm and is filed under 117b, Unsolvable problems. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply