8 A. YU. OLSHANSKII AND M. V. SAPIR

the letter q. Then it is possible to show that the words

qfu\(q')~lU2qr

and

qfvi(qf)~1V2qf (where u\, U2,v\,V2 are words in A') are conjugate in !K if and

only if for some words P, Q

QuiQ~~l = vi,P~1u2P = V2

in the free group and PQ = 1 in

5(Ar),

a copy of S. This problem easily

reduces (exercise!) to the following problem about group S: given four words

s, t,p, r in the alphabet A find two integers m, n such that

stn

=

pmr

in$. It

is quite possible that this problem can be undecidable even if the conjugacy

problem is decidable.

These two examples suggest that we need to change the machine M: we

cannot allow trapezia with top path labelled by words of the form

qu\q~lU2q

having long histories. In other words, if a computation of the 5-machine

starts with

qu\q"1U2q,

then it should not be too long (more precisely, if it

is too long, we should be able to replace it with a shorter computation). If

we achieve that then we would have a recursive bound on the length of the

word W in Example 1 and the words P, Q in Example 2, so we would be

able to find these words by a simple search.

This lead us to the ^-machine § considered in this paper (see Sections

2.3,2.4,2.5). This machine has four sets of state letters: if, L, P, P-letters.

These letters are placed in an admissible word %{u) according to the follow-

ing pattern: KLPRK^R^P^L^KLPR....

The P-letters play the role of the many copies of q in %(qu) above: they

move along an admissible word and "find" places where to insert relations

from £. The if-letters are the letters k{ in %{qu) (they divide admissible

words into copies of the same word and do not move). The L- and P-letters

are "support letters". While P is moving, L, P stay next to if-letters. But

when P "wants" to insert a relation, L, R must move next to P and they

insert the relation "together" (executing the rule LPR — » rLPR, r G £).

After that L , P must move back to their initial positions, and P can move

to a new place in the admissible word (the work of the machine resembles a

complicated dance performed synchronously by several groups of dancers).

It is important to mention that we cannot allow all parts of the admissible

words to be arbitrary group words. To avoid long computations without

inserting new relation from £, we had to require that the words between

neighbor if-letter and P-letter, L-letter and P-letter, P-letter and if-letter

(but not between P-letter and P-letter!) to be positive (i.e. they cannot

contain letters a - 1 ) .

In order to keep these subwords positive we use a trick that goes back

to Novikov, Boone and Higman (see Rotman [Rot]). They used a special

letter x and Baumslag-Solitar relations of the form for every a

in the tape alphabet of the machine. The idea is that if we have relations

a~1xa = x2 for all a E A and a word u~1xu, where u is a reduced word in