TR IDSIA-19-03, Version 4;
arXiv:cs.LO/0309048 v4

PDF -
GM Home Page -
Summary

(based on versions
1.0 (Sept 2003)
& 2.0 (Oct 2003))
& 3.0 (Dec 2003))

**
JÜRGEN SCHMIDHUBER
**

IDSIA, Galleria 2, 6928 Manno-Lugano, Switzerland &

TU Munich, Boltzmannstr. 3, 85748 Garching, München, Germany

**Revised 27 December 2004**

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 -notation, provided the utility
of such speed-ups is provable at all.

- Introduction and Outline
- Overview / Basic Ideas / Limitations
- Set-up and Formal Goal
- Basic Idea of Gödel Machine
- Proof Techniques and an -Optimal Initial Proof Searcher
- Limitations of Gödel Machines

- Essential Details of One Representative Gödel Machine

**Global Optimality Theorem**- Globally Optimal Self-Changes, Given and Encoded in
- Alternative Relaxed Target Theorem
- Global Optimality and Recursive Meta-Levels
- How Difficult is it to Prove Target Theorems?

- Bias-Optimal Proof Search (BIOPS)
- Online Universal Search in Proof Space
- How a Surviving Proof Searcher May Use the Optimal Ordered Problem Solver to Solve Remaining Proof Search Tasks

- Discussion & Previous Work
- Possible Types of Gödel Machine Self-Improvements
- Example Applications
- Probabilistic Gödel Machine Hardware
- Relations to Previous Work
- Are Humans Probabilistic Gödel Machines?
- Gödel Machines and Consciousness
- Frequently Asked Questions

- Conclusion
- Acknowledgments
- Bibliography
- About this document ...