THE CONJUGACY PROBLEM AND HIGMAN EMBEDDINGS 5

following relations in Z: 9~lqOT = uqv, 0Ta — a6T for every a E Al)Y (the

letters 0

r

, corresponding to the rules of M are added to the generating set).

In this case the words i^, P[ are of length 1, and are equal to 6T.

The words P and

Pf

contain the history of our computation, because Pi

and P[ correspond to 5-rules applied during the computation. The words

T\ and Tm are labels of the bottom and the top paths of the trapezium.

If the set of relations Z is chosen carefully (and there are very many ways

of doing this, see [SBR, BORS, 01Sa2, OlSal, 01Sa3]), then the converse is

also true:

Condition 1. If there exists a trapezium with the top labelled by I \ ,

the bottom labelled by WQ and the sides labelled by words over O (the set

of all 8T) then T\ is admissible and the labels of the sides correspond to the

history of an accepting computation.

Thus the word PT^P'^W^1 can be written on the boundary of a

trapezium if and only if the word T\ is accepted.

The next step is to consider T V 1 copies of our trapezium with labels

taken from different alphabets. For technical reasons (similar to the hyper-

bolic graphs argument in [SBR], [012], [BORS]) we need T V to be even and

large enough (say, N 8). Let us choose disjoint alphabets in different

copies of the trapezium. Then we can glue two copies of the trapezium by

using a special letter k which conjugates letters from the right side of the

first trapezium with letters from the left side of the mirror image of another

copy (Figure 3):

1 *

P'!\

1 _ •

'

"* 1

PI

_ 4 1

Ti k ^

Figure 3.

(Notice that if P and P' are copies of each other then we can also glue

the right side of one trapezium to the left side of another without taking

mirror images.) Of course the conjugacy relations involving letter k should

be added into the set of group relations Z.