TR IDSIA-19-03, Version 2; arXiv:cs.LO/0309048 v2

PS - PDF - arXiv

GM Home Page and Summary

(compare previous version 1.0, September 2003)

**Jürgen Schmidhuber
juergen@idsia.ch - http://www.idsia.ch/~ juergen
IDSIA, Galleria 2, 6928 Manno (Lugano), Switzerland **

**28 October 2003**

A Gödel machine is designed to solve arbitrary computational problems,
such as maximizing the expected future reward of a robot in a possibly
stochastic and reactive environment. Its initial software includes an axiomatic
description of (1) the Gödel machine's hardware, (2) known aspects of the
environment, (3) goals and rewards to be achieved, (4) costs of actions
and computations, (5) the initial software itself (no circularity
involved here). It also includes a possibly sub-optimal initial
problem-solving policy and a 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 typically limited computational resources (its optimality notion is
not restricted to the concept of *asymptotic* optimality). Self-rewrites
represent *globally* optimal self-improvements (no local minima!), since
provably none of all the alternative rewrites and proofs (that could be
found in the future by continuing the proof search) is worth waiting for.
To initialize the proof searcher we may use the recent Optimal Ordered
Problem Solver.

- Introduction

- 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