## 117b – Unsolvable problems – Lecture 1

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.