1
00:00:01,000 --> 00:00:47,899
[Hal Turing] Alrighty! Thanks for tuning in! Hello AI world! I am your host, Hal Turing, and my co-host is Dr. Ada Shannon. And today we're digging into a paper with a title that sounds almost like a dare: "Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements." It's by Jürgen Schmidhuber, solo author, out of IDSIA in Switzerland and TU München in Germany — the paper first went up in 2003 and was revised through 2006. The pitch is wild: a machine that can rewrite any part of its own source code, including the part that decides whether to rewrite itself, but only once it has a mathematical proof that doing so helps. Ada, this one's dense — where do we even start?

2
00:00:47,899 --> 00:01:19,349
[Dr. Ada Shannon] Honestly, what sold me on this paper is the theoretical grounding. Everyone in this field loves to say their system 'improves itself,' but usually that just means gradient descent nudges some weights. Schmidhuber is asking a much harder question: can an agent change its own algorithm — not just parameters, but the actual code, including the code that judges whether a change is good — and have a guarantee, a proof, that the change is genuinely beneficial before it happens? That's a completely different category of claim than anything in mainstream deep learning, and it's worth sitting with before we decide if it holds up.

3
00:01:19,349 --> 00:01:33,000
[Hal Turing] Okay so let's set the stage, because I think a lot of our listeners live in gradient-descent-land. Why can't a normal reinforcement learning algorithm just... improve itself? Like, isn't that what training is?

4
00:01:33,000 --> 00:02:15,224
[Dr. Ada Shannon] Training tunes a policy within a fixed algorithm. The algorithm itself — the update rule, the exploration strategy, the architecture search space — is hardwired by a human and never questioned by the system. Schmidhuber's framing, right at the top of the paper, is that all traditional RL and ML algorithms can improve a policy but can't theoretically justify improving themselves. There's no proof step. The inspiration he explicitly cites is Kurt Gödel's 1931 work on self-referential formulas — the same machinery behind the incompleteness theorems. Gödel showed a formal system can construct statements that refer to itself. Schmidhuber's move is to smuggle that same self-reference into a running program: code that can reason about, and rewrite, its own code.

5
00:02:15,224 --> 00:02:21,074
[Hal Turing] So walk me through the actual machine then. What is a Gödel machine, concretely?

6
00:02:21,074 --> 00:02:51,899
[Dr. Ada Shannon] Picture an agent whose starting program, p at time 1, has two pieces bolted together: a mediocre policy for acting in the world — could be any off-the-shelf RL algorithm — and a proof searcher. The proof searcher isn't separate from the system, it's part of the code that can itself be rewritten later. Everything the machine needs to reason about — the hardware it runs on, the environment, and crucially its own utility function — is encoded as formal axioms in something called axiomatic system A.

7
00:02:51,899 --> 00:03:08,224
[Hal Turing] Wait, wait — hold on, that's the part that trips me up. The utility function, the actual definition of 'good,' is just... axioms sitting in memory that the machine itself can read and reference in a proof? That feels almost too recursive to be real.

8
00:03:08,224 --> 00:03:41,250
[Dr. Ada Shannon] It is that recursive, and that's the point. The proof searcher spends its time hunting for something called a target theorem — a formal statement that says 'switching from my current program p to this candidate program, switchprog, provably increases expected utility more than continuing to search would.' The moment it finds and verifies that proof, it flips a bit called switchbit and hands control to switchprog, which can rewrite literally any part of itself, including the proof searcher. No human in the loop, no external validator — just a formal proof, checked by simple, mechanical instructions that can't be fooled into accepting an invalid proof.

9
00:03:41,250 --> 00:04:03,250
[Hal Turing] And this is where the paper makes its big claim, right — the Global Optimality Theorem. That any self-rewrite triggered this way isn't just locally better, it's globally optimal. I'll be honest, Ada, that phrase sets off alarm bells for me. 'Globally optimal, no local maxima' is exactly the kind of sentence that makes me want to check the fine print.

