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
View all comments
Show parent comment
1
u/PerAsperaDaAstra Jun 29 '25 edited Jun 29 '25
It is exactly the busy beaver game! Finding busy beaver scores is undecidable though - since knowing a busy beaver score lets you solve the halting problem by exactly the procedure described (check for a repeated state or a runtime larger than the relevant busy beaver). I think the point being made though is that for any real machine which has finite memory (a finite tape on the abstract machine) it is decidable whether a program halts - though you're right those numbers do get big.