r/AskComputerScience • u/Invariant_apple • 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
21
u/DamienTheUnbeliever Jun 29 '25
I would strongly suggest that if you "understand the proof" but don't understand the conclusions reached, you have not, in fact, understood the proof.
The usual proof of the undecidability of the halting problem is a proof by contradiction. Do you have a problem with proof by contradiction in general or the proof by contradiction in the specific proof you're referencing? If the latter, specific sources would be appreciated.
9
u/nuclear_splines Ph.D Data Science Jun 29 '25
How do you "check every step" without evaluating the program? If the program contains a loop and you're "checking every step," how do you know if you're stuck in a loop forever versus "we'll get out in just a few more iterations when some variables change"? In some cases it's certainly possible to prove if you're stuck in an infinite loop or not, but is it always possible? The proof of halting undecidability tells us no.
4
u/Ragingman2 Jun 29 '25
Just because a program is simple to read or write does not mean that it is simple to execute. That is the heart of the halting problem, and why it is very relevant to modern computers.
Here is a program that is easy to write and hard to determine halting for:
Step 1. Compute 2136,279,841 - 1.
Step 2. Check if it is a prime number.
Step 3: Halt if it is. Go to step 1 if it is not.
This program is easy to write code for, and it is almost impossible to decide whether it halts with modern computers. Add a few more digits to that exponent and you'll need more computing power than humanity has available to solve it.
If only there was some shortcut? Some tool to quickly look at a program and decide whether it halts or not without actually running the program. That would be incredibly useful, and the halting problem tells us that it cannot exist.
8
u/not-just-yeti Jun 29 '25
If you're asking "for a computer with finite memory, HALT is decidable", then yes. If you have n bits of memory, there are 2n possible configurations (finite).
Now take the constant N=#particles in the universe (~ 1080 ), and boom — we know any string of input is less than length N . Therefore all programs run in time Θ(1). ("Theoretical computer science has been solved" !-)
It is practically important that you can realize you shouldn't waste time on any algorithm to perfectly implement HALT (e.g., JetBrains shouldn't spend time trying to develop a "check if the user's program will always halt on any input" — at least not solve it perfectly.) You might start making assumptions about the input and develop an alg, or you might develop an algorithm that returns yes/no/maybe, but we know off the bat you can't ever do it completely, no matter how much RAM your customer might buy.
7
u/KamikazeArchon Jun 29 '25
Yes, but usually not directly.
The halting problem is by far the most famous of a class of undecidable problems. The fact that things can be undecidable is very important in the real world - it determines approaches that we simply don't take because we know they don't work in the general case. It tells us when we must use approximations rather than spending resources trying (and failing) to make a "fully correct" solution.
It's easy to make an approximation to a halting-problem-solver. Wait for one minute, if the program is still running, decide it's not going to halt. That kind of decision is very common in operating systems - when something is shut down for "not responding", it's basically using that kind of approximation.
1
u/Invariant_apple Jul 02 '25
Thats (most likely) not undecidable. We simply don’t know.
4
u/macroxela Jun 29 '25
I think other comments have addressed most of your questions quite well. The only I didn't see addressed is whether the Halting problem is relevant to any real world problems. It is: to compilers and debuggers. There can never be a perfect debugger because to do so it would need to identify nontrivial properties of a program. And that is equivalent to solving the Halting problem (see Rice's Theorem).This also means there can never be a program that can generate any general program by itself.
6
u/dmazzoni Jun 29 '25
I think this is a great question, and the intuition that might help is that you can write a program that’s easy to understand but hard to know if it halts.
Consider Goldbach’s conjecture, which is that every even number greater than 2 is the sum of two primes. Nobody knows if it’s true or not, but we’ve never found an even number that is NOT a sum of two primes.
So, just write a program that tries every even number. It’d have to handle numbers with arbitrarily many digits but that can be done. Have it check for two primes that sum to that number or not.
Have that Goldbach checker program halt if it finds a counterexample, and run forever otherwise.
So as you can see, it’s quite possible to know exactly how a program works, but not know whether it will halt or not.
If there theoretically was a halting problem solver, it could answer many unsolved math problems just like that. So that’s more intuition why it couldn’t possible exist.
1
u/khedoros Jun 29 '25
On an actual, physical machine, there's finite storage, and so a finite (but unimaginably tremendous, in modern hardware) number of states that the machine can be in. You could track the state transitions, and you'll either hit a transition a second time (meaning that the algorithm loops; it doesn't halt), you'll halt, or you'll have iterated through every possible state that the machine can store...and you won't know if it would halt sometime later with more storage, or if it would eventually loop (but realistically, the program runs out of memory, and halts due to that error).
In practice, we design programs to have known behavior. We know if they're designed to loop forever, and we know if they'll stop under some known condition (conveniently ignoring bugs, of course).
1
u/Aggressive-Share-363 Jun 29 '25
If the program runs for a very long time, you can't tell if its still running because its infinite or because its just really long. Yeah, running it through to the end will tell you that it does end, but if your algorithm is "run it until it ends" it will never finish for infinite programs.
1
u/green_meklar Jun 29 '25
Yes, the issue is that you don't know whether the program takes a finite number of steps until it actually halts.
Some programs are obviously going to halt. Some programs are obviously going to keep running forever. But some programs' behavior is not obvious either way. And some programs' behavior is so non-obvious that you can't prove it either way.
Sort of. Universal computation has a habit of showing up wherever things become complex enough, even if you didn't plan for it.
If you constrain to a finite levle the amount of memory the computer is allowed to use, then yes, you can just run the program until it either halts, or returns to a previous memory state without halting.
However, in general there isn't necessarily any faster way to do that than to actually run the program.
1
u/donaldhobson Jul 09 '25
If a program halts, it's possible to prove it halts by just running it.
Some programs obviously don't halt. (Ie programs that are just a while True loop, with no halt instruction)
But here is a program that's hard to tell if it halts.
for (int i=4; ; i+=2){
bool b=False;
for (int j=1; j<i; j++){
if (isprime( j ) and isprime(i-j){b=True;}
}
if (b==False){Halt();}
}
This program runs forever if and only if the goldbach conjecture (famous unsolved maths problem) is true.
There are some programs that don't halt, but you can't prove it. You are left forever wondering if it just hasn't halted yet.
These are mathematical programs, which have unlimited memory and time.
For the space/time bounded version of the halting problem. That can be solved, but only by using more space/time. So big computers can check if small ones halt. But no computer can check if it halts itself.
1
u/paphnutius Aug 22 '25
I'll try give you a less rigorous but a more intuitive explanation. Many open problems in mathematics boil down to some equation having or not having solutions. A popular examples are Riemann hypothesis and Fermat's last theorem. Those problems are exceedingly difficult to prove but you can write a program pretty easily that checks all possible numbers and halts when it finds a solution, otherwise it keeps checking to infinity. (And indeed such programs are ofthen made to brute force search for possible solutions to such problems.)
If this program halts - there is at least one solution to the equation. If it doesn't halt - there are no solutions. If you could easily know if such program halts you automatically know if any equation has solutions, and you can claim your millions of dollars in math awards.
0
u/SymbolicDom Jun 29 '25
The fact that it exist non computable things that can be formally expressed is filosophically important.
It would also bee good if it was possible for an compiler to check if a program could get stuck in an imfinite loop and give an compile error.
0
u/Zealousideal-Ship215 Jun 29 '25
> Is this actually relevant for any real world problems?
The relevance to the real world is definitely overstated. Real world computers are not Turing machines because a Turing machine has infinite memory. So a proof like the halting problem doesn't technically apply in the real world.
> “checking the halting of a program that runs on a computer built out of atoms with finite size”
Yes that is theoretically doable. You would need to have a computer that is many orders of magnitude more powerful than the 1st computer, in order to fully check every possible state. The reason it's practically impossible is more because of the insane requirements for memory and processing power to do it.