1
$\begingroup$

Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing machine.

There are other modifications one can make - it should answer halting for all Turing machine/input tape pairs except possibly for one pair, or for finitely many pairs or for finitely many Turing machines.

The standard proof doesn't seem to extend to these cases in an easy way.

$\endgroup$
  • 3
    $\begingroup$ I can encode the diagonalization widget with a bit of extra junk (include some unused states for instance) so ruling out a finite number of TMs will never rule out every instance of the standard counterexample in the proof. $\endgroup$ – Daniel Gratzer Nov 30 '18 at 17:39
  • $\begingroup$ I am not sure I understand your comment. Certainly if you knew the particular Turing machines that could fall, then the standard argument goes through but if you can't know the input on which you fail, how can you exclude them? $\endgroup$ – Asvin Nov 30 '18 at 17:43
  • $\begingroup$ So my understanding of your problem specification is that you are given $\langle M, i \rangle$, some TM and some input. You must return whether this halts if $M \neq M_e$ for some particular TM $M_e$ (the exception). Now, if this exception machine is not the diagonalization widget traditionally used to prove the halting problem is undecidable, you're in trouble. However, since there are many unimportant tweaks I can make to that construction you cannot rule them all out. Perhaps I misunderstood your description of the problem? $\endgroup$ – Daniel Gratzer Nov 30 '18 at 17:48
  • 1
    $\begingroup$ If the description is that there exists one language, though we do not get to know what it is, then we can just cook up two distinct encodings of the widget. at least one of them is not the exception and so one of them causes a contradiction. $\endgroup$ – Daniel Gratzer Nov 30 '18 at 17:52
  • 6
    $\begingroup$ This is not a research-level question. An undecidable problem stays undecidable if you change it for finitely many inputs. $\endgroup$ – Emil Jeřábek Nov 30 '18 at 18:57