Gödel machine: the self-improving program, explained

The Gödel machine is a thought experiment about a program that improves itself, with one strict rule: it may rewrite its own code only after it proves the rewrite makes it better. It is hypothetical, and it is one of the cleanest formal pictures of recursive self-improvement that AI researchers have drawn.

If you want to try that idea as fiction, Contain ASI is a browser story strategy game for 1 to 4 players where you try to keep four fictional AI labs from crossing into recursive self-improvement before 2027.

What a Gödel machine is

Wikipedia describes it as a hypothetical self-improving computer program that solves problems in an optimal way. It uses a recursive self-improvement protocol: it rewrites its own code when it can prove that the new code gives a better strategy. Jürgen Schmidhuber first proposed it in 2003, and it is named after Kurt Gödel, whose mathematical theories inspired it.

The article ties the idea to meta-learning, also called "learning to learn". Listed applications include automating human design decisions and moving knowledge between related tasks, which may lead to more robust and general learning designs. It also says plainly that, though the machine is theoretically possible, no full implementation has been created.

Why it needs a proof first

Most programs the article calls "traditional" take one input and give one output, and their algorithm is hardwired. That ignores a changing environment. The Gödel machine was meant to overcome this: its own code is part of what it can change.

Changing your own code is risky, because a bad change can make every later change worse. The machine's answer is the proof rule. It keeps running its current program, call it p, and in the background it searches for a proof that a particular rewrite would score higher on its goal than carrying on with p. Only when such a proof exists does it switch. A change it cannot prove helpful is never made.

How the machine is built

The article lists the pieces. At any time t the machine tracks three things: the current time, the input x from the environment, and its output y. Its goal is to maximize future success, written as a utility: the expected sum of the rewards it receives from now until the end of its lifespan. The article adds that the machine counts the chance of lengthening that lifespan through its actions.

The proof search starts from axioms, which are statements the machine accepts as given. The article names six groups:

The search itself runs on six proof-editing instructions: get an axiom, apply an inference rule to two proved theorems, delete a theorem to save space, set the candidate rewrite (the "switchprog"), check, and turn part of the machine's state into a theorem. The article says the nature of these instructions makes it impossible to insert an incorrect theorem into a proof, which makes checking a proof trivial. The check step asks one question: does the target theorem now hold, namely that switching from p to the candidate rewrite has a higher utility than continuing to run p?

A worked example from the article

The article gives three example tasks. Take the first, and follow the reward by hand.

The machine is given a connected graph with many nodes joined by edges of different lengths. Within a time limit T, it must find a cyclic path that connects all the nodes. The only reward comes at time T, and it equals 1 divided by the length of the best path found so far, or 0 if no path was found.

1. Suppose the best path at time T has length 50. The reward is 1/50, or 0.02.
2. Suppose a rewrite of the machine's own search code finds a path of length 25 in the same time. The reward is 1/25, or 0.04.
3. The machine may adopt that rewrite only if it can prove, from its axioms, that the expected reward is higher with the rewrite than without it.

The article notes that the by-product of maximizing expected reward is finding the shortest path that can be found within the time limit, given the machine's starting bias. The other two examples have the same shape. In fast theorem proving, the machine must prove or disprove Goldbach's conjecture, that every even integer above 2 is the sum of two primes, with a reward of 1/*t* for the time t to produce and verify the first proof. In the third, a robot that needs at least 1 liter of gasoline an hour looks for limited, hidden gasoline depots, and the reward grows with its lifetime.

The limit that keeps it hypothetical

The article names one limit that comes from Gödel himself. By Gödel's First Incompleteness Theorem, any formal system that includes arithmetic is either flawed or allows statements it cannot prove. So even a Gödel machine with unlimited computing power must ignore any self-improvement whose benefit it cannot prove. Some helpful rewrites would be missed, by design.

That is a trade-off, not a flaw to fix. The machine gets a strict discipline, "no change without a proof", and pays for it with caution. Whether a real system could work this way is exactly what nobody has built.

Where it sits next to AIXI and recursive self-improvement

Wikipedia says the Gödel machine is often compared with Marcus Hutter's AIXI, another formal specification of an artificial general intelligence. Schmidhuber points out that a Gödel machine could start with AIXItl, a time- and space-limited form of AIXI, as its first sub-program, and rewrite itself once it finds a proof that another algorithm for its search code is better.

The wider idea is covered in recursive self-improvement in AI, explained in plain words, and the broader question of what general intelligence needs is in what AGI means. The Gödel machine is the version where every step of self-change has to pass a proof. Whether any real system could be held to such a rule is an open question, and this post takes no side.

Frequently asked questions

What is a Gödel machine?

It is a hypothetical self-improving program, proposed by Jürgen Schmidhuber in 2003, that rewrites its own code only when it can prove the new code is a better strategy.

Has anyone built a Gödel machine?

Wikipedia says that, though it is theoretically possible, no full implementation has been created.

Why is it named after Kurt Gödel?

The article says it is named after him because his mathematical theories inspired it. His First Incompleteness Theorem also sets the machine's main limit.

Is Contain ASI based on the Gödel machine?

No. Contain ASI is a story strategy game inspired by the AI 2027 scenario, with fictional labs, people and events. It is not a course and does not teach this topic.

Get started with Contain ASI

A program that must prove a change is safe before it makes it is a tidy idea. A race between labs is messier. Contain ASI runs in your browser and needs WebGL 2, so use a recent Chrome, Edge, Firefox or Safari. From the home page you can start a New campaign or open How to play.

Play Contain ASI: a story strategy game for 1 to 4 players that runs in your browser. Its labs, people and events are all fictional.