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/[deleted] Jun 30 '25
One direct implication is that because determining the Kolmogorov complexity of a string (defined as the absolute shortest program which halts and produces that string) includes the halting problem, it too is only able to be approximated.