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.