TY - JOUR

T1 - Gödel Machines: Fully Self-referential Optimal Universal Self-improvers

AU - Schmidhuber, Jürgen

N1 - Generated from Scopus record by KAUST IRTS on 2022-09-14

PY - 2007/12/1

Y1 - 2007/12/1

N2 - We present the first class of mathematically rigorous, general, fully self-referential, self-improving, optimally efficient problem solvers. Inspired by Kurt Gödel'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.

AB - We present the first class of mathematically rigorous, general, fully self-referential, self-improving, optimally efficient problem solvers. Inspired by Kurt Gödel'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.

UR - http://link.springer.com/10.1007/978-3-540-68677-4_7

UR - http://www.scopus.com/inward/record.url?scp=84880251870&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-68677-4_7

DO - 10.1007/978-3-540-68677-4_7

M3 - Article

SN - 1611-2482

VL - 8

SP - 199

EP - 226

JO - Cognitive Technologies

JF - Cognitive Technologies

ER -