ID #1023

How can I query/predict the program behaviors? e.g., if a variable x always hold the same value?

According to Rice's Theorem, it is easy to see that nontrivial properties about the programs are always undecidable. The intuition is that if a nontrivial property can be decided, then we can resolve the halting problem.

Let's examplify the point.  Assume the existence of a decision procedure that decides if x in a program has a constant value. Then this procedure can be used to also decide the halting problem by using as input the program:
x = 1; if (TM(j)) x = 2;
Here x has a constant value if and only if the j’th Turing machine halts on empty input!

Tags: theory

Related entries:

You can comment this FAQ