I saw the solution but can't understand the intuition of the following question:

Let's define $$L^{\ge k} = \{w\in L : |w| \ge k\}$$ and $$L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^{\ge k} \}$$

$L\in R$ because $L=\emptyset$, the proof is a bit long and anyway I understood most of the steps, My question is about the intuition, what is the hint here that $L=\emptyset$ or any other hints for the solution?


$$ \overline{HP}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\} $$ It's the complementary language of $$ HP=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\} $$

  • 1
    $\begingroup$ What is $HP$? Is $\overline{HP}$ a complementary of $HP$? $\endgroup$
    – user114966
    Jan 16 '21 at 23:46
  • $\begingroup$ $HP=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\}$. Yes it's the complementary $\endgroup$ Jan 17 '21 at 0:05
  • 1
    $\begingroup$ @ChaosPredictor it would be nice if you can add that to the question. $\endgroup$ Jan 17 '21 at 1:14

The intuition is that finite languages are very simple in the sense that throwing a finite number of words from a language does not affect membership in $\text{R}$ or in $\overline{\text{RE}}$, etc. Therefore, since $L^{\geq k}$ is the result of throwing a finite number of words from $L$, we get that:

  1. $L(M)^{\geq k} \in \text{RE}$, and
  2. $\overline{HP}^{\geq k} \notin \text{RE}$.

So the language $L = \{ \langle M \rangle: \exists k: \ L(M)^{\geq k} = \overline{HP}^{\geq k}\}$ must be empty.

Formally speaking, we have the following claims:

Claim 1: For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A \leq_m A \setminus B$.

Hint for the proof of claim 1: $B$ is finite and thus decidable. Therefore, given input $x$ for the reduction, we can check whether $x\in B$. Then you can proceed easily. Think where to map inputs $x$ from $B$, and where to map inputs $x$ from $\overline{B}$.

We also have the following similar claim which could be useful.

Claim 2: For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A\setminus B \leq_m A $.

Given the above claims, we're done. Indeed, $\overline{HP} \notin \text{RE}$, and for every $k$, $\overline{HP}^{\geq k} = \overline{HP}\setminus \{w\in \overline{HP} : |w| < k\}$. That is, $\overline{HP}^{\geq k}$ equals a non-trivial infinite language minus a finite subset, and so by claim 1, $\overline{HP}^{\geq k} \notin \text{RE}$. Also, it holds that $L(M)^{\geq k} \in RE$ for every machine $M$ (this is easy, you can prove that directly using standard closure properties and the fact that $L(M)^{\geq k} = L(M)\setminus \{ w\in L(M): |w| < k\}$. Alternatively, you can use claim 2 but you have to be careful regarding the edge cases where $L(M)$ is trivial, etc.). Therefore, it cannot be the case that there is a machine $M$ with $L(M)^{\geq k} = \overline{HP}^{\geq k}$.


You could start from the fact that the language $HP$ of the Halting problem is r.e. If its complement $\overline{HP}$ were r.e. too then that would mean that $HP$ is recursive (in $R$) which is impossible.

Next, if there were at least one $k$ such that $L(M)^{\ge k} = \overline{HP}^{\ge k}$ then we could use this Turing machine $M$ to prove $\overline{HP}$ is r.e. as follow.

Split $\overline{HP}$ into two parts as

$$\overline{HP} = \{s \in HP : |s| < k\} \bigcup \overline{HP}^{\ge k}$$ or $$ \{s \in HP : |s| < k\} \bigcup L(M)^{\ge k}$$
The left set is in $R$ and $L(M)^{\ge k}$ is r.e, and hence $\overline{HP}$ is r.e. We have a contradiction. Therefore there is no such $k$ and hence $L$ is empty, that is in $R$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.