Is this a weaker or stronger form of the halting problem Halting problem: There is no decider for $L =\{\langle M,w\rangle ~|~ M$ halts on $w \}$
This problem: For any $H$ which can decide some infinite subsets of $L$, then I can always, constructively find $\langle M,w\rangle$ such that $H(\langle M,w\rangle)$ is incorrect.
Here the infinite subset part is supposed to be like heuristics. Primitively checking for infinite loops and things. If someone comes up with a program which can mostly determine halting, I should always be able to come up with an adversarial case in which it fails.
Halting implies these adversarial cases exist, but can I find them at all? Can I find them efficiently?
The standard proof that the halting problem $L$ is undecidable also gives an efficient algorithm for constructing an instance on which a given Turing machine $H$ fails to solve the halting problem.
For any Turing machine $H$, let $M_H$ be a Turing machine implementing the following algorithm: &quot;On input $\langle P \rangle$ where $P$ is a Turing machine, run $H(\langle P, P \rangle)$. If it outputs $1$, run forever, otherwise halt.&quot;
By design, $H(\langle M_H, M_H \rangle)$ fails. Either it runs forever, or else it halts and gives the wrong answer to the question of whether $\langle M_H, M_H \rangle \in L$. Given $\langle H \rangle$, one can efficiently construct $\langle M_H, M_H \rangle$.