THE CONJUGACY PROBLEM AND HIGMAN EMBEDDINGS 3
paper, so the notation here does not necessarily coincide with the notation
in the rest of the paper.
We consider the case when S = (A | £) has decidable conjugacy prob-
lem and we want to embed it into a finitely presented group with decidable
conjugacy problem (the case when the conjugacy problem in S has arbi-
trary r.e. Turing degree is similar). The standard idea is to start with
a machine which recognizes the set £ and then interpret this machine in
a group. Of course we would like to have a machine which is easier to
interpret. The most suitable machines for our purposes are the so called
S-machines invented by the second author in [SBR] and successfully used in
[SBR, BORS, OlSal, 01Sa2, 01Sa3]. An S-machine works with words which
can have complicated structure determined by the problem. Different parts
of these words can be elements of different groups (so we do not distinguish
words whose corresponding parts are equal in the corresponding groups). As
in Turing machines, every rule of an S-machine replaces subwords containing
state letters by other subwords. For an exact definition of S-machines see
Section 2.1. For now the reader can imagine just an ordinary Turing machine
which works with words from the free group instead of a free monoid.
Here we give just one example of an S-machine which essentially goes
back to C. Miller [Mil] (although Miller did not use S-machines). The real
S-machine used in this paper is a "descendant" of this S'-machine (obtained
from Miller's machine by several "mutations"). Assume that A is a sym-
metric set that is it contains the formal inverses of its elements, and let us
embed S = (A | £) into some finitely presented group S (AUY | £) using,
say, the standard Higman embedding. Now consider the S'-machine M with
one state letter q and the tape alphabet AUY considered as a generating set
of the free group, and the following commands (each command says which
subwords of a word should be replaced and the replacement word):
[q -+
a~1qa]1
for every a E AUY,
[q rq], for every r £ £.
The first set of rules allows the state letter to move freely along a word of
the form uqv where u,v are words from the free group on AUY. Such words
are called admissible words for M.
The second set of rules allows us to insert any relation from £ into the
word (we are also allowed to insert and remove subwords of the form
aa~l
because A U Y is a generating set of a free group).
It is easy to see that a word qu, where u is a word over A, is recognized
by this machine (that is the machine takes it to the word q) if and only if
u 1 in the group S, that is if and only u = 1 in S (because S is embedded
into
S).1
1 Notice that by a result of Sapir [01Sa2], for every Turing machine T there exists an
Previous Page Next Page