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.