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