Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

Question

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct?

TLDR: Halting problem is undecidable because it leads to infinite recursion and never stops.

Elaborating:

At the bottom, I have attached an example of how I have seen the proof presented in a few books(1), but to see recursion, I will express the proof in pseudocode:

Assume the existence of a decider H (an Turing machine that can determine if any program accepts or rejects):

function H(M: str, w: str) -> boolean:
   # returns true if M accepts w, false if M rejects w.
   result = M(w) # simulate running M on w
   return result

We can then build a Turing Machine D that computes the opposite of H:

function D(M: str) -> boolean:
   result_h = H(M, M)
   return not result_h

BUT if we call D on a description of itself, D(D), it will first call H(D, D) that in turn will call D(D) once again.

This is an infinite recursion that clearly never terminates. Therefore, the proof is invalid and the assumption of H is wrong and therefore H is not computable.

Question:

I find this to be an extremely intuitive explanation of why the problem is undecidable: because the assumption that H exists leads to an algorithm clearly never terminates.

So I was wondering what holes could there be in this argument or is this a solid way of thinking about undecidability?

Thanks!

1 The usual proof goes something like this (Introduction to the Theory of Computation, Third International Edition, Michael Sipser):

Answer 1

$\newcommand{\D}{\langle D \rangle}$

No, your argument does not prove the undecidability of the halting problem.

For one, your pseudocode for $H$ doesn't appear to even attempt to decide the Halting problem. All it does is simulate its arguments and yield the result. That is what a universal Turing machine does, not a halting decider.

Now, if you construct a diagonal machine for a universal Turing machine $U$, then it will go into an infinite loop, because $D(\D)$ simulates $U(\D,\D)$ which simulates $D(\D)$ and so on. That part is correct.

However, this shows that $U$ does not even satisfy the definition of a "decider," which is supposed to always halt on every valid input. $(\D,\D)$ is a valid input on which $U$ does not halt, so it is not a decider at all. If instead you say that the 'valid inputs' are necessarily deciders themselves, so that the simulation $U$ does must terminate, then this instead shows that the diagonal machine is not a decider, and thus not valid input to $U$. But a halting decider is supposed to operate successfully for every Turing machine, not just for terminating ones (since the 'halting problem' for halting Turing machines is trivial).

Also, your proposed proof is about a specific $H$. This does not establish that all Turing machines fail to decide halting, which is what the undecidability theorem is about. Your argument does show that any $H$ that implements a decision procedure for all machines cannot be like your pseudocode, because if it simply simulated its arguments there would be a diagonal program on which it didn't halt, and would not be a decider. But a proof needs to show that actual terminating algorithms also don't decide the halting problem, which your argument does nothing to establish.

Answer 2

No, you only gained intuition about why the code H you wrote is not the halting oracle.

What about all other possible attempts of implementing H? (Warning: do not try to argue that they too must enter an infinite loop, because that is blatantly false.)