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

cs.stackexchange https://cs.stackexchange.com/questions/113277

Frage

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!

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top