Is this a weaker or stronger form of the halting problem

Question

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?

Answer 1

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: "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."

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