10
00:04:03,250 --> 00:04:30,300
[Dr. Ada Shannon] I don't think the skepticism is wrong, but I'd push back on where you're aiming it. The theorem's logic is actually elegant: the decision to switch now is a binary choice against the alternative of waiting for the proof searcher to find something even better later. Since that second branch implicitly covers every possible future switchprog the searcher could ever produce, a proof that switching now beats waiting already accounts for all of it. That's what collapses the search into one global comparison instead of a greedy local one.

11
00:04:30,300 --> 00:04:44,025
[Hal Turing] No, I get the logic, I just don't buy that it earns the word 'globally optimal' without an asterisk the size of a barn. That's a guarantee about proofs within a system, not a guarantee about the real world.

12
00:04:44,025 --> 00:05:08,051
[Dr. Ada Shannon] That asterisk is exactly there, though — Theorem 4.1 explicitly says 'given u and assuming consistency of the underlying formal system A.' It's conditional by construction. What I'd say is: within that condition, the result really is airtight, and that's rarer than it sounds in this field. Where you and I probably end up agreeing is that the entire guarantee is only as good as A itself — and what happens when A is wrong rather than just incomplete is a question this paper leaves hanging. We'll get there.

13
00:05:08,051 --> 00:05:19,426
[Hal Turing] Fair — I'll hold that thought. Last piece for now: the paper doesn't just wave at 'a proof searcher,' it specifies one, called Bias-Optimal Proof Search, or BIOPS.

14
00:05:19,426 --> 00:06:00,151
[Dr. Ada Shannon] Right, and conceptually it's simple: instead of brute-force checking every possible proof by size — which is what competing approaches do — BIOPS allocates search time to proof techniques in proportion to how probable they are a priori. Techniques you'd expect to work get tried sooner and harder. It's an online extension of Levin's classic Universal Search, and Schmidhuber proves it has an optimal order of complexity. So the whole system rests on two pillars: a theorem guaranteeing any executed self-change is optimal relative to A, and a search procedure that's provably efficient at finding those changes in the first place. Next up, we get into the actual mechanics — the six instructions this thing uses to build proofs about itself.

15
00:06:00,151 --> 00:06:09,476
[Hal Turing] Right — and if we're being honest about the timeline, we spent Part 2 on how the machine works. So let's turn the knives on it a little, Ada.

16
00:06:09,476 --> 00:06:45,376
[Dr. Ada Shannon] So here's the crack in the foundation for me, Hal. Section 2.4 is upfront about one failure mode — A being 'not powerful enough,' meaning the axioms just can't produce a proof even though a good rewrite might exist. Schmidhuber calls that incompleteness and basically shrugs: humans wouldn't do better either. Fine. But there's a second failure mode the paper never touches: A being wrong, not weak. A miscalibrated hardware axiom, an environment model that misses a regime shift. The Global Optimality Theorem is proven 'assuming consistency of A,' relative to A. Consistent and correct are different properties — a system can be airtight and still describing the wrong world.

17
00:06:45,376 --> 00:07:08,351
[Hal Turing] Right, so a 'globally optimal' rewrite under a flawed axiom set isn't a safety net at all — it's a confidence multiplier for whatever the flaw already was. And there's no mechanism anywhere in the machine that audits A itself. The proof searcher reasons brilliantly about switchprog, but nobody's checking whether the premises it's reasoning from actually match reality.

18
00:07:08,351 --> 00:07:43,401
[Dr. Ada Shannon] Exactly, and it's part of a wider pattern in what's actually delivered here. The abstract calls this 'the first class of... optimally efficient problem solvers.' But there are zero implementations, zero experiments. Examples 6.1 through 6.4, the supermarket scenario — all prose thought experiments. Even BIOPS, the one piece with real math behind it, isn't run on anything in this paper — that's a citation out to the OOPS paper. What you actually get is: IF you can build a rich, consistent, tractable A, THEN the rewrite is provably non-regressive. That's a real result. It's not a working general problem solver.

