Softmax Transformers are Turing-Complete

ICLROral2026

Authors: Hongjian Jiang, Michael Hahn, Georg Zetzsche, Anthony Widjaja Lin
Affiliation: Rheinland-Pfälzische Technische Universität
Venue: ICLR 2026
Track: Oral

TL;DR

Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are Turing-complete.

Opening excerpt from the authors’ abstract. source

Read the paper

OpenReview

Topics

chain-of-thought transformer attention

← All ICLR 2026 Oral papers · Browse the whole archive