No Turing machine can decide whether any given Turing machine will halt for a given input. That is:
- 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,
- 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.)