<p>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.</p>

<p>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.</p>

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

CC BY-SA 4.0
2018-11-30T17:39:14.017Z
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.
daniel gratzer
CC BY-SA 4.0
2018-11-30T17:43:08.480Z
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?
Asvin
CC BY-SA 4.0
2018-11-30T17:48:02.000Z
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?
daniel gratzer
CC BY-SA 4.0
2018-11-30T17:49:38.623Z
Yes, that's right except i dont require M_e to be known in advance. I just require that there is at most one exception.
Asvin
CC BY-SA 4.0
2018-11-30T17:50:59.337Z
So if you change the widget used in the standard proof, the exceptional machine can change in response
Asvin
CC BY-SA 4.0
2018-11-30T17:52:21.840Z
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.
daniel gratzer
CC BY-SA 4.0
2018-11-30T17:53:28.007Z
Yes, I think that works!
Asvin
CC BY-SA 4.0
2018-11-30T18:57:11.323Z
This is not a research-level question. An undecidable problem stays undecidable if you change it for finitely many inputs.
Emil Jeřábek
<computability><turing-machines><halting-problem>
Solving the Halting problem for most inputs
Asvin
# Solving the Halting problem for most inputs

(Asked by: username_0 on 2018-11-30)

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.

**Tags:** computability, turing-machines, halting-problem
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: 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?  
> **username_0**: Yes, that's right except i dont require M_e to be known in advance. I just require that there is at most one exception.  
> **username_0**: So if you change the widget used in the standard proof, the exceptional machine can change in response  
> **username_1**: 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.  
> **username_0**: Yes, I think that works!  
> **username_2**: This is not a research-level question. An undecidable problem stays undecidable if you change it for finitely many inputs.  

---

## 0 answers

