Compiling Turing Machines into
Storage Modification Machines

It is well known that Schönhage’s Storage Modification Machines [4] can simulate Turing Machines (TM) [5]. Simulation of small universal TM, or other simple universal models such as Post’s tag systems [1] and the cellular automaton Rule 110 [6], is by now a standard way to prove that a large number of alternate models of computation, including a variety of physically-inspired systems, are computationally universal. In the following, we consider a slightly revised version of Schönhage’s Storage Modification Machine (SMM) and offer a simple construction to simulate the behavior of a TM. This construction sets the base for a generic TM-to-SMM compiler.

Turing Machines, masquerading as read-write-head-and-tape mechanic contraptions, are in fact quite mathematical, theoretical models of computation. They are best viewed as abstract machines (metaphorically) manipulating symbols on a strip of tape according to a table of rules. In a simplified design, the infinite tape is divided into contiguous cells, each cell having a right- and a left-neighbor, which may or not exhibit a symbol (from a given, usually finite, alphabet). The head when positioned over a cell can read or write this cell’s symbol. Finally the machine is characterized by a state, also from a given, usually finite, state-set.

An elementary execution step of such a TM is summarized as follows:

1. 1.

   Read the current cell’s symbol $\sigma$ (or blank, if no symbol is present).

According then to the combination of current state and symbol in the transition table, $(S,\sigma)$:

1. 2.

   Write back a symbol $\sigma^{\prime}$ on the current cell.

2. 3.

   Move head to one of the two neighbors of the current cell.

3. 4.

   Change internal state to $S^{\prime}$.

The behavior of this simple TM is entirely specified by its transition table which states, for each relevant $(S,\sigma)$ combination, the data required to perform steps 2, 3 and 4 above.

In our construction, this data is simply a string which concatenates the symbol $\sigma^{\prime}$, the constant $L$ (left) or $R$ (right) to indicate which contiguous neighbor to target in step 3, and finally the new state $S^{\prime}$ of the TM.

Running a TM involves (i) positioning the head on a tape with some initial symbols in some cells, (ii) setting some state as the initial one, and (iii) start consecutively executing the above steps. By convention when no combination of state and symbol is found in the transition table, the machine halts¹¹1The whole point of Turing in his original 1936 paper was to provide a mathematical description of a very simple device capable of arbitrary computations, and prove properties of computation in general – and in particular, the uncomputability of the Entscheidungsproblem (decision problem) of predicting whether a so specified TM would halt or move forever, reading and writing symbols..

Storage Modification Machines presented here are from a variant in [2] where they are used to implement population protocol models. Like a TM, a SMM represents a single computing agent. It is equipped with memory and a processing unit. Its memory stores a finite directed graph of equal out-degree nodes [4], with a distinguished node called the center. (Edges of this graph are also called pointers.) Edges leading out of each node are uniquely labelled by distinct directions, drawn from a finite set $D$.

Any string $x\in D^{*}$ refers to the node $p(x)$ reached from the center by following the sequence of directions labelled by $x$. (Note that this is somehow similar to moving the head in a TM.) In the variant used here, nodes may have different out-degrees, and we set $p(x)=\emptyset$ when $x$ is not a valid path in the graph.

SMM are furthermore characterized by a program, or control list, which is a finite list of consecutively numbered instructions (reminiscent of the transition tables in TM). The restricted instruction set is as follows:

• •

  new label creates a new labelled node and makes it the center, setting all its outgoing edges to the previous center.

• •

  set xd to y where $x,y$ are paths in $D^{*}$ and $d\in D$ is a direction, redirects the $d$ edge of $p(x)$ to point to $p(y)$.

• •

  center x where $x$ is a path, moves the center to $p(x)$.

• •

  if x y then ln where $x,y$ are paths and ln a line number, jumps to line ln if $p(x)=p(y)$ and skips to the next line if not. Line numbers can be absolute, ln, or relative to the current line number, +ln or -ln.

• •

  stop message halts the SMM, printing out message.

The similarities highlighted above between TM and SMM are our guidelines to the specification of a generic transformation of the TM transition table to appropriate sequences of SMM instructions.

More specifically, elaborating on these similarities: each TM tape cell and each position of the head over it are represented by a node in the compiled SMM, with one dedicated direction, say f, pointing from head to cell and cell to head.

The symbol on the tape cell is simply the binary representation of its index in the alphabet, using $n$ specialized directions in the tape node, where $n$ is the integer immediately superior to the base-2 log of the alphabet size. The state of the TM is encoded in a head node in the same way, the binary representation of its index in the state-set using $m$ specialized directions (which may be in common with the former $n$ ones, without confusion as a node is either a tape or a head).

A special direction in both type of nodes, say o, always points to a fixed initial node, the Origin. The center of the SMM is set to the current position of the TM head, i.e. the SMM head node linked to the current tape cell tape node.

By convention, the binary representation bits in nodes are $0$ when their direction points to self, and $1$ when their direction points to the fixed Origin.

Finally tape nodes are doubly-linked using two specialized directions, e and w (for east and west); their corresponding head nodes (in the f direction) are doubly-linked in the same way. The compiled SMM has then $4+max(n,m)$ directions.

The TM compiler is built as a sequence of code generation/decoration passes:

• •

  State Selection. Build a decision tree based on the state binary representation over the $m$ bit directions, using SMM controls if <B> o to test each <B> bit direction.

• •

  Symbol Detection. At each leaf of the previous tree, build a decision tree based on the symbol binary representation over the $n$ bit directions. At each leaf of each of these new trees, add the control list implementing the $(\sigma,S)$ transition found in the TM table: binary encode the new symbol on the current tape node; move to the e or w head node as indicated in the transition (possibly creating new SMM nodes in the process, if they do not exist, hence simulating an infinite tape); finally encode the new state in this head cell, and make it the center. This reproduces the steps 2-4 of the TM.

• •

  Prologue. Prefix the control list resulting from the previous passes with a specific control list setting up the initial tape and symbols, the initial head position and the initial state.

The compiled SMM is ran stepwise: the initial prologue to set up the TM as a first mandatory step, followed by a sequence of calls to the above transition control list. Each call to the SMM execution step implements a full transition in the TM execution.

Schönhage’s Storage Modification Machines can generally simulate Turing Machines. This paper provides an alternate construction of such SMM simulations which finds its use in a Turing Machine to SMM compiler . Related questions on the minimal (space) complexity SMM required for simulation of complex Turing Machines may then be addressed by looking into optimizing this simple TM-to-SMM compiler.