Tag system
Tag systems are a class of string-rewriting systems that act on a dataword by repeatedly deleting a fixed number of symbols from the beginning and appending an associated production word for each alphabet symbol, and are specified by a deletion number and a finite alphabet.5 Despite their minimal rule set, they are computationally universal and their halting problem is undecidable.1 Emil Post formulated the halting and reachability decision problems for the systems and spent nine months of research on them, underestimating the complexity that so simple a form could produce.6 Minsky (1961) proved that any Turing machine can be represented as a tag system, and Cocke and Minsky (1964) proved the universality of 2-tag systems,1 • 2 which Woods and Neary (2006) showed simulate Turing machines in polynomial time.4
| Key fact | Detail |
|---|---|
| Universality | Minsky (1961) proved any Turing machine can be represented as a tag system; Cocke and Minsky (1964) proved 2-tag systems universal1 • 2 |
| Halting problem | Undecidable; the halting problem of a tag system can be of complete degree 0′1 • 3 |
| Efficient simulation | Woods and Neary (2006) showed 2-tag systems simulate Turing machines in polynomial time, an exponential improvement over previously known overheads4 |
| Minimum alphabet | Tag systems with only 2 symbols, the minimum possible, are universal with polynomial time overhead (Neary, 2013)2 |
| Applications | Undecidability of the Post correspondence problem for 4 pairs of words and of matrix mortality for five 3×3 matrices2 |
Definition and operation
A tag system acts on a dataword, a string of symbols from a finite alphabet. It is specified by a deletion number and, for each alphabet symbol, an associated word (the production).
Two parameters measure the size of a tag system in the literature: the deletion number and the alphabet size5. A tag system halts when its word becomes shorter than the number of elements removed at the beginning1.
The balance between deletion and addition governs the possible behavior. If the number of symbols added is never greater than the number deleted, the resulting behavior is at most cyclic; allowing additions of unbounded length produces the most complex behavior1.
Post's program
Post formulated two decision problems for his system, now known as the halting problem and the reachability problem. The halting problem asks, for a given tag system and any initial word, whether the system will halt when started from that word; the reachability problem asks, for a given tag system, a fixed initial word, and an arbitrary word, whether the system will ever produce that word6. Post spent nine months of research on tag systems, starting from simpler cases and attempting to scale the results, and underestimated the complexity that so simple a form could produce6.
Universality
By proving that any Turing machine may be represented as a tag system, Minsky (1961) established universality and the undecidability of halting for tag systems; the result was subsequently improved by Cocke and Minsky (1964) and by Wang (1963)1. Cocke and Minsky proved the universality of 2-tag systems, which since then have been used extensively to prove the universality of numerous computational models2. Wang (1963) also considered a kind of opposite to a tag system, which he called a lag system1.
Tag-system simulation became a standard route to small universal Turing machines.
Time complexity of simulation
For decades the known simulations through tag systems were exponentially slow, and it was open whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi, and Kudlek were efficient simulators7. In 2006, Damien Woods and Turlough Neary, computer scientists then at the University of Seville and University College Dublin respectively, showed that 2-tag systems efficiently simulate Turing machines, and as a corollary that the small universal Turing machines of Rogozhin, Minsky, and others simulate Turing machines in polynomial time4. This was an exponential improvement on the previously known simulation time overhead and improved a forty-year-old result in the area4. Related work showed that the elementary cellular automaton Rule 110 is also efficiently universal7.
In 2013, Neary proved universality for tag systems with only 2 symbols, the minimum possible, via an intricate construction simulating cyclic tag systems with polynomial time overhead; all previously known universal 2-tag systems had a large number of symbols2.
Decision problems and applications of undecidability
The halting problem for tag systems is undecidable, and its degree of unsolvability can be the complete degree 0′3. Decidability returns at the smallest parameter values: for tag systems with a single-symbol alphabet the halting problem is solvable5, and for the case where both the alphabet size and the deletion number equal 2 a decidability criterion applies8.
Undecidability as a tool. Because binary tag systems simulate Turing machines in polynomial time, their halting problem serves as a convenient starting point for reductions. Neary reduced the halting problem for binary tag systems to the Post correspondence problem for 4 pairs of words, improving the previous bound of 7 pairs; since the problem is decidable for 2 pairs, only the 3-pair case remained open2. The same result showed that the matrix mortality problem is undecidable for sets of five 3×3 matrices and for sets of two 15×15 matrices, improving the previous bounds of seven 3×3 matrices and two 21×21 matrices2.
Average-case complexity. A tag system can efficiently simulate a Turing machine even when the input is given in an extremely simple encoding that adds only log n carefully set bits to encode a Turing machine input of length n. As a result, the bounded halting problem for nondeterministic tag systems is average-case NP-complete, the first average-case completeness result for so simple a model of computation9.
References
- Tag System, Wolfram MathWorld
- Turlough Neary (2013). Undecidability in binary tag systems and the Post correspondence problem for four pairs of words. arXiv.
- Decision problems for tag systems, Journal of Symbolic Logic, Cambridge Core
- Damien Woods and Turlough Neary (2006). On the time complexity of 2-tag systems and small universal Turing machines. arXiv.
- Jacob Weightman (2025). Solving Simple Tag Problems
- Let's Be Logical (Ghent University publication discussing Post's tag work)
- Turlough Neary and Damien Woods (2011). The complexity of small universal Turing machines: a survey. arXiv.
- Solvability of the Halting and Reachability Problem, CiteSeerX
- Average-Case Completeness in Tag Systems, STACS 2019, Dagstuhl
Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Formal languages and automata theory › Grammar formalisms and generating systems
Initially written Oct 15, 2026 · Edited: Oct 25, 2026
Your notes
© 2026 EdgeChat AI, a subsidiary of Biostate AI. Free to use with credit under the Edgepedia Community License. Developers: read Edgepedia by API or MCP. Embed a reference card.