Question about the proof of the undecidability of the Halting Problem

Question

From what I can see, the proof of the undecidability of the Halting Problem relies on a fairly basic self-referential paradox, the simplified version being (from Wikipedia):

def g():
    if halts(g):
         loop_forever()

Obviously, in this case there can not be any output for halts(g) as the output of g itself depends on halts(g). However, I don't really see the point of this proof because you can create this phenomena for literally any arbitrary function. For example, let us a consider a function returns_true that returns true if the given input returns true and false otherwise:

def g():
    return !returns_true(g)

We once again arrive at the same conclusion: returns_true(g) doesn't return true or false. Does that mean that there is no function returns_true that works on all inputs? Technically yes, but obviously that isn't really the point of the question, it works on all non-obviously-malformed inputs. Since the same can be said for the halting problem, what exactly is the point?

Answer 1

You said:

you can create this phenomena for literally any arbitrary function

but the example you provided of returns_true is very far from a typical function, and is rather a higher-order function very similar to the one used in the halting problem, which seems to require running/analysing its input function in its entirety. And given that the attempt to do so might itself run into the halting problem, it seems natural to me that the same proof method applies against returns_true.

In particular, I believe the problem in this case lies in the fact that by the way you defined g, it immediately leads to an infinite mutual recursion between g and returns_true, so it doesn't halt, and will not return any value.

So it appears to me that your statement:

it works on all non-obviously-malformed inputs

translates into something like "it works on all inputs that are guaranteed to halt", but sadly, given the halting problem, we don't actually know which inputs these are (at least on a theoretical Turing Machine with unlimited memory).

Answer 2

Notice, that the code you wrote isn't well defined. That is, the code:

def g():
    if halts(g):
        loop_forever()

Is actually not well defined. The problem here is with the second line, where you referenced $g$ inside itself. Think about it, you need the entire definition of $g$, in order to write the definition of $g$? Not really a great idea.

To fix this, take a look at how actually this self-reference is created:

def g(func_code):
    if halts(func_code(func_code)):
        loop_forever()

And now the definition of $g$ doesn't depend on itself, while we can still create the self-referential problem by asking what will happen when we pass $g$ as an argument to itself: $g(g)$. Notice that there is func_code(func_code) since func_code must need exactly one input argument if we want that $g(g)$ will be well defined.

In the same sense as the way we "fix" this proof for the halting problem, we will try to "fix" the "proof" for general functions:

def g(func_text):
    return not returns_true(func_text(func_text))

And now notice that the very definition of $g$, requires an input which is a function that gets one argument.

If we say our functions were all from a set $A$ into a set $B$, then also $g$ has to be so, and thus $A$ must somehow be able to "encapsulate" all functions from $A$ to $B$ - which is clearly impossible (there are more functions than there are elements in $A$).

Hence, this claim - while making "intuitional" sense, breaks down when taking a look at it more carefully.