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}.
Previous Page Next Page