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
• Transformers from Scratche2eml.school
• Thinking Like Transformersarxiv.org
• On the Tradeoffs of SSMs and Transformers | Goomba Labgoombalab.github.io
• Transformer Circuits Threadtransformer-circuits.pub
• Memory makes computation universal, remember?thinks.lol
• Transformer Explainer: LLM Transformer Model Visually Explainedpoloclub.github.io
• The Annotated Transformernlp.seas.harvard.edu
• Transformer (deep learning) - Wikipediaen.wikipedia.org
• Understanding Transformers... (beyond the Math) – kalomaze's kalomazing blogkalomaze.bearblog.dev
• [1807.03819] Universal Transformersarxiv.org
• Transformer (deep learning) - Wikipediaen.wikipedia.org