I am trying to understand Turing's halting problem proof by applying the same paradox to a similar problem where, instead of determining if a given code will halt, you instead determine if it will return True or False (assuming it will always return eventually). Obviously such a machine can exist, as it is simply a standard compiler. However, when run through the paradox:
We assume h is a function that determines if the return is True or False
We construct a machine P around h in the following way:
def P(i):
return not h(i, i)
P(P)
As we can see, if P returns True then P returns False, and vice versa. Thus compilers cannot exist, as a compiler is an example of h. Can someone please help me find the error in reasoning?
The issue is when you write
You haven't gotten a contradiction yet! There are three possible behaviors of $P$: return false, return true, or don't return anything. All you've proved so far is that the first two can't occur. But nothing in your assumptions about $h$ prevents the third. This is different from the case of the halting problem, where one of the hypotheses is exactly that the halting-ness-checker halts on all inputs.