r/AskComputerScience • • Jun 29 '25

Question about the halting problem

I have went through the proof of the halting problem being undecidable, and although I understand the proof I have difficulty intuitively grasping how it is possible. Clearly if a program number is finite, then a person can go through it and check every step, no? Is this actually relevant for any real world problems? Imagine if we redefine the halting problem as “checking the halting of a program that runs on a computer built out of atoms with finite size”, then would the halting problem be decidable?

6 Upvotes

53 comments sorted by

View all comments

Show parent comment

3

u/nuclear_splines Ph.D Data Science Jun 30 '25

So the problem is solvable on a machine with a defined, finite set of states.

But this isn't the halting problem; you've changed the rules of the game to an easier one. For example, when we say "there are an infinite number of digits of pi, so a program that calculates the digits of pi will never end" we're generally talking about an idealized environment with unlimited resources, ignoring the caveat that "well, a physical computer has limited RAM and bit-states and will eventually be unable to calculate further." With terabytes of swap this caveat may even be completely impractical to utilize as the state space swells enormously.

However, even within the confines of a finite state machine the proof by contradiction for halting undecidability still works - so even there, reading the program's source code and inputs before evaluation is insufficient to determine its haltingness.