Why S-machines?

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 $uqv\to u'q'v'$ where u, v, u', v' are words in the tape alphabet, $q,q'\in Q$ (see [37] for details). Then using the same idea as in the construction of G_m,n we can replace the relations q_i^r=aq_i 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 W₀.

Thus we have the following presentation of the group G(M) associated with M.

• (uqv)^r=u'q'v', for every transition $r=[uqv\to u'q'v']$ of the machine M,
• ar=ra, for every $a\in A$ and every transition r
• kr=rk, for every $k\in\{k_1,...,k_N\}$ and every transition r.

As before, we need N copies of each of these relations written in disjoint alphabets. The hub relation will have the form K(W₀) where W₀ 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 $U=U_1\to U_2\to ...\to U_p=W_0$ be an accepting computation. As before we will have a sequence of concentric circles, each labeled by K(U_i), the innermost oval will be labeled by K(W₀).

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, q₀ and one tape letter a. The only transitions are the following:

(r₁)

$aq\to q_0$,

(r₂)

$aq_0\to q_0$.

The accept configuration is q₀ (the tape is empty). It is clear that the set of configurations accepted by this machine consists of configurations aⁿq₀ and a^mq where $n\ge 0, m>0$, 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.

Fig. 5.

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 r₂a=ar₂ and (aq₀)^r₂=q₀ and has boundary label corresponding to the relation (q₀)^r₂=a^-1q₀ which is the relation corresponding to the rule $[q_0\to a^{-1}q_0]$, the inverse rule for $[q_0\to aq_0]$.

Fig. 6.

It is possible to prove that the group G(M) actually simulates the S-machine with the set of admissible words aⁿq, aⁿq₀ and the set of rules

• $q\to a^{-1}q_0$,
• $q_0\to a^{-1}q_0$.

plus the inverse rules. This S-machine is ``stronger" than M, it accepts more configurations, including the configuration q.

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 $uqv\to u'q'v'$ by the S-rule $[q\to u^{-1}u'q'v'v^{-1}]$. 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 x^a=x². 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).