Since the halting problem is undecidable, does that mean that there exists an always undecidable program?

Question

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!

Answer 1

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

Answer 2

The question is wrong. The "usual demonstration" proves that the deciding machine $D_0$ cannot exist, as that leads to contradiction. Therefore, the adversarial $A_0$ cannot exist either, as it has $D_0$ as a part/subroutine. It is then impossible to construct the discriminator $D_1$, it cannot check for $A_0$ source, when $A_0$ source cannot exist.

And if ignoring the previous argument, $D_1$ must now provide the correct hardcoded answer for $A_0$. But what is that answer supposed to be? There is no correct answer for what the impossible $A_0$ would do, so there is no useful answer to hardcode here. The "string of machines" doesn't happen.

Now to your question.

The proof of unsolvability says you cannot identify all machines, as some of them would simply use your identifier and then do the opposite of whatever it says. This cannot be sidestepped by hardcoding specific cases, as there is no correct answer for any such adversarial machine. You may recognize the source of a particular adversarial machine in finite time, but there is no hardcodable answer other than "unknown". There is also an infinite amount of variants of such machines (for example, by doing any simple calculation before the adversarial stuff), so you cannot recognize them all in finite time either.

You can have a machine that answers continues/stops/unknown in all cases though. It could simulate the machine to be tested for a million cycles. If it halts, the decider output "halts". If, during this time, the simulated machine and its tape gets to exactly the same state as observed in some earlier iteration, then we have proved it continues forever with some period less than a million iterations. So output "continues" then. In other cases, output "unknown". Honest and correct in all cases, but won't identify machines needing more than a million steps to repeat state. (And no machines that produce infinite output either.)

The proof of undecidability does not provide a particular machine that no turing machine can decide. All it does, is prove that you cannot identify all cases - as any perfect decider can be used as part of an adversarial machine that fools this perfect decider. It will necessarily fool all other perfect deciders too, as all perfect deciders must give the same answer in all cases!

Still, the proof does not provide a particular undecidable machine, as the given undecidable machine needs that perfect decider we cannot have. There may be other undecideable machines, but what they look like is currently unknown.

Answer 3

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.

Answer 4

I take it that we are calling a decider a machine that takes in a natural number $n$ and then prints out either "yes" or "no", where as observers we interpret the output as the decider's opinion of whether Turing machine $n$ halts on an empty tape. Consider the decider $D_y$ that always prints "yes," along with the one $D_n$ that always prints "no." If someone presents me with a Turing machine called always undecidable, I will say that, to the contrary, one of $D_y$ and $D_n$ will correctly decide that machine.