Abstract
We present the first class of mathematically rigorous, general, fully
self-referential, self-improving, optimally efficient problem solvers. Inspired
by Kurt Goedel'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 O()-notation, provided the utility of such speed-ups is provable
at all.
Users
Please
log in to take part in the discussion (add own reviews or comments).