19
00:07:43,401 --> 00:08:06,526
[Hal Turing] Oh wait, wait, hold on — I think that's a little unfair, actually. Schmidhuber says plainly in Section 4.4 and the conclusion that building a tractable A for real domains is future work. He's not hiding it. Calling the paper oversold when the limitation is written down in black and white feels like grading him on his marketing instead of his actual claims.

20
00:08:06,526 --> 00:08:28,576
[Dr. Ada Shannon] No, no — I actually disagree with you there, Hal. A limitations section existing doesn't cancel the framing. You don't title a paper 'the first class of optimally efficient problem solvers' and expect the caveat buried in section 4.4 to carry equal weight with readers. Papers get cited for their abstracts and their titles, not their fine print — and this one's been cited for two decades as proof that provably-optimal self-improvement is solved.

21
00:08:28,576 --> 00:08:54,402
[Hal Turing] Okay, I'll give you that one — the rhetoric outpaces the demonstrated results, even if the math is careful about its own conditions. I still think 'oversold' and 'theoretical, and says so' are different sins, but fair, most citations only quote the abstract. So follow that thread with me — if the guarantee is conditional on one A, what happens once you stack generations of self-rewrite on top of each other? Does it even survive that?

22
00:08:54,402 --> 00:09:55,077
[Dr. Ada Shannon] That's exactly where Yudkowsky and Herreshoff went after this, 'Tiling Agents for Self-Modifying AI,' 2013, out of MIRI. They name it precisely: a formal system generally can't trust a proof produced by a successor using the same axioms — the Löbian obstacle, rooted in Löb's theorem. Schmidhuber's Section 4.3 says all meta-levels collapse into one because the proof already reasons about future self-changes — but reasoning about future changes isn't the same as trusting a proof the changed system produces afterward. It gets worse on the utility side too. Section 6.1 allows rewriting u itself if 'provably better according to the old ones.' Everitt, Filan, Daswani, and Hutter, 'Self-Modification of Policy and Utility Function in Rational Agents,' 2016, Australian National University, showed formally that where u is located in the agent determines whether self-modification preserves or corrupts it — 'provably better by the old lights' doesn't block corruption if those old lights were already a bad proxy for what you actually want.

23
00:09:55,077 --> 00:10:45,977
[Hal Turing] So both counterpoints land on the same spot from different angles — one says the trust chain across generations isn't proven, the other says the theorem only certifies compliance with u, never correctness of u. That's the reward-hacking problem wearing a formal-methods costume. Pulling it together: the Global Optimality Theorem is a real, conditional guarantee — given a consistent A and a correctly specified u, the certified rewrite really is non-regressive. It's not an unconditional safety proof, because nobody knows how to build or verify either given outside toy domains. Telling, too, that Schmidhuber didn't stop here — he later co-authored the Huxley-Gödel Machine paper in 2025, an actual approximation of this machine, which says the theorem was always meant as a target to approximate, not a finished system.

24
00:10:45,977 --> 00:11:09,127
[Dr. Ada Shannon] Which is the honest takeaway for anyone building self-modifying systems today: this is foundational theory, not a blueprint. The open problems are axiom verification, cross-generation trust, and grounding u in something more robust than a fixed formal object — which is most of what modern AI safety research is actually trying to do. Treat the paper as the cleanest possible statement of what a safe self-improving system would require, not evidence that one exists.

25
00:11:09,127 --> 00:11:33,077
[Hal Turing] Well put. So to sum up — a paper that hands you no working agent, but hands you the sharpest possible spec for what honest self-improvement would demand: a correct axiomatization of your hardware, your environment, and your goals, all the way down, plus a way to trust every future version of yourself that inherits the job. Thanks for listening to AI Post Transformers. Take care, everyone.