0
$\begingroup$

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.)

$\endgroup$

closed as off-topic by Yuval Filmus, Marzio De Biasi, David Eppstein, Jeffε, Kaveh Dec 1 '13 at 19:18

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

  • "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." – David Eppstein, Jeffε, Kaveh
  • "Questions on undergraduate-level computer science are off-topic here, but can be asked on Computer Science Stack Exchange. See also: What kind of questions are too basic?" – Yuval Filmus, Marzio De Biasi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ Seems more appropriate for cs.stackexchange. $\endgroup$ – Yuval Filmus Sep 12 '13 at 3:58
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Peeja Sep 12 '13 at 13:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.