Transformers Can Compute Anything
Commentators often claim that large language models will always fail at certain tasks because of fundamental architectural limits. Those claims are wrong. Transformer models are Turing-complete. They can implement any computable algorithm. The proof is straightforward: multilayer perceptrons handle arbitrary computation, and attention mechanisms provide writable memory. Together they form a complete computational substrate.
How the Compiler Works
To demonstrate this, a compiler was built that translates a simple assembly language directly into weights for a standard Llama transformer. No training occurs. The compiler emits weights that execute the provided program. The resulting model runs the program through inference alone. You can run this compiler yourself at the project page.
Context as Memory
The model's context window serves as a memory store. Writing a value v to address x emits two tokens that encode the address and the value. Standard rotary positional embeddings (RoPE) enable most-recent-write lookup through attention. This creates a functional memory system where reads retrieve the latest value written to each address.
Append-Only Design and Compaction
The evaluator uses append-only memory. New writes extend the context rather than overwriting old positions. Context compaction functions like garbage collection, reclaiming space by removing stale entries. This design keeps the implementation simple while maintaining correctness.
Implications for Architecture Decisions
Since LLMs can learn arbitrary assembly, they can learn any computable function by construction. There is no completeness reason to abandon transformer architectures. Any future architecture shift would rest on efficiency grounds alone, not on theoretical capability gaps.