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?