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?
$\begingroup$
$\endgroup$
6
2 Answers
$\begingroup$
$\endgroup$
6
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$ Commented Oct 23, 2014 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$– DCTLibCommented Oct 23, 2014 at 15:00
-
$\begingroup$ I understand what you mean by arbitrary memory and input size. $\endgroup$ Commented Oct 23, 2014 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
Pand its inputxas input and decide whetherPhalts onx. $\endgroup$ Commented Oct 23, 2014 at 15:08 -
2$\begingroup$ @JuzerAli This last comment of yours is a correct and true statement. $\endgroup$ Commented Oct 23, 2014 at 15:52
$\begingroup$
$\endgroup$
0
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
whileloop, then it halts.If every basic block in the program contains a
returnstatement, 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.
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 fromraw_input()is a valid Python program that terminates. $\endgroup$read_inputdoes more carefully (does it read a fixed amount of input, or read until end of file?). $\endgroup$