Problem Detail: 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?
Asked By : Juzer Ali
Answered By : DCTLib
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/32239 Ask a Question Download Related Notes/Documents
