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