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 uses axioms to systematically search for proofs that a specific re-write is useful - it will result in greater utility for the AI by more efficiently maximizing its utility function - and that no other re-write can be proved to be more useful in a reasonable amount of time. Then, the Gödel Machine will switch its own code by the re-write. The axioms also include a detailed formal description of the machine's software and hardware, including both the components interacting with the environment and those dealing with the formal proofs, and a possibly partial description of the environment.
According to Schmidhuber this approach is globally optimal and it will not get stucked 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 founded.
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 Bayesian: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 prove that another algorithm will be more optimal.