A Gödel machine is an approach to Artificial General Intelligence that uses a recursive self-improvement architecture proposed by Jürgen Schmidhuber. It was inspired by the mathematical theories of Kurt Gödel, where one could always find a mathematical truth or axiom that if attached to a formal system would make it stronger. A Gödel Machine is a universal problem solver that will make provably optimal self-improvements – self-improvements which can be proved to better maximize its utility.
Schmidhuber’s design consists of a solver, which attempts to solve the goals set for the machine, and a searcher, which has access to a set of axioms which completely describe the machine. One example design1 contains:
The searcher may completely rewrite any part of the machine, provided that it can produce a formal proof showing that such a rewrite will further the system’s goals, and that no other re-write can be proved to be more useful in a reasonable amount of time. According to Schmidhuber, this approach is globally optimal and it will not get stuck at local optimals. This is because the machine has to prove that it is not more useful to continue the proof search for alternative self-rewrites that could be more useful than the one just found.
The Gödel machine is often compared with Marcus Hutter's AIXI, another formal specification for an AGI. AIXI is constructed in a way its average utility converges – also through self-improvements - asymptotically to the utility of an ideal rational agent. However, different from a Gödel Machine, it usually assumes unlimited computing resources and it can never completely re-write its own code – its search code for optimizations is unmodifiable. Schmidhuber points out that the Gödel machine could start out by implementing AIXI as its initial sub-program, and self-modify after it finds a proof that another algorithm will be more optimal.