Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code:

x = read_input
print x

Does undecidability mean that there may possibly be an input to this program such that the program may never halt?

  • 1
    $\begingroup$ Well, in that case, presumably the program won't terminate if the input stream never ends. This isn't really within the realms of Turing machine computation, where the input is normally assumed to be finite. $\endgroup$ – David Richerby Oct 23 '14 at 15:05
  • $\begingroup$ I'm guessing what you really wanted is something like x = raw_input() \n eval(x) \n print "input program terminates"? This takes an input program and outputs "input program terminates" if and only if the input read from raw_input() is a valid Python program that terminates. $\endgroup$ – Kevin Oct 23 '14 at 16:02
  • $\begingroup$ @JuzerAli, it would help if you described what read_input does more carefully (does it read a fixed amount of input, or read until end of file?). $\endgroup$ – D.W. Oct 23 '14 at 19:20
  • $\begingroup$ @D.W.I guess it reads till end of file. $\endgroup$ – Juzer Ali Oct 23 '14 at 19:28
  • 1
    $\begingroup$ I don't think this should be closed as a programming/software development question. Although it mentions Python, my impression is that it's not about Python per se, and certainly not about programming, but about the relationship between the halting problem and actual programming languages, with Python used as an example. $\endgroup$ – David Richerby Oct 23 '14 at 20:42

Short answer: No.

Undecidability is a property of problems, not of programs. What is undecidable is however to check if some given program ever halts on any input. This problem has the program as input.

If you fix a program, then it may be decidable to check if the program halts for some input. This problem has the program input as input. In particular, for programs such as yours that always terminate, the termination problem is decidable, meaning there exists an algorithm for it: it just outputs "yes".

Note that the term "undecidability" only has a meaning in environments that allow arbitrary memory size and arbitrary input size. The Python language may fit to this definition, but the interpreter your are using certainly doesn't.

  • 1
    $\begingroup$ So let me put it this way. Python interpreter can be seen as a TM. It accepts python language. My question is what does undecidability mean in context of python. Is following statement true about undecidability: There exists a string which is not valid python language string but the interpreter may never halt to tell us that it isn't. $\endgroup$ – Juzer Ali Oct 23 '14 at 14:57
  • 1
    $\begingroup$ A program is valid python if it is syntactically valid. Syntactic validity of Python programs is decidable and the interpreter certainly uses an algorithm for it that is guaranteed to terminate. $\endgroup$ – DCTLib Oct 23 '14 at 15:00
  • $\begingroup$ I understand what you mean by arbitrary memory and input size. $\endgroup$ – Juzer Ali Oct 23 '14 at 15:00
  • 2
    $\begingroup$ So I guess this statement should be correct. It is impossible to create a program which can accept a valid python program P and its input x as input and decide whether P halts on x. $\endgroup$ – Juzer Ali Oct 23 '14 at 15:08
  • 2
    $\begingroup$ @JuzerAli This last comment of yours is a correct and true statement. $\endgroup$ – Patrick87 Oct 23 '14 at 15:52

Undecidability tells us that, given an arbitrary program and some input, there is no general computational procedure which tells us whether that program halts on that input.

It says nothing about specific computational procedures which may be correct for specific (classes of) programs. That is, we can generate heuristics which correctly answer the question for some programs; the more complicated we're willing to make the heuristics, the more programs may be potentially covered. All that undecidability says is that no finite set of heuristics is going to correctly cover all cases.

To illustrate, we can start developing heuristics to decide whether a program $P$ halts on an input $x$. Let's narrow down our language first: we'll assume a procedural language, with no function calls, and the only control flow constructs are while and if-else. On the right machine, this system is Turing-equivalent.

If the program doesn't contain a while loop, then it halts.

If every basic block in the program contains a return statement, then it halts.

You can take this as far as you want to go, defining a sort of "halting semantics" for your programming language. The semantics will never be correct for all possible programs - if your language/machine is Turing-equivalent - but you can do pretty good. The above (correct) heuristics are enough to definitively answer the example in your question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.