Fetching the paper…
Reading the bibliography…
We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer, as long as the context window is sufficiently long.
Finite combinatory processes—formulation1
E. L. Post · 1936
Earlier work this paper cites.
Universal sequential search problems
L. A. Levin · 1973
Earlier work this paper cites.
Randomness conservation inequalities; information and independence in mathematical theories
L. A. Levin · 1984
Earlier work this paper cites.
The complexity of propositional linear temporal logics
A. P. Sistla and E. M. Clarke · 1985
Earlier work this paper cites.
Computability, complexity, and languages: fundamentals of theoretical computer science
M. Davis, R. Sigal, and E. J. Weyuker · 1994
Earlier work this paper cites.
On the complexity of k-sat
R. Impagliazzo and R. Paturi · 2001
Earlier work this paper cites.
Optimal ordered problem solver
J. Schmidhuber · 2004
Earlier work this paper cites.
Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
R. A. Hearn and E. D. Demaine · 2005
Earlier work this paper cites.
Universal artificial intelligence: Sequential decisions based on algorithmic probability
M. Hutter · 2005
Earlier work this paper cites.
Computational complexity: a modern approach
S. Arora and B. Barak · 2009
Earlier work this paper cites.
Language models are unsupervised multitask learners
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, et al · 2019
Earlier work this paper cites.
Measuring mathematical problem solving with the math dataset
D. Hendrycks, C. Burns, S. Kadavath, A. Arora, S. Basart, E. Tang, D. Song, and J. Steinhardt · 2021
Cited alongside, same era.
Attention is turing-complete
J. Pérez, P. Barceló, and J. Marinkovic · 2021
Cited alongside, same era.
J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat, et al · 2023
Cited alongside, same era.
Towards revealing the mystery behind chain of thought: a theoretical perspective
G. Feng, B. Zhang, Y. Gu, H. Ye, D. He, and L. Wang · 2023
Cited alongside, same era.
Gemini: a family of highly capable multimodal models
T. Gemini, R. Anil, S. Borgeaud, J.-B. Alayrac, J. Yu, R. Soricut, J. Schalkwyk, A. M. Dai, A. Hauth, K. Millican, et al · 2023
Position: The no free lunch theorem, kolmogorov complexity, and the role of inductive biases in machine learning
M. Goldblum, M. A. Finzi, K. Rowan, and A. G. Wilson · 2024
Later among the works it cites.
Meta ai, open source, limits of llms, agi & the future of ai, 2024
Y. Lecun · 2024
Later among the works it cites.
Chain of thought empowers transformers to solve inherently serial problems
Z. Liu, H. Liu, D. Zhou, and T. Ma · 2024
Later among the works it cites.
The expressive power of transformers with chain of thought
W. Merrill and A. Sabharwal · 2024
Later among the works it cites.
Ask, and it shall be given: Turing completeness of prompting
R. Qiu, Z. Xu, W. Bao, and H. Tong · 2024
Later among the works it cites.
Limits of deep learning: Sequence modeling through the lens of complexity theory
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Swe-bench: Can language models resolve real-world github issues?
C. E. Jimenez, J. Yang, A. Wettig, S. Yao, K. Pei, O. Press, and K. Narasimhan · 2023
Cited alongside, same era.
The parallelism tradeoff: Limitations of log-precision transformers
W. Merrill and A. Sabharwal · 2023
Cited alongside, same era.
Gpqa: A graduate-level google-proof q&a benchmark
D. Rein, B. L. Hou, A. C. Stickland, J. Petty, R. Y. Pang, J. Dirani, J. Michael, and S. R. Bowman · 2023
Cited alongside, same era.
The claude 3 model family: Opus, sonnet, haiku, 2024
Anthropic · 2024
Cited alongside, same era.
A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Yang, A. Fan, et al · 2024
Cited alongside, same era.
N. Zubić, F. Soldá, A. Sulser, and D. Scaramuzza · 2024
Later among the works it cites.
Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning
D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al · 2025
Closest in time.
A little depth goes a long way: The expressive power of log-depth transformers
W. Merrill and A. Sabharwal · 2025
Closest in time.
Simulating time with square-root space
R. R. Williams · 2025
Closest in time.
Pencil: Long thoughts with short memory
C. Yang, N. Srebro, D. McAllester, and Z. Li · 2025
Closest in time.