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