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

Now let us present the ideas of a Higman embedding based on M. Let

Ti, T2,..., Tm = WQ be an accepting computation of M, that is a sequence of

admissible words such that T^+i is obtained from Ti by applying an S'-rule

of M, the last word in this sequence is equal to q in the free group.

Suppose that modulo some set of group relations Z we have for every

2 = 1, ..., m — 1

PtTt = Ti+lPl

for some words Pi and P[ over a certain alphabet (it is included in the

finite generating set of the group we are constructing), that is we have a van

Kampen diagram with the boundary label P^T^(P/) _ 1 T^

1

(Figure 1):

Ti

i+l

Pi

IP'

Figure 1.

(the set Z describes the method of tessellating this rectangle into cells). Then

we have that PTX = W0Pf where P = Pm^1...P2Pi1 P[ = P^_V..P^P[. The

corresponding van Kampen diagram A has the form of a trapezium:

n

Ti

Figure 2.

For example, if we use the ^-machine M described above then the pre-

sentation Z is easy to describe: for every rule r ~ [q — uqv] we have the

^-machine 3V C corresponding a to a group % as above which is polynomially equivalent to

T. This shows that machines JV C are as powerful as ordinary Turing machines.