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

Suppose that Tm is equal to g, i.e. the word T\ is acceptedby the machine.

If we connect the first copy of A with the second copy, then with the third

copy, and finally connect the iV-th copy with the first copy, using different

letters &2, ••• &/v &i

w e

get an annular diagram, a rinp. The outer boundary

of this ring has label %{T\) of the form

fciT[fc^"1(r(,)_1...

(here we use the fact

that N is even). The words T{,..., T{ are different copies of T\. The inner

boundary has label fciVfc^"1^")-1... (this word is called the /m&) (Figure 4

shows the diagram in the case N = 4):

Figure 4.

We add the hub to the list of defining relations Z. Now with every word T

of the form uqv where u, v are words in A U Y we have associated the word

3C(T), and we see that if T is accepted then %(T) is equal to 1 modulo Z.

Again, if Z is chosen carefully then the converse is also true:

Condition 2. If %{T) is equal to 1 modulo Z then T is accepted by

§. Thus we have an interpretation of S in the group generated by the tape

alphabet and the state alphabet of S, the set O, and the set {fci,..., fc/v}5

subject to the relations from Z.

The diagram on the previous Figure is called a disk. The trapezia forming

this disk are numbered in the natural order (from 1 to N).

We assume that the copy of the alphabet A used in the first subtrapezium

of a disk coincides with A itself (the generating set of S)-

Let us denote the group given by the presentation Z we have got so far

by G(M).

There are several ways to use the group G(M) to embed S into a finitely

presented group. We cannot use the method used by Higman [Hi], Aanderaa

[AC], Rotman [Rot], and us in [BORS] because it leads to problems discov-

ered by Collins in [Col]. We use another method, described in [01Sa2] and

used also in [01Sa3].