Writing study: Softmax Transformers are Turing-Complete

ICLR overviewCorpus atlasBy contribution typeVisual galleryRules & templateWriting patternsPaper studies

← ICLR 2026 oral writing corpus

Hongjian Jiang, Michael Hahn, Georg Zetzsche, Anthony W. Lin · Official ICLR 2026 oral record

Observed writing choices, not acceptance rules. This study examines the inspected manuscript version. It does not establish why the paper was accepted or that its presentation choices should be copied unchanged.

Figure, table and section ledger

Editorial contribution type: Theory & formal foundations (primary).

Layout extraction, not a required paper template. Counts are distinct caption labels; a multi-panel figure counts once. Section spans are estimated from heading positions, including floats and whitespace. Method and limitations.

Canonical PDF

21 physical pages

Before references / appendix

≈ 10.21 page-equivalents

Main figures / tables

1 / 1

Attached appendix figures / tables

0 / 2

Attached appendix span

≈ 7.62 page-equivalents

Before references / appendix: ≈ 48.62%References / intervening material: ≈ 15.1%Attached appendix: ≈ 36.29%Estimated layout envelopes, not text/artwork area. Unresolved appendix boundaries remain within the undivided post-body material.

Section-by-section lengths and source pages

The title/abstract/front matter precede the first numbered heading. A span ends at the next detected top-level heading, not at the last sentence; end-page whitespace is included. References and statements are listed separately. These are not measurements of text-only or artwork area.

Top-level heading	Starts on PDF page	Estimated span	Share of entire PDF
1 INTRODUCTION	1	≈ 1.13 pp.	5.38%
2 MODELS FOR TRAINABLE COT TRANSFORMERS	2	≈ 2.84 pp.	13.52%
3 UNARY CASE	5	≈ 2.18 pp.	10.38%
4 GENERAL CASE	7	≈ 2.44 pp.	11.62%
5 EMPIRICAL EXPERIMENTS	10	≈ 0.49 pp.	2.33%
6 CONCLUDING REMARKS	10	≈ 0.51 pp.	2.43%
ACKNOWLEDGMENTS	11	≈ 0.1 pp.	0.48%
REFERENCES	11	≈ 3.17 pp.	15.1%
A ADDITIONAL MATERIAL ON SECTION 2	14	≈ 3.47 pp.	16.52%
B ADDITIONAL MATERIAL ON SECTION 3	17	≈ 0.4 pp.	1.9%
C ADDITIONAL MATERIAL ON SECTION 4	18	≈ 1.04 pp.	4.95%
D ADDITIONAL MATERIAL ON SECTION 5	19	≈ 2.72 pp.	12.95%

All detected figure and table locations

Main text

• Figure 1 · p. 6
• Table 1 · p. 10

Attached appendix

• Table 2 · p. 19
• Table 3 · p. 21

Argument and organization

1. Definitions and staged expressivity results

   Builds the theorem through unary, letter-bounded and permutation-invariant cases before general languages.

2. Construction, experiments and technical appendices

   Separates constructive proof from finite-length supporting experiments and places formal details in section-matched appendices.

Problem, claim and contribution

The introduction contrasts soft attention with earlier hard-attention constructions, then states the additional chain-of-thought and positional assumptions rather than presenting a generic capability benchmark.

Sections 1–2, pp. 1–4 · Main paper

Argument and section order

The progression from counting-friendly languages to arbitrary languages makes the necessity of the encoding phase intelligible; phase I stores an input encoding and phase II simulates a counter machine.

Sections 3–4, pp. 5–9 · Main paper

Figures, captions and visual explanation

A small two-state counter-machine diagram supplies an example repeatedly reused in the construction. Its transition labels match the surrounding equations, although the dense wrapped text leaves little explanatory caption space.

Figure 1 and Example 1, pp. 6–7 · Main paper

Tables, comparisons and evidence

Table 1 groups columns first by representation/position encoding and then by three length splits, so the generalization contrast can be read horizontally without separate plots.

Section 5, Table 1, p. 10 · Main paper

Appendix and reproducibility

The section-matched appendices distinguish formal architectural assumptions from the actual ReLU training implementation and document whole-trace exact match rather than merely answer accuracy.

Appendices A.1–A.4 and D.1–D.2, pp. 14–17, 19–21 · Main paper

Clarity and writing conventions

The headline needs explicit qualification: the proof uses log-length attention scaling, threshold activations and an idealized learner; the learned finite-length experiments do not establish a practical universal-computation guarantee.

Appendices A.1–A.4 and Section 5 · Main paper

What to reuse—and what not to infer

Transferable lesson: For a theoretical paper, organize intermediate cases around the obstacle each removes, reuse one concrete running example, and distinguish theorem assumptions from experimental implementations.

Boundary: Turing completeness permits unbounded computation; the result is not a guarantee for ordinary finite-precision LLMs, SGD or standard RoPE. Table 3 uses different model sizes across encoding conditions, and the main early-stopping description refers to test0, warranting protocol clarification.

Apply this lesson using the argument and evidence worksheet.

Inspection record and sources

Checked

2026-09-19

Reading status

Full text + selected visuals inspected

Main text

Pages 1–10, Sections 1–6; definitions, NoPE construction, general RPE construction and experiments.

Appendix / supplement

Pages 14–21, Appendices A–D, including formal SMAT definition, proofs, learning framework and experimental data/setup.

Visually inspected PDF pages

6, 10

• Official ICLR 2026 proceedings conference PDF; PDF creation metadata: Wed May 13 15:55:44 2026 EDT · 21 pages