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

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

• What is $HP$? Is $\overline{HP}$ a complementary of $HP$? – Dmitry Jan 16 at 23:46
• $HP=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\}$. Yes it's the complementary – ChaosPredictor Jan 17 at 0:05
• @ChaosPredictor it would be nice if you can add that to the question. – Bader Abu Radi Jan 17 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$$.