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