<p>The standard proof that the halting problem <span class="math-container">$L$</span> is undecidable also gives an efficient algorithm for constructing an instance on which a given Turing machine <span class="math-container">$H$</span> fails to solve the halting problem.</p>
<p>For any Turing machine <span class="math-container">$H$</span>, let <span class="math-container">$M_H$</span> be a Turing machine implementing the following algorithm: &quot;On input <span class="math-container">$\langle P \rangle$</span> where <span class="math-container">$P$</span> is a Turing machine, run <span class="math-container">$H(\langle P, P \rangle)$</span>. If it outputs <span class="math-container">$1$</span>, run forever, otherwise halt.&quot;</p>
<p>By design, <span class="math-container">$H(\langle M_H, M_H \rangle)$</span> fails. Either it runs forever, or else it halts and gives the wrong answer to the question of whether <span class="math-container">$\langle M_H, M_H \rangle \in L$</span>. Given <span class="math-container">$\langle H \rangle$</span>, one can efficiently construct <span class="math-container">$\langle M_H, M_H \rangle$</span>.</p>

CC BY-SA 4.0
2021-04-22T12:43:17.770Z
I didn't think of that. Thanks.
abrahimladha
CC BY-SA 4.0
2021-04-22T03:14:45.967Z
2021-04-22T03:14:45.967Z
William Hoza
<p>Halting problem: There is no decider for <span class="math-container">$L =\{\langle M,w\rangle ~|~ M$</span> halts on <span class="math-container">$w \}$</span></p>
<p>This problem: For any <span class="math-container">$H$</span> which can decide some infinite subsets of <span class="math-container">$L$</span>, then I can always, constructively find <span class="math-container">$\langle M,w\rangle$</span> such that <span class="math-container">$H(\langle M,w\rangle)$</span> is incorrect.</p>
<p>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.</p>
<p>Halting implies these adversarial cases exist, but can I find them at all? Can I find them efficiently?</p>

<halting-problem>
Is this a weaker or stronger form of the halting problem
abrahimladha
# Is this a weaker or stronger form of the halting problem

(Asked by: username_0 on 2021-04-22)

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?

**Tags:** halting-problem

---

## 1 answers

### Answer by username_1 on 2021-04-22. Score: 3 | Accepted answer

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

> **Comments:**
> **username_0**: I didn't think of that. Thanks.  

---

