I am studying algorithms and I came across this exercise:
'Prove that there is no program/algorithm that determines if a program P uses an uninitialized variable on a given input x.'
Here is the proof I came up with:
Let's assume that there is an algorithm Det to determine if a program P uses an uninitialized variable on a given input x.
Let the program be
P(x) if Det(P,x) is true do nothing else variable i print i
Here we see a contradiction. If Det(P,x) is false then we have used an uninitialized variable. We have not used uninitialized variable elsewhere so whenever it returns true, its wrong.
I am not sure if I am thinking in the right way.
I think you almost have it, but you have to say a bit more to truly show the contradiction.
Your program is perfect, i.e. 'P(x): if Det(P,x) is true do nothing else variable i print i'. You've also shown the case where Det(P,x) evaluates to false, but you forgot to mention what happens if Det(P,x) evaluates to true (this case is needed for completeness). For example:
Assume Det(P,x) is true. Then, Det has determined P(x) uses an uninitialized variable with input x. But this is impossible, as P states that if Det(P,x) is true, then we do not use an uninitialized variable.
Now assume Det(P,x) is false. Then, Det has determined P(x) doesn't use an uninitialized variable. But this is impossible, as P states that if Det(P,x) is true, then we use uninitialized variable i.
Thus, evaluating Det(P,x) always results in a contradiction, meaning that it cannot exist.
EDIT: This proof is NOT correct! Observe that Det(P,x) can just inspect P, and if Det(P,x) sees a call to itself, then Det(P,x) chooses to use an uninitialized variable and returns true. Currently trying to find a correct solution (see comments).