S-machines

First of all let us present some ideas how to find a group with an ``arbitrary" Dehn function. Consider again the main diagram called a disc on Figure 5 for the group G_m,n.

The disc is divided by the k-bands into N sectors. The words written on the circles between consecutive k's have the form

uq₁uq₂uq₃

and to pass from one level to another level we replace q_i by aq_i. So we can imagine these words written on a tape of a Turing machine, where q_i marks the places where the heads are, and we have a rule of the form

$$[q_1\to aq_1, q_2\to aq_2, q_3\to aq_3]$$

for every a.

What we get is a simple example of a so called S-machine.

Roughly speaking, the difference between S-machines and ordinary Turing machines is that S-machines are almost ``blind". They ``see" letters written on the tape only when these letters are between two heads of the machine and the heads are very close to each other. If the heads are far apart, the machine does not see any letters on the tape, in this case a command executed by the machine depends only on the state of the heads.

In contrast, ordinary Turing machines can see letters on the tape near the position where the head is. The command executed by the machine always depends not only on the state of the head but (which is very important!) also on the letter(s) observed by the head. Notice that even for moving the head of a Turing machine one square to the left, one needs to know the content of the square to the left of the head.

Let us give a precise definition of S-machines. Let k be a natural number. Consider now a language of admissible words. It consists of words of the form

q₁u₁q₂...u_kq_k+1

where q_i are letters from disjoint sets Q_i, i=1,...,k+1, u_i are reduced group words in an alphabet Y_i (Y_i are not necessarily disjoint), the sets $\bar Y=\bigcup Y_i$ and $\bar Q=\bigcup Q_i$ are disjoint.

Notice that in every admissible word, there is exactly one representative of each Q_i and these representatives appear in this word in the order of the indices of Q_i.

If $0\le i\le j\le k$ and W= q₁u₁q₂...u_kq_k+1 is an admissible word then the subword q_iu_i...q_j of W is called the (Q_i,Q_j)-subword of W(i<j).

An S-machine is a rewriting system [23]. The objects of this rewriting system are all admissible words.

The rewriting rules, or S-rules, have the following form:

$$[U_1\to V_1,...,U_m\to V_m]$$

where the following conditions hold:

Each U_i is a subword of an admissible word starting with a $Q_\ell$-letter and ending with a Q_r-letter (where $\ell=\ell(i)$must not exceed r=r(i), of course).

If i<j then $r(i) < \ell(j)$.

Each V_i is also a subword of an admissible word whose Q-letters belong to $Q_{\ell(i)}\cup...\cup Q_{r(i)}$ and which contains a $Q_\ell$-letter and a Q_r-letter.

If $\ell(1)=1$ then V₁ must start with a Q₁-letter and if r(m)=k+1 then V_n must end with a Q_k+1-letter (so tape letters are not inserted to the left of Q₁-letters and to the right of Q_k+1-letters).

To apply an S-rule to a word W means to replace simultaneously subwords U_i by subwords V_i, i=1,...,m. In particular, this means that our rule is not applicable if one of the U_i's is not a subword of W. The following convention is important:

After every application of a rewriting rule, the word is automatically reduced. We do not consider reducing of an admissible word a separate step of an S-machine.

We also always assume that an S-machine is symmetric, that is for every rule of the S-machine the inverse rule (defined in the natural way) is also a rule of this S-machine. This reflects the fact that the r-edges in the disc on Figure 5 can point away from the hub or toward the hub.

Notice that virtually any S-machine is highly nondeterministic.

Among all admissible words of an S-machine we fix one word W₀. If an S-machine ${\cal S}$ can take an admissible word W to W₀ then we say that ${\cal S}$ accepts W. We can define a time and space function of an S-machine as usual. If $Z\to Z_1\to...\to Z_n=W_0$ is an accepting computation of the ${\cal S}$-machine ${\cal S}$ then |Z|+|Z₁|+...+|Z_n| is called the area of this computation. This allows us to define the area function of an S-machine.

Theorem 18 (Sapir, [38])   S-machines are polynomially equivalent to (non-deterministic) Turing machines. More precisely for every Turing machine Mwith time function T(n) there exists an S-machine with area function T(n)⁴ which is equivalent to M (this means that there exists a correspondence $\phi$ between configurations of M and admissible words of ${\cal S}$, given a configuration c, the word $\phi(c)$ is computable in linear time, and the machine M accepts c if and only if ${\cal S}$ accepts $\phi(c)$).  

In fact a stronger theorem can be deduced from the main results of [38]. It was recently proved by Sapir.

Theorem 19 (Sapir, 1998)   For every Turing machine M with time function $\le T(n)$ such that T(n)⁴ is superadditive, there exists an S-machine ${\cal S}$ with one head and only one internal state which is equivalent to M and has time function $\le T(n)^4$.  

Notice that an S-machine with one head and one state letter is completely blind (in the sense explained above). The rules of such an S-machine have the following very simple form:

$$[q\to uqv]$$

where q is the internal state, u and v are words in the tape alphabet.

The amazing fact is that the proof of a completely Computer Science statement, Theorem 19, involves some heavy geometric group theory. We first convert M into an S-machine ${\cal S} _1$ with many heads, then convert ${\cal S} _1$ into the group from [38] with Dehn function T(n)⁴, then convert the group into an S-machine ${\cal S}$ with one head and one internal state, having time function T(n)⁴ (in the last step we use an idea from Miller [27]).

The group $G_N({\cal S} )$ associated with an S-machine ${\cal S}$ is constructed in the same way as the group G_m,n presented above. We add all rules of ${\cal S}$ to the set of generators and for every rule r of the form $[U_1\to V_1,...,U_p\to V_p]$ we have p relations U₁^r=V₁,...,U_p^r=V_p. These relations replace the relations q_i^r=aq_i in the presentation of G_m,n. The other relations are the same.

Although this construction slightly differs from the construction in [38] it is possible to prove the following statement.

Theorem 20 (Sapir, [38])   Every nondeterministic Turing machine M with time function T(n) can be converted into an S-machine ${\cal S}$ in such a way that the Dehn function of the group $G_N({\cal S} )$ is T(n)⁴ provided T(n)⁴ is superadditive.

Now in order to embed a finitely generated group G into a finitely presented group we take a Turing machine M recognizing words which are equal to 1 in G, convert it into an S-machine ${\cal S}$, and then basically repeat the construction of the group H_m,nreplacing B(m,n) by G and G_m,n by $G_N({\cal S} )$. The resulting group is denoted by $H_N({\cal S} )$. It plays the role of group H in Theorem 14.