Where Does Computation End? · Shaurya
Where Does Computation End?
August 18, 2026<br>computation, computability, hypercomputation, physics, philosophy
I started with a fairly specific question: Is the Gödel Machine actually used today? Jürgen Schmidhuber, "Gödel Machines". I expected the answer to lead somewhere inside AI. Instead, it led me into a much stranger question:
What does it actually mean for something to be computable?
And eventually, an even stranger one:
Is the limit of computation a fundamental property of reality, or is it a boundary created by the way we choose to model reality?
This is my attempt to follow that rabbit hole.
1. The Gödel Machine has a strange problem
A Gödel Machine is, roughly speaking, a hypothetical self-improving AI. It runs its current program, searches for a mathematical proof that changing its own program would increase its expected utility, and only then allows itself to rewrite its code.
That sounds reasonable until you ask a simple question: What if the modification is genuinely better, but the machine can't prove that it is? Imagine a chess-playing Gödel Machine. Its current algorithm is mediocre. It discovers a new algorithm that would play substantially better chess. But before replacing itself, it needs to prove that the new algorithm will produce greater utility than the old one.
That proof might require reasoning about every possible future game. For arbitrary programs, questions about future behavior can run directly into undecidability. While Gödel Machines did not manifest into a real system, the idea behind them still lives on in different forms like self-modifying / self-improving agents, meta-learning, AI systems that optimize their own reasoning/search, program synthesis and automated theorem proving, AI agents that evaluate and improve their own generated code, and recursive/iterative AI improvement*.
*these generally use empirical evaluation, gradient optimization, search, or heuristics, rather than the Gödel Machine's extremely strict “prove the modification is better, then execute it” mechanism
And that led me to the Halting Problem.
2. The Halting Problem is not about waiting long enough
At first, the Halting Problem sounded almost trivial. Surely, if I inspect a program carefully enough, I should eventually be able to determine whether it stops. And for many individual programs, I can.
The actual claim is much stronger:
Can we create one algorithm that takes any program and any input and always determines whether that program will eventually halt?
Suppose we had:
def halts(program, input):<br># returns True if program eventually stops
Now construct a program that deliberately does the opposite of whatever halts predicts:
def evil(program):<br>if halts(program, program):<br>while True:<br>pass<br>else:<br>return
Now ask:
halts(evil, evil)
If it says True, evil loops forever. If it says False, evil immediately terminates. Either way, the prediction is wrong.
The problem isn't that computers are too slow. The problem is that no universal algorithm of this form can exist within ordinary computation . That distinction is important. We can solve many individual halting questions. What we cannot have is a universal procedure that solves all of them.
In the 1930s, several people formalized “mechanical computation” in very different ways:
Turing machines — Turing
Lambda calculus — Church
Recursive functions — Kleene
Post machines — Post
They weren't simply copies of each other. They started from different mathematical ideas. Yet they all ended up characterizing essentially the same class of computable functions.
That was one of the major reasons the Church–Turing thesis became compelling: Maybe the Turing boundary isn't an arbitrary choice of one mathematical model. Maybe it is capturing something fundamental about what an algorithmic process is.
3. So what exactly is computation?
This question bothered me more than the Halting Problem itself. We casually say:
"The computer computed it."
But what is computation? At the simplest level, it is the systematic transformation of information according to rules. Turing's great contribution was to formalize what we mean by a mechanical procedure.
A Turing machine is absurdly simple:
a tape
symbols
a read/write head
a finite set of rules
a current state
And yet this tiny abstraction can represent general computation. What made Turing's model especially interesting was that other researchers independently developed different formalisms --- lambda calculus, recursive functions, Post systems --- and they ended up describing essentially the same class of computable functions.
This convergence gave us the Church--Turing thesis:
Anything that can be computed by a reasonable mechanical procedure can be computed by a Turing machine.
But notice the wording. It is a thesis , not a mathematical theorem. "Reasonable mechanical procedure" is not itself a mathematical definition. And this opens an...