A model built from one repeated step
A tag system is a tiny machine that works on a string of symbols. It has a number m, called the deletion number, and a table of production rules, one for each symbol. On every step it does three things:
- Look at the first symbol of the string.
- Append the production attached to that symbol to the end of the string.
- Delete the first m symbols from the front.
It repeats until the string is shorter than m, at which point it halts (some versions define halting with a special symbol instead). The string acts like a queue: symbols leave from the front and new ones join at the back. There is no tape head, no separate state, and no counters.
The idea was introduced by the logician Emil Post in the 1920s, and he studied how hard it is to predict their behavior. It is well documented that even simple-looking systems of this type were difficult to analyze.
A worked example
Take a 2-tag system, so m is 2, with these productions on the symbols a, b and c:
- a becomes bc
- b becomes a
- c becomes aaa
Start with the string aaa and follow it.
- aaa: the first symbol is a, so append bc to get aaabc, then delete two symbols to get abc.
- abc: the first symbol is a, so append bc to get abcbc, delete two, leaving cbc.
- cbc: first symbol c, append aaa to get cbcaaa, delete two, leaving caaa.
- caaa: first symbol c, append aaa to get caaaaaa, delete two, leaving aaaaa.
After four steps, a string of three a’s has become a string of five a’s. Try starting from aa instead. The first step appends bc and deletes two, leaving bc. Then b appends a, giving bca, and deleting two leaves a. The string now has fewer than two symbols, so the system halts.
This particular system is often used as a demonstration because, on strings made only of a’s, its long-run behavior mirrors a rule similar to the famous 3n+1 problem: halve an even number, and for an odd number multiply by three, add one and halve. Our example agrees, since 3 became 5 (that is, (3 times 3 plus 1) divided by 2) and 2 became 1. Whether this process always reaches 1 is a well-known open question, so what looks like a toy is tied to a problem nobody has solved.
Why they can compute anything
Tag systems are not just curiosities. It is known that tag systems, even with deletion number 2, can simulate Turing machines. The sketch of the idea is that the string encodes the machine’s tape and current state, and a carefully designed set of productions makes each rotation of the queue carry out one simulated step. The details of the encoding are intricate, but the principle is the same as in any completeness proof: choose a universal system, then show that the new system imitates it.
A close relative, the cyclic tag system, replaces the table of productions with a fixed repeating list of strings and a single rule: look at the first symbol, and if it is 1 append the next string from the list. Cyclic tag systems are important because they were used in the argument that Rule 110, a very simple cellular automaton, is universal. Linking a one-dimensional automaton to a queue of symbols is exactly the kind of bridge that rewriting rules make possible.
Tiny universal machines
A broader research theme asks how small a universal system can be. Researchers have searched for Turing machines with very few states and symbols that can still simulate any other machine, and for small cellular automata and rewriting systems with the same property. The results are usually stated in terms of “number of states by number of symbols,” and the counts have come down over time. Treat any specific record as something to look up rather than memorize, since such lists get revised.
Two cautions apply to these tiny machines:
- They are universal only through very elaborate encodings. A tiny universal machine may need an enormous, carefully built input to run a simple program, and it may be extremely slow.
- Smallness of the machine does not mean the programs are small or readable. This matches what the broader field of minimalist languages shows: reducing the instruction set moves complexity into the programs.
Connection to esoteric languages
Several esoteric languages are essentially rewriting systems in disguise, and those built on rewriting rules often take their power directly from tag-system-like arguments. Thinking in terms of a queue and productions also helps when reading about counter machines, since two counters and a queue can imitate each other.
For grid programmers, the lesson is encouraging. If a language has a way to store a growing sequence, read from one end, and append to the other, with a few conditional choices, then universality is close at hand. A grid with an instruction pointer that reads and writes cells already has most of those ingredients, which is part of why completeness arguments for such languages are plausible.
Takeaway
Tag systems show that the ingredients of general computation are surprisingly modest: a queue, a fixed table, and the repeated rule of reading one symbol and appending a reply. They are a useful target when proving that another system is universal, because the matching tends to be clean.