0

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?

Alex Breeze
  • 11
  • 2

1 Answers1

2

The issue is when you write

Thus compilers cannot exist, as a compiler is an example of h.

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.

Noah Schweber
  • 245,398