Here we will explain why we need to convert Turing machines into S-machines.
Consider any Turing machine M. For simplicity assume that M has one tape, which is always finite, but we can add squares at the right end of the tape, the alphabet A of tape letters, the set Q of states, and the set R of transitions. As usual we assume that the head is always placed between two squares of the tape, and observes both squares. So the transitions have the form where u, v, u', v' are words in the tape alphabet, (see [37] for details). Then using the same idea as in the construction of Gm,n we can replace the relations qir=aqi by (uqv)r=u'q'v' (here r is a letter associated with the transition of M). As in [37] we assume that M has only one accept configuration W0.
Thus we have the following presentation of the group G(M) associated with M.
As before, we need N copies of each of these relations written in disjoint alphabets. The hub relation will have the form K(W0) where W0 is the accept configuration.
Now it is easy to see that for every accepted word U we can tessellate the disc with boundary label K(U) into cells labeled by these relations. Let be an accepting computation. As before we will have a sequence of concentric circles, each labeled by K(Ui), the innermost oval will be labeled by K(W0).
So it is easy to see that the word K(U) is equal to 1 in G(M) if the configuration U is accepted by M.
Unfortunately the converse statement is wrong in most cases and this is precisely why we need S-machines. Let us demonstrate this on a simple example. Consider the following Turing machine M. It has two states q, q0 and one tape letter a. The only transitions are the following:
The accept configuration is q0 (the tape is empty). It is clear that the set of configurations accepted by this machine consists of configurations anq0 and amq where , and does not include, for example, the configuration q. Thus we would like K(q) to be not equal to 1 in G(M). The diagram on Figure 5 shows that K(q) is equal to 1 in this group.
This picture shows the tessellation of only one of the sectors. The other sectors are tessellated in the same way.
One can easily see the difference between this picture and the standard picture of a disc. Here we have pairs of cells which have two common edges, but in the standard disc, cells could have at most one common edge.
The diagram on Figure 6 is a subdiagram of the diagram on Fig. 6. It consists of two cells corresponding to the relations r2a=ar2 and (aq0)r2=q0 and has boundary label corresponding to the relation (q0)r2=a-1q0 which is the relation corresponding to the rule , the inverse rule for .
It is possible to prove that the group G(M) actually simulates the S-machine with the set of admissible words anq, anq0 and the set of rules
In general if we take any Turing machine M and repeat this construction we will get a group simulating the S-machine obtained by replacing every transition by the S-rule . This S-machine will almost always be much stronger than the original Turing machine.
One way around this problem was invented by Boone and Novikov [37]. This is why they used the Baumslag-Solitar type relations xa=x2. These relations prevent appearance of negative letters on the ``tape" (the concentric circles in the disc). But we could not use these relations because they make the Dehn function exponential.
Thus we had to prove instead that S-machines are polynomially equivalent to ordinary Turing machines (Theorem 18).