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