THE CONJUGACY PROBLEM AND HIGMAN EMBEDDINGS 11

2.2 A n auxiliary group

Let S be a group given by the following presentation

9 = (ai,...,a

m

|w = l,w G £), (2.1)

where £ is a recursively enumerable set of words in ai,. .., am. Adding if

necessary, new generators and relations of the form a^a^ = 1 one can assume

that the set £ consists of positive words only, i.e., there are no occurrences

of

a~l

in the words w G £.

We first prove Theorem 1.1 and then show how to modify the proof

to obtain Theorem 1.2. So we shall assume that 9 has solvable conjugacy

problem.

By the Higman Embedding Theorem [Rot] there is a finitely presented

group 9 generated by ai,..., am,..., a^ containing 3 as a subgroup. By

Clapham-Valiev's result [Cla, Va], one can assume that the word problem in

9 is decidable.

Besides, one may assume that again, for each generator a of 9, the inverse

letter

a1

is also included in the set of generators {ai,..., am,..., a^} of 9- For

every a G {ai,..., a^}, we assume that there are positive relators of the form

aa' and a'a in the finite set £ of positive defining relators for 9- We will also

suppose that if r G £ then r' G £ where r' is obtained from r

_ 1

by replacing

every occurrence of a letter a

- 1

by the letter a'. Finally, we will assume that

£ contains the empty word 0. It is clear that £ is a presentation of the group

9 in the class of all monoids, so we have the following

Lemma 2.1. Assume that w\ = W2 for positive group words w\,W2 in

the generators of$. Then there is a sequence of positive words starting with

w\ and ending with W2, where every word in the sequence is obtained from

the previous word by insertion or deletion of a subword w G £.

The list of relations of the group !K which we are going to construct will

depend on the set £ of defining words for 9- Lemma 3.9 below claims that

there is a natural embedding of the subgroup 5 5 into IK, but (caution!)

we will not embed the whole group 9 into K.

2.3 T h e hardwar e of S

The group *K that we are going to construct is associated with two very

similar 5-machines, 8 and S. We shall describe the S'-machines, then we will

describe how to convert these machines into a group presentation.

We fix an even number N 8.

The set % of state letters of S consists of letters Zj(r,i) where z G

{K, L, P, R}, j = 1,..., N, rel,iE {1,2, 3,4, 5}.