1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ OP cites Wikipedia for his original, perhaps you should go there and fix the referenced article. $\endgroup$
    – vonbrand
    Aug 13 at 23:18
  • $\begingroup$ The original g() is actually perfectly valid Python code, and this is the typical way to define recursive functions in Python (and in many other languages). In general, there's no issue with having a function refer to a symbol that has not yet been defined; if it's not available at runtime, it'd raise a NameError, but in this case, by the time g is called, it's already available. $\endgroup$
    – yoniLavi
    Sep 3 at 21:25
  • 1
    $\begingroup$ @yoniLavi Well, even though languages do technically allow it, its still not something easily available to TMs. For TMs, you will not have the definition of the TM available to use for itself (since it would create a paradox about the size of the TM's description). You could define a new notion of a recursive TM, but it will always boil down to creating a TM that gets an input of a description of another TM, and give that TM's description as an input to itself. $\endgroup$
    – nir shahar
    Sep 3 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.