Turing's solution to the Entscheidungsproblem [duplicate]
Algorithm to solve Turing's "Halting problem‍​" (6 answers)
Why, really, is the Halting Problem so important? (12 answers)
Based on what I have read so far, to me it sounds like Alan Turing's solution the Entscheidungsproblem means that there is no algorithmic solution to tell whether a given algorithm with input will eventually halt or not. But why is this so crucial in the "computability" world?
It sounds like if I write a program (let's call it P) and have an input, there doesn't exist a separate program that can read in P and the input to tell whether P will halt or not - so what? Can't I just run P to see if it will halt?
I would greatly appreciate it if someone can explain to me what it means to have no algorithm to decide whether a program will halt or not.
jkim796jkim796
$\begingroup$ A problem with that is that you can't tell whether a program is e.g. stuck in an infinite loop, as opposed to just taking very long to run to completion. How do you know when to stop and assume it won't halt? After a few minutes? hours? days? What if the program just takes longer than that? $\endgroup$ – Blacklight Shining Apr 14 '15 at 14:12
$\begingroup$ Like Blacklight says, the problem is, if you let it run for 100 years, there's no way to know if it wouldn't halt after 100 years and 1 millisecond. In practice, you give up much sooner. $\endgroup$ – jmite Apr 17 '15 at 18:57
$\begingroup$ see also cs.stackexchange.com/questions/4856/… and cs.stackexchange.com/questions/20109/… $\endgroup$ – Ran G. Apr 17 '15 at 23:21
Why, really, is the Halting Problem so important?
Algorithm to solve Turing's "Halting problem‍​"
Why is the halting problem unsolvable by a turing machine?
Is the halting problem specific to Turing machines?
Halting problem - one issue that's bothering me
Misunderstanding Turing's Halting-Problem Argument
Explanation of an explanation of Turing's proof to the halting problem?
What is the complement of Halting Problem?