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.


marked as duplicate by David Richerby, Kyle Jones, Yuval Filmus, Ran G., Luke Mathieson Apr 18 '15 at 2:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from stackoverflow.com Apr 17 '15 at 16:56

This question came from our site for professional and enthusiast programmers.

  • 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