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.


closed as off-topic by Emil Jeřábek, cody, Peter Shor , Gamow, domotorp Dec 2 '18 at 20:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, cody, Peter Shor , Gamow, domotorp
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$ – jozefg 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$ – jozefg 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$ – jozefg 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