Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Constant Bit-size Transformers Are Turing Complete
Authors: Qian Li, Yuyi Wang
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that constant bit-size transformers are Turing complete. Specifically, given any TM, there exists a transformer with fixed numerical precision and a fixed number of parameters that can simulate the TM on inputs of arbitrary length, provided that the transformer s context window is sufficiently long. |
| Researcher Affiliation | Collaboration | Qian Li Shenzhen International Center For Industrial And Applied Mathematics, Shenzhen Research Institute of Big Data Shenzhen, China EMAIL Yuyi Wang CRRC Zhuzhou Institute & Tengen Intelligence Institute Zhuzhou, China EMAIL |
| Pseudocode | No | The simulation of the Post machine by the transformer is described procedurally in Section 3, including numbered steps for Token embedding layer, Positional encoding layer, Decoder layer, and Output layer, with mathematical equations, but it is not presented in a formal pseudocode block or algorithm environment. |
| Open Source Code | No | The NeurIPS checklist question 5 explicitly states: "This paper does not include experiments requiring code." |
| Open Datasets | No | The paper is theoretical and focuses on proofs and complexity classes. It does not describe any experimental work that would require datasets. The NeurIPS checklist indicates no experiments are included. |
| Dataset Splits | No | As this is a theoretical paper, no datasets are used for experimental evaluation, and therefore no dataset splits are provided. |
| Hardware Specification | No | This paper is purely theoretical and does not involve running experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical and does not describe any implementation details or software used for experiments. The NeurIPS checklist confirms no experiments are included. |
| Experiment Setup | No | This is a theoretical paper that does not involve experimental work, thus there are no details on experimental setup or hyperparameters. |