LLMs Are Turing-Complete

The piece argues that transformer-based large language models are Turing-complete and therefore can implement any computable algorithm. The demonstration constructs a compiler that translates a simple assembly language directly into a set of Llama transformer weights without any gradient training; the model’s token context functions as writable memory by emitting address/value token pairs. Standard MLP layers provide arbitrary computation while attention mechanics - using RoPE (rotary positional encodings) at a deliberately low frequency - implement a last-write-wins lookup, enabling most-recent-write retrieval. Simple programs like Fibonacci and the Sieve of Eratosthenes are shown as examples, and context compaction is presented as a form of garbage collection for the append-only memory.

The consequence drawn is that there is no theoretical completeness reason to abandon transformers: they can learn or be built to execute any algorithm, so architecture debates reduce to efficiency trade-offs rather than expressiveness. Important caveats are acknowledged: an explicit construction doesn’t guarantee typical training will discover such implementations; real systems have finite context and word sizes (so physically realizable models aren’t infinite Turing machines); and practical choices like RoPE frequency affect how memory semantics are implemented.