THE CONJUGACY PROBLEM AND HIGMAN EMBEDDINGS 9
A, is equal modulo these relations to a power of x then the first letter of u
is positive.
We use a similar idea. But our task is more complicated than in [Nov,
Bo, Hi] because we need to consider conjugacy of arbitrary pairs of words,
not only those that have "nice" structure. So we had to use many different
letters x, replace 2 by 4 in the Baumslag-Solitar relations, and make some
other technical modifications. Notice that one problem with using the x-
letters and Baumslag-Solitar relations is that since T V 1 is odd we cannot
use x-letters in the second disk described above (indeed, otherwise it would
be impossible to glue the T V 1 sectors together since the words P and
P' would not be copies of each other). Thus we need to consider two S-
machines (one responsible for the first disk, another for the second disk)
which are very similar but have different "hardware": the admissible words
of the first machine must have positive parts described above, the admissible
words of the second machine do not have to satisfy this restriction.
Notice that Examples 1 and 2 are only the main obstacles that we had
to overcome in this paper. Other technical difficulties lead to further fine
tuning of our S-machine. Sections 2.7, 2.8, 2.9 contain precise description
of the presentation of our group !K.
Now let us briefly describe the strategy of the proof that the conjugacy
problem in !K is Turing reducible to the conjugacy problem in S. As in our
previous papers the main tool in this paper is bands (other people call them
"strips", "corridors", etc.).
In terms of annular (Schupp) diagrams, our task is the following: given
two words u and v in generators of !K, find out if there exists an annular
diagram over the presentation of !K with boundary labels u and v. It turns
out that any annular diagram over % (after removing some parts of recur-
sively bounded size) becomes a diagram of one of three main types: a ring
(where the boundary labels contain K-, L-, P-, P-letters but do not con-
tain ^-letters, all maximal 0-bands are annuli surrounding the hole of the
diagram), a roll (where the boundary label does not contain K-, L-, P-,
P-letters but contain ^-letters; all maximal K-, L-, P-, P-bands are annuli
surrounding the hole), and a spiral (where the boundary labels contain both
K-, L-, P-, or P-letters and ^-letters; both K-, P-, P-, P-bands and the 6-
bands start and end on the different boundary components, and each #-band
crosses each K-, L-, P-, and P-band many
times2).
Different methods are
used to treat different cases. Roughly speaking, the study of rings amounts
to study the lengths of computations of our S'-machines, the study of rolls
amounts to the study of the space complexity (how much space is needed
by the machines during a computation), and the study of spirals amounts
to the study of computations with periodic history. The x-letters and the
2In that case the #-band looks like a spiral on a plane that starts at the origin and
crosses certain straight lines (the K-, L-, P- and i?-bands) many times.
Previous Page Next Page