<p>The usual proof that the halting problem is undecidable already gives you exactly such an algorithm. Given an algorithm $A$, we construct an algorithm $B$ that on input $x$ computes $A$ on program $x$ and input $x$, and then enters an infinite loop iff $A$ answered "halts". Now consider giving $B$ itself as an input. If $A(B,B)=\text{"halts"}$ then $B$ doesn't halt on $B$, so $A$ is wrong. Same if $A(B,B)=\text{"doesn't halt"}$. So $\langle B,B\rangle$ is an example input on which $A$ is wrong.</p>

CC BY-SA 3.0
2013-09-12T13:07:24.067Z
That's awesome. Extra points for the most concise, readable proof of the the undecidability of the halting problem I've read (which clearly I didn't understand before asking the question).
Peeja
CC BY-SA 3.0
2013-09-12T03:57:23.683Z
2013-09-12T03:57:23.683Z
Yuval Filmus
<p>No Turing machine can decide whether any given Turing machine will halt for a given input. That is:</p>

<ol>
<li>If you give me a Turing machine which you <em>claim</em> can take a Turing machine and an input for that machine and will tell me whether the machine will halt,</li>
<li>There is some counterexample TM/input pair I can provide to that machine for which it will fail.</li>
</ol>

<p>This is the undecidability of the halting problem. Old news.</p>

<p>My question is: <strong>Can such a counterexample be <em>computed</em> for any candidate decider of the halting problem?</strong></p>

<p>That is, is there a Turing machine which can take as input some Turing machine and compute a TM/input pair for which the given Turing machine fails to decide the halting problem?</p>

<p>(Incidentally, I'm slightly over my head here, so I may be asking my question wrong, or asking a wrong question. Thoughts and pointers are welcome.)</p>

CC BY-SA 3.0
2013-09-12T03:58:05.903Z
Seems more appropriate for cs.stackexchange.
Yuval Filmus
<turing-machines><halting-problem><decidability>
Is refuting candidate deciders of the halting problem computable?
Peeja
# Is refuting candidate deciders of the halting problem computable?

(Asked by: username_0 on 2013-09-12)

No Turing machine can decide whether any given Turing machine will halt for a given input. That is:

1. If you give me a Turing machine which you *claim* can take a Turing machine and an input for that machine and will tell me whether the machine will halt,
2. There is some counterexample TM/input pair I can provide to that machine for which it will fail.

This is the undecidability of the halting problem. Old news.

My question is: **Can such a counterexample be *computed* for any candidate decider of the halting problem?**

That is, is there a Turing machine which can take as input some Turing machine and compute a TM/input pair for which the given Turing machine fails to decide the halting problem?

(Incidentally, I'm slightly over my head here, so I may be asking my question wrong, or asking a wrong question. Thoughts and pointers are welcome.)

**Tags:** turing-machines, halting-problem, decidability

> **Comments:**
> **username_1**: Seems more appropriate for cs.stackexchange.  

---

## 1 answers

### Answer by username_1 on 2013-09-12. Score: 3 | Accepted answer

The usual proof that the halting problem is undecidable already gives you exactly such an algorithm. Given an algorithm $A$, we construct an algorithm $B$ that on input $x$ computes $A$ on program $x$ and input $x$, and then enters an infinite loop iff $A$ answered "halts". Now consider giving $B$ itself as an input. If $A(B,B)=\text{"halts"}$ then $B$ doesn't halt on $B$, so $A$ is wrong. Same if $A(B,B)=\text{"doesn't halt"}$. So $\langle B,B\rangle$ is an example input on which $A$ is wrong.

> **Comments:**
> **username_0**: That's awesome. Extra points for the most concise, readable proof of the the undecidability of the halting problem I've read (which clearly I didn't understand before asking the question).  

---

