Goedel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements

By J. Urgen Schmidhuber. 2003

92 citations recorded by the source corpus.

We present the first class of mathematically rigorous, general, fully self-referential, self-improving, optimally efficient problem solvers. Inspired by Kurt Goedel's celebrated self-referential formulas (1931), such a problem solver rewrites any part of its own code as soon as it has found a proof that the rewrite is useful, where the problem-dependent utility function and the hardware and the entire initial code are described by axioms encoded in an initial proof searcher which is also part of the initial code. The searcher systematically and efficiently tests computable proof techniques (programs whose outputs are proofs) until it finds a provably useful, computable self-rewrite. We show that such a self-rewrite is globally optimal - no local maxima! - since the code first had to prove that it is not useful to continue the proof search for alternative self-rewrites. Unlike previous non-self-referential methods based on hardwired proof searchers, ours not only boasts an optimal order of complexity but can optimally reduce any slowdowns hidden by the O()-notation, provided the utility of such speed-ups is provable at all.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning, Meta & Continual Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Reinforcement Learning

In Meta & Continual Learning

Citations in the corpus

Scalable agent alignment via reward modeling: a research direction (2018, background): “Agents that plan this way have no incentive to change their reward functions (Schmidhuber, 2007; Omohundro, 2008), nor manipulate the register holding the reward signal (Everitt, 2018, Sec.”
The Nature of Self-Improving Artificial Intelligence (2008, background): “Fully deliberative self-improving systems do not yet exist but several research groups and companies are actively investigating them [11, 12, 13, 14, 15].”
Modeling AGI Safety Frameworks with Causal Influence Diagrams (2019, methodology): “An elegant solution to this problem is to use model-based agents that simulate the state sequence likely to result from different policies, and evaluate those state sequences according to the current or initial reward function [Everitt, 2018; Orseau and Ring, 2011; Hibbard, 2012; Schmidhuber, 2007; ”
Optimal Artiﬁcial Curiosity, Creativity, Music, and the Fine Arts (2005, background): “Note that unlike in most previous work by others [11, 50], but like in much of the author’s own previous work [44, 34], there is just one life, no need for predefined repeatable trials, no restriction to Markovian interfaces between sensors and environment [25], and the utility function implicitly t”
The Singularity: a Philosophical Analysis (2010, background): “(A formal analysis that makes 10The “Gödel machines” of Schmidhuber (2003) provide a theoretical example of self-improving systems at a level below AI, though they have not yet been implemented and there are large practical obstacles to using them as a path to AI.”
Reward Tampering Problems and Solutions in Reinforcement Learning: A Causal Influence Diagram Perspective (2019, background): “Schmidhuber (2007) may have been the first to encounter the reward function tampering problem, while designing so-called Gödel-machine agents that are able to change any part of their own source code, including their own reward function.”
Artificial Intelligence as a Positive and Negative Factor in Global Risk (2006, background): “(Though see Schmidhuber 2003 for a related notion.) But one ought to think about a challenge, and study it in the best available technical detail, before declaring it impossible - especially if great stakes depend upon the answer.”
Measuring Intelligence through Games (2011, methodology): “1 Universal Intelligence Building upon Solomonoff’s theory of universal induction Solomonoff (1964), and extending it to handle agents that act in their environment (in contrast to just passively pondering upon observations), Hutter (2005) recently developed a formal framework for universal artifici”
Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution (2023, background): “Kirsch & Schmidhuber (2022) propose a self-referential meta-learning approach, combining self-referential weight matrices with ideas from Gödel Machines (Schmidhuber, 2003), i.e., to allocate more computational resources to better performing solutions.”