1
$\begingroup$

The usual demonstration of the halting problem's undecidability involves positing an adversarial machine (call it $A_0$) that runs the decider machine (call it $D_0$) on itself and performs the opposite of the answer it gets. But it would be possible to construct a machine $D_1$, that checked for the exact source code of $A_0$ and output the correct answer. Of course then another machine $A_1$ that runs $D_1$ instead of $D_0$ could also be constructed. And so on to any finite $n$.

So it seems like any given adversarial machine can be thwarted by another larger-indexed decider machine. So it appears that it does not directly follow from that demonstration that there is any single machine that there cannot be a decider machine constructed for. The proposition that there is no single machine that can decide for all cases still holds of course, but I'm interested in that slightly different question of whether there exists a machine that no decider machine can correctly identify whether it halts. Is the answer to that question known?

I can imagine a possible answer that any given machine must either halt or not so one of the trivial decider programs that always says the same answer would be correct. But it seems to me that there is a sensible notion of "non-trivially deciding" that would exclude examples like that. But maybe the fact I'm currently unable to describe that notion precisely indicates I'm wrong about that?

Edit: I think I now have a way of describing a notion of "non-trivially deciding", although now that name does not fit as well. First we need to change the problem slightly. In this version the decider machines output one of $halts$, $continues$, or $unknown$, indicating that the machine halts, does not halt, or the decider machine does not "know" respectively. So we can call decider machines that are correct in all of the cases that they output $halts$ or $continues$ "correct" or "honest" decider machines.

So now my question is, is there a machine that no single honest decider machine would identify correctly? By "identify correctly" I mean the decider outputs either $halts$ or $continues$ and that the outputs correctly correspond to the machine under examination's behaviour. By the definition of honest, if the machine under examination halts and the decider outputs $continues$ or the machine under examination does not halt, and the decider outputs $halts$ then the decider is not honest. So this definition excludes the decider machines that always output the same answer, including the one that always outputs $unknown$ by my definition of "identify correctly".

Edit 2: To elaborate on my notion of a decider machine correctly identifying a machine's behaviour, we can break the definition into two parts gaining some more vocabulary in the process.

First we have the criterion that the decider outputs $halts$ or $continues$ for that machine. We can call that criterion the identification criterion, and we can say of decider machines that they identify a machine if and only if they out one of $halts$ or $continues$ on that machine.

Second we have the criterion that the decider's output correspond to the to the machine under examination's behaviour. So if the examined machine halts and the decider outputs $halts$ the decider is correct about that machine. Similarly if the examined machine does not halt, a decider that outputs $continues$ would be correct. It seems useful to include outputting $unknown$ as "technically correct". So the full rules would be a decider is correct about a given examined machine if one of the following is true:

  • The examined machine halts and the decider outputs $halts$ or $unknown$
  • The examined machine does not halt and the decider outputs $continues$ or $unknown$

We can call this the "correctness" criterion, and say that a decider is correct about a given machine if and only if the above condition is true.

We can put the vocabulary back together and say that a decider correctly identifies a given machine if they identify that machine, and they are correct about that machine. So now we can state that the always $unknown$ decider does not correctly identify every machine since, while it is always correct about every machine, it does not identify any machines!

$\endgroup$
  • 1
    $\begingroup$ "I can imagine a possible answer that any given machine must either halt or not so one of the trivial decider programs that always says the same answer would be correct. But it seems to me that there is a sensible notion of "non-trivially deciding" that would exclude examples like that." Why? $\endgroup$ – orlp Sep 1 at 10:11
  • $\begingroup$ @orlp I've added what I think to be a precise description of what I wanted to describe. I had an intuition that one existed but I was unable to describe it at the time. $\endgroup$ – Ryan1729 Sep 1 at 18:31
  • $\begingroup$ It's still unclear to me when a decider is allowed to output "unknown". You say your rules exclude a decider that always returns "unknown", but by what mechanic do you do this? $\endgroup$ – orlp Sep 1 at 19:02
  • $\begingroup$ @orlp I've now added a more precise definition of "correct identification" and stated explicitly why that definition excluded the always $unknown$ decider. $\endgroup$ – Ryan1729 Sep 1 at 19:26
  • $\begingroup$ Still trivially avoidable. Consider the decider that simulates the machine for $c$ steps, if it halts before that, it outputs halt, otherwise it outputs unknown. $\endgroup$ – orlp Sep 1 at 20:47
2
$\begingroup$

Suppose you've come up with a machine $P_0$ which you claim decides the halting problem. I create a $Q_0$ that makes it malfunction somehow (your $P_0$ either ends up diverging or gives the wrong answer). The proof of the Halting Problem shows that I can always create such a $Q_0$.

"Aha!" you say. "But now I can create $P_1$, which is exactly like $P_0$—except that it checks whether its input is $Q_0$ and gives a hardcoded answer if so." Sure, you can do this. But then I can just create a $Q_1$ in exactly the same way that I created $Q_0$. This is always possible—that's how the proof works.

You can show by induction that you can always create a $P_n$ that has $n$ hardcoded special cases, protecting it against $n$ different $Q$s. In fact, for any "undecidable program" $Q$ I create, you can create a special $P$ that can decide it:

DoesItHalt(X):
    if X = Q, return [hardcode whichever answer is correct]
    else, return true

Therefore there is no "universally halting-undecidable program" $Q_\omega$. But I can also create a new $Q$ that defeats any $P$ you make, since you can have as many special cases as you like, but that number must be finite. Therefore there is no "universal halting-decider program" $P_\omega$ either (which is the whole point of Turing's proof).

$\endgroup$
0
$\begingroup$

The answer to your question is yes. That is exactly the whole point of the Halting Problem: It is impossible to build a recognizer that correctly answers "Yes" or "No" in finite time to the question "Does P halt?" for all P. We don't need to exhibit a P for which all recognizers fail to be able to prove that it exists.

$\endgroup$

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.