Better Turing Machines

When Percepta posted this delightful demo, one of the reactions I saw online was: "How is this new? Didn't we already know that transformers are Turing complete?" That got me curious about the evolution of the result that transformers are Turing complete, and now I want to talk a little bit about that evolution and why it matters that the result evolved. To illustrate part of that discussion, here's a demo of a particular way to emulate a Turing machine with a transformer. We'll get back to it.

The first paper with the headline result that transformers are Turing complete is On the Turing Completeness of Modern Neural Network Architectures (Pérez et al., ICLR 2019), whose follow-up journal version is Attention is Turing-Complete (Pérez et al., JMLR 2021). But what does that headline mean? It promises us that for every Turing-computable function, it is possible to cook up a transformer which computes that function. No promise is made that the transformer so cooked will have any nice properties, or have the particular kind of transformer architecture we prefer, or be practical to implement on physical computers.

And indeed this original proof (of the equivalent statement that for every language accepted by a Turing machine there exists a transformer which recognizes that language) gives us a somewhat user-unfriendly transformer: it requires arbitrary precision starting at the positional encodings. As soon as one sits down to implement one of these transformers, one must reckon with the fact that one's processors were not designed for arbitrary precision. And so room is left for other authors in other papers (or in other corporate blog posts) to produce refinements of the original theorem which still only produce transformers which simulate Turing machines, but manage to produce transformers with one or another desirable property.

From my point of view, thinking ahead to the demo you find on this page, certain improvements in particular are desirable. Right away I see that I want fixed or at least conveniently bounded precision; Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (Li et al., ICLR 2024) gets me fixed precision. But it does so at the cost of increasing embedding dimension with increasing input size, and you can see in the demo above that I allow you to enter inputs of variable length. Thus, in fact, I want fixed specification of the transformer so that I don't have to cook a fresh one every time the input gains one character; and it is Constant Bit-size Transformers Are Turing Complete (Li and Wang, NeurIPS 2025) which finally gets me that: their transformers have constant precision and constant embedding dimension, and it is the context window and number of CoT steps which grow with input size.

This is a proof of the Turing completeness of transformers, but it is both more elegant and more practical than the Pérez et al. proof with the same headline, and I am grateful that Li and Wang were curious enough to find the improvement. Their proof relies on the equivalence between Turing machines and Post machines.¹ A Post machine, or queue automaton, consists of a finite control equipped with a queue. Li and Wang prove a particular specification of the equivalence, their Theorem 2: "Given any single-tape TM running in t(n) time and s(n) space, there is an equivalent PM running in O(t(n)×s(n)) time and using a s(n)-size queue." (There is an error² in their proof, but it is both fixable and inconsequential.) Then, instead of simulating the Turing machine directly, the paper simulates the corresponding Post machine, with the rotations of its queue playing out in the context window of the transformer, except for the leftmost cell of the queue which is encoded into the part of the PM state we call its register.

The demo above runs transformers built on this model. They simulate Turing machines which in one case compute the addition of 1 to decimal integers and in the other case run the bubble sort algorithm on an alphabet of {a, b, c}. The proof in the paper has the Post machine queue rewind twice for every simulated leftward move of the Turing machine head; since this can be improved,³ each transformer comes in two rewind variants: a faithful implementation of the paper's algorithm and an improved version minus the redundant rewind and extra symbols to support it. Each frame of the demo animation is driven by a forward pass of an actual transformer: embedding, then positional encoding, then a hardmax self-attention layer, then a ReLU feed-forward layer,⁴ then the output layer. The transformers are compiled rather than stored; when compiled, they have the following embedding dimensions d, vocabulary sizes |V|, and numbers of small integer weights:

Notes

1. Li and Wang here cite the wrong paper by Post, one which proposes what is commonly called a Post-Turing machine. The queue automata here called Post machines are descended from Post's 1943 paper Formal Reductions of the General Combinatorial Decision Problem (sometimes incorrectly cited in the literature with "General" replaced by "Classical"), where he proves a universality result about string generation systems which today we read as stating a fact about queues. This idea was developed the rest of the way by Zohar Manna in his 1974 book Mathematical Theory of Computation; the equivalence between Turing machines and Post machines is his Theorem 1-3. Here Li and Wang again cite the wrong lineage, crediting the result to a textbook of Davis et al. which proves the corresponding theorem about Post-Turing machines rather than Post machines.
2. The error in Appendix B, Proof of Theorem 2, appears in the authors' description of how the PM simulates a step of the TM when the TM head moves right, in the subcase where the PM appends a blank to the queue. After behaving as the authors describe, the PM holds the new blank cell at the rightmost position in its queue. But this is the TM head's cell, and a new TM step is about to begin, and the invariant condition that is supposed to hold at the start of every TM step in the proof states that the TM head's cell must be leftmost in the PM's queue. This can be fixed by a rotation of the queue, which does not alter the big-O time used by the simulation. Moreover, the error proves inconsequential because the version of this PM actually used in the proof of Theorem 4 is altered to behave differently with respect to blank cells.
3. The idea is to remove the ~ diacritic from the PM alphabet, relax the invariant condition to allow the ^ diacritic to appear on the leftmost symbol in the queue, and strip diacritics from symbols on their way into the register. Since the simulated TM head reads from the leftmost end of the logical queue — i.e., the register — it only ever sees symbols in the diacritic-free alphabet.
4. The paper has another error here: they take the residual stream to be |V|-dimensional, when in fact it has the embedding dimension d. This trivializes their output layer. The transformers that run on this page implement the paper's intent rather than its written specification: the feed-forward layer serves as a lookup table for the PM's transition function and the output layer decodes the resulting embedding back into a token.