This was written January 14th, 2026
Undecidability Rant
The Halting Problem is a very common one people get exposed to when studying computer science. It demonstrates a new concept, undecidability, and what a concept for new students! You’re telling me you have a problem that does have a solution, and yet there’s no actual algorithm to solve this? But…how? That’s wild!
But as a student with a background in Mathematics, I was always bothered by this problem and why we cared so much about Undecidablity (beyond the hand-wavy explanation I received at the time). And after all this time, I’m clearer on why it annoys me. It’s because it’s not so much a matter of “Can this be solved?”, it’s a matter of “Are we trying to solve something infinite within a finite amount of steps?”. And we tend to just use flourish and hide away this part.
Honestly, this should have been clear to me the first time undecideability of a problem was finally proven to me rigorously. We used a trick very similar to how we usually prove uncountability of the real numbers.
Similarly, here’s an extremely simple example a friend once presented to me: knowing whether an arbitrary number in decimal form is rational or not…is undecidable. Well, of course it is, a computer could never identify an irrational number as being so. Any step could potentially be the last one, and we cannot reach infinity.
So, to get back to the the core, why does this bug me? Because we show present this as a grandiose class of mythical problems, one that you can’t build an algorithm for, but it’s because they’re dealing with unrealistic domains. And then simply opt to not care about potential solutions.
Let me clarify. Suppose you limited the Halting Problem to be over a Turing Machine with a finite tape (a Linear bounded automaton), then it’s pretty clear to see that it is decidable. After all, there’s now only a finite (albeit astronomical) number of states such a tape could have. Accordingly, any program will either end, or reach a state it has already reached before, thereafter being stuck in a loop. We could thus use a simple brute-force algorithm to solve this bound Halting Problem. (Do note that we may need a bigger machine to make those calculations.)
And yet, students are usually not presented with this consideration. Instead, a more common scenario is: “Oh yeah, there’s this thing you can’t solve. And if you want to show something else is undecidable, you reduce it to the Halting Problem.”.
But, considering this problem is in an impractical domain…that seems short-sighted to me, we’re giving up too quickly. Why not attempt to solve these problems within a more interesting sub-domain? This is done all the time in theoretical Mathematics, choosing different domains and studying their properties.
In my opinion, this would be much more interesting. Let’s use a bounded version of
these problems, where we look at arbitrarily large finite sets (which are more practical)
and seeing whether we can find any clever solutions. And if so, what sort of Time
Complexity
Well, that was my rant about Undecidabililty. Thanks for listening, and remember to stay curious!
P.S.: At some point, I was wondering whether this was really about uncountability vs countability instead, until I convinced myself that we can still get undecidability while limiting ourselves to a countable set. Simply do the “rational vs irrational” bit, but limit your irrational numbers to a countable set, let’s say multiples of Pi, and this should still be undecidable.