email@example.com - 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.