Are Transformers Turing-complete? A Good Disguise Is All You Need.

Transformer architectures cannot simulate computer programs. They are not Turing-complete, despite what several papers have claimed.

I will avoid an introduction and get straight to it. I’ll assume that you know what Turing-complete means, that you are familiar with transformers , and that you care about the question: Are transformers Turing-complete? (I may later write about what that question means and why it is important.) Several papers claim that transformers are Turing-complete and therefore capable of computing any computable function. But I believe these claims are all misleading. Some make conceptual errors and are simply incorrect in their claims of Turing-completeness for their models. Others have modified

related reading

• A Mathematical Framework for Transformer Circuitstransformer-circuits.pub
• Thinking like Transformersrush.github.io
• Looped Transformers as Programmable Computersarxiv.org
• [1807.03819] Universal Transformersarxiv.org
• Transformers from Scratche2eml.school
• Thinking Like Transformersarxiv.org
• Memory makes computation universal, remember?thinks.lol
• Transformer Circuits Threadtransformer-circuits.pub
• On the Tradeoffs of SSMs and Transformers | Goomba Labgoombalab.github.io
• Can LLMs Be Computers?percepta.ai
• 2402.12875arxiv.org
• Transformer Explainer: LLM Transformer Model Visually Explainedpoloclub.github.io