TR IDSIA-19-03, Version 3;
arXiv:cs.LO/0309048 v3

PS -
PDF -
GM Home Page -
Summary

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

IDSIA, Galleria 2, 6928 Manno (Lugano), Switzerland

**11 December 2003**

An old dream of computer scientists is to build an optimally efficient
universal problem solver. We show how to solve arbitrary computational
problems in an optimal fashion inspired by Kurt Gödel's celebrated
self-referential formulas (1931). Our Gödel machine's initial software includes an
axiomatic description of: the Gödel machine's hardware, the problem-specific utility
function (such as the expected future reward of a robot), known aspects
of the environment, costs of actions and computations, and the initial
software itself (this is possible without introducing circularity).
It also includes a typically sub-optimal initial problem-solving policy
and an *asymptotically* optimal proof searcher searching the space of
computable proof techniques--that is, programs whose outputs are proofs.
Unlike previous approaches, the self-referential Gödel machine will rewrite *any* part of its software, including axioms and proof searcher, as soon
as it has found a proof that this will improve its future performance,
given its typically limited computational resources. We show that
self-rewrites are globally optimal--no local minima!--since provably
none of all the alternative rewrites and proofs (those that could be
found by continuing the proof search) are worth waiting for.

**Note:** some of the formulae in the original pdf/ps version
failed to come out properly in the present html version.

- Introduction and Overview
- Previous Work: Best General Methods Need Proof Searchers!
- Basic Principles of Gödel Machines
- Fast Initial Proof Searcher
- Outline

- Formal Details of a Particular Gödel Machine
- Overview of Hardware and Initial Software / Proof Searcher
- How Online Proof Techniques Connect Syntax and Semantics
- Bias-Optimal Proof Search (BIOPS)

- Discussion
- Possible Types of Gödel Machine Self-Improvements
- Example Applications
- Probabilistic Gödel Machine Hardware
- Limitations of the Gödel machine
- More Relations to Previous Work on Self-Improving Machines
- Practical Issues
- Are Humans Probabilistic Gödel Machines?

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

Back to Goedel machine home page