Simplest Turing-complete ruleset for Markov algorithm

Question

Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?

Answer 1

Rule 110 is universal, and can be expressed as a Markov algorithm.

In particular, Rule 110 corresponds to the Markov system with alphabet $\{0,1,\verb!^!,|,\$ \}$ and a pair of bits for each element in the automaton. The pair of bits records the current status of that element (empty or filled) and the previous status. Elements are updated by doing a left-to-right scan; the marker $|$ keeps track of where we are in the scan, $\verb!^!$ indicates the start of the string, and $\$$ indicates the end of the string. We obtain the following $2^6 + 2^2 + 2^6 = 132$ rewriting rules:

• $uv|wxyz \to uvxt|yz$ where $t = \text{Rule110}(u,x,z)$,
• $|uv\$ \to vv\$ $
• $\verb!^! uvwxyz \to \verb!^! vv|wxyz$

where $u,v,w,x,y,z$ are meta-variables that range over $\{0,1\}$. In other words, the first bullet item corresponds to $2^6$ rewriting rules: $00|0000 \to 0000|00$, $00|0001 \to 0001|01$, etc.; the second bullet item corresponds to $4$ rewriting rules, corresponding to all possible ways to assign $0$ or $1$ to $u$ and $v$; and the third bullet item corresponds to $2^6$ more rewriting rules.

What's going on with this crazy re-writing system? It's actually not as ridiculous as it looks. For a cellular automaton with $n$ elements, we start with a string of length $2n+2$ of the form $\verb!^! 0x_1 0x_2 0x_3 \dots 0x_n \$ $, where each $x_i$ is $0$ or $1$ according to whether that element is empty or filled.

The interpretation of the pair of symbols $uv$ is that the current status of the element is given by $v$, and the previous status is given by $u$. We scan over the elements from left to right, updating the status of each element. The marker $|$ indicates where we are in the scan right now. Notice that we need to keep track of both the previous and current state of each element, which is why I use a pair of bits for each element rather than one bit per element.

The first bullet item takes care of the left-to-right scan. The second bullet item makes sure that the scan terminates, and removes the $|$ marker. The third bullet item ensures that if there is no $|$, then we re-start the scan starting at the left.

---

You can also play a similar trick with any Turing machine, and thus emulate a universal Turing machine with a Markov algorithm.

Suppose we have a Turing machine with tape alphabet $\Gamma$ and finite state space $Q$. Then the Markov system has alphabet $\Sigma = \Gamma \cup Q \cup \{\text{<}\}$. The idea is that the string $t_1 t_2 \cdots t_i \text{<} q t_{i+1} \cdots t_n$ corresponds to a configuration of the Turing machine that has $t_1 t_2 \cdots t_i t_{i+1} \cdots t_n$ on its tape, has state $q$ in its finite-state control, and where the head is positioned over $t_i$ in the tape. The marker $\text{<}$ indicates the current position of the head.

Then it's easy to write a finite set of rewriting rules that correspond to the operation of the Turing machine. In particular, the behavior of the Turing machine depends only on the symbol under the head and the state of the finite control. Thus, we'll get a set of rewriting rules of the form $t \text{<} q u \to t' u \text{<} q'$ (for transitions where the head moves right) and $s t \text{<} q \to s \text{<} q' t'$ (for transitions where the head moves left). Since the finite-state control has only finitely many state transitions, we'll need only finitely many rewriting rules in the Markov algorithm.

Finally, we can apply this to your favorite universal Turing machine. The smaller the universal Turing machine, the simpler the resulting Markov algorithm will be.