State whether the language is in $R$, $RE$, etc. The intuition for the solution

Question

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?

EDITED

$$ \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}\} $$

Answer 1

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

Answer 2

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