0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ The point is not about having an infinite recursion, it is about having a contradictory output. No matter what the machine tells, the response can not be trusted because it's responses are paradoxical. $\endgroup$
    – Chaos
    Aug 5, 2023 at 21:03
  • $\begingroup$ Right. That seems to be what the proofs like the one attached get at but I find that less intuitive. So I am wondering if the fact that this leads to an infinite recursion can also be used as an argument for why halting problem can not be decided $\endgroup$
    – boinka
    Aug 5, 2023 at 21:06
  • $\begingroup$ I don't know whether there exists an argumentation about the Halting Problem being undecidable due to an infinite recursion. The proof that managed to convinced me personally can be found in the book Modern Compiler Design in C (by Andrew Appel) and it describes the problem throught functions rather than TMs. In that case the contraddiction is reached and one is not even tempted to reason about recursion: a simple case analysis on function composition suffices to see the contradictory nature of the assumption. I don't think infinite recursion plays a role here. $\endgroup$
    – Chaos
    Aug 5, 2023 at 21:18

2 Answers 2

1
$\begingroup$

$\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.

$\endgroup$
1
  • $\begingroup$ ty for the answer. Mb I was not sufficiently clear - the code i wrote is meant to be a "paraphrase" of the proof attached below it. The proof begins with "suppose H is a decider...". i borrow that assumption and take it as "assume h terminates...". My thinking was that the code for H is also universal because i could not find another way to construct it, but see how this could be wrong. $\endgroup$
    – boinka
    Aug 6, 2023 at 15:05
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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