Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

49 Views Asked by At

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

enter image description here