A Formulation of Recursive Self-Improvement and Its Possible Efficiency
Open accessAbstract
Recursive self-improving (RSI) systems have been dreamed of since the early days of computer science and artificial intelligence. However, many existing studies on RSI systems remain philosophical, and lacks clear formulation and results. In this paper, we provide a formal definition for one class of RSI systems, and then demonstrate the existence of computable and efficient RSI systems on a restricted version. We use simulation to empirically show that we achieve logarithmic runtime complexity with respect to the size of the search space, and these results suggest it is possible to achieve an efficient recursive self-improvement.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Gödel Agent can theoretically make increasingly better modifications over time through recursive self-update.
“G¨ odel Agent can theoretically make increasingly better modifications over time through recursively self-update (Wang, 2018).”
From Gödel Agent: A Self-Referential Agent Framework for Recursive Self-Improvement (2024) · cites this paper as Wang, 2018
The Introduction (p. 1) describes recursive self-improving systems that iteratively create better software, and the mathematical example (p. 2) shows a program updating to better-scored programs. The paper does not establish this claim specifically for a “Gödel Agent”; it mentions Gödel machines only in its references (p. 8). (LLM, conf=0.83)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Bounded Recursive Self-ImprovementPreprint
Nivel, E., Þórisson, K. R., Steunebrink, B. R., Dindo, H., Pezzulo, G., Rodríguez, M., Hernández, C., Ognibene, D., Schmidhuber, J., Sanz, R., et al. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.6764 · Cited by 25 · see citing works
From Seed AI to Technological Singularity via Recursively Self-Improving SoftwarePreprint
Yampolskiy, R. V. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.06512 · Cited by 9 · see citing works
Flagged first, then by citations
Research works printed but not linked: 5
- [1]1. Chalmers, D.J.: The singularity. Science Fiction and Philosophy: From Time Travel to Superintelligence, Second Edition pp. 171-224 (2010)
- [2]2. Fallenstein, B., Kumar, R.: Proof-producing reflection for hol. In: International Conference on Interactive Theorem Proving. pp. 170-186. Springer (2015)
- [4]4. Myhill, J.: The abstract theory of self-reproduction. Views on general systems theory pp. 106-118 (1964)
- [6]6. Schmidhuber, J.: Godel machines: Self-referential universal problem solvers making provably optimal self-improvements. arXiv preprint cs.LO/0309048 (2003) · arXiv
- [7]7. Steunebrink, B.R., Schmidhuber, J.: Towards an actual g¨ odel machine implementation: A lesson in self-reflective systems. In: Theoretical Foundations of Artificial General Intelligence, pp. 173-195. Springer (2012)
Cited by
Sorted by citations
Gödel Agent: A Self-Referential Agent Framework for Recursively Self-Improvement
Yin, X., Wang, X., Pan, L., Lin, L., Wan, X., & Wang, W. Y. (2025) · Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2025.acl-long.1354 · Cited by 5 · see citing works
Self-citationGödel Agent: A Self-Referential Agent Framework for Recursive Self-Improvement
Yin, X., Wang, X., Pan, L., Lin, L., Wan, X., & Wang, W. Y. (2024) · arXiv · doi:10.48550/arxiv.2410.04444 · Cited by 2 · see citing works
“G¨odel Agent can theoretically make increasingly better modifications over time through recursively self-update (Wang, 2018).”
Self-citation
- Authors
- Wang, W.
- Corresponding author
- Wang, Wenyi
- ORCID
- Wang, Wenyi
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2018
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1805.06610
- OpenAlex
- W2803264000
- Cited by
- 0
- References
- 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
- Keywords
- recursive self-improvement, self-improving systems, formal definitions, computability, runtime complexity, logarithmic time complexity, search space
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
