0
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 2
    $\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