# Semi-decidability of the language $\overline{L_{\epsilon}}$

Firstly consider the problem: given $$L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$$ where $$R(M)$$ are encoded transitions of $$M \in TM_0$$. Assume for contradiction $$\overline{L_{H}}$$ is semi-decidable, then there is $$Q \in TM_0$$ with $$L(Q) = \overline{L_{H}}$$ therefore for every $$M \in TM_0$$ we have the following $$Q \ accepts \ input \ R(M)w \iff M \ does \ not \ accept \ input \ w \ \ \ \ (1)$$ Then we construct machine $$Z$$ s.t. doubles the input and runs machine $$Q$$. Observe the following for arbitrary $$M \in TM_0$$: \begin{alignat*}{2} Z \ accepts \ input \ R(M) &\iff Q\ accepts \ input \ R(M)R(M)\\ &\iff M \ does \ not \ accept \ input \ R(M) \end{alignat*} Taking $$M = Z$$ will yield us a contradiction. Hence, $$\overline{L_{H}}$$ is not semi-decidable.

The same technique I am trying to apply for the case $$L_{\epsilon} = \{R(M) : M \in TM_0 \ \text{s.t. M accepts \epsilon}\}$$ where $$R(M)$$ are encoded transitions of $$M \in TM_0$$. But I am facing some troubles. Assume for contradiction $$\overline{L_{\epsilon}}$$ is semi-decidable, then there is $$Q \in TM_0$$ with $$L(Q) = \overline{L_{\epsilon}}$$ therefore for every $$M \in TM_0$$ we have the following $$Q \ accepts \ input \ R(M) \iff M \ does \ not \ accept \ input \ \epsilon$$ Then I cannot really find appropriate $$Z$$ for this case, as doubling the input simply won't work. Any suggestions are appreciated.

• can you expand on the definition of $TM_0$ here? – nir shahar Jun 7 '20 at 19:52
• is it just the set of all turing machines? why is there a "0" subscript there? – nir shahar Jun 7 '20 at 19:53
• $TM_0$ is a set of all TM over binary alphabet – stackoverload Jun 7 '20 at 21:04
• Then i think im misunderstanding something. Why would $Q$ terminate on $R(M)w$ if and only if $M$ doesnt terminate on $w$? I think you meant there to be: $Q$ accepts $R(M)w$ if and only if $M$ does not accept $w$. The first part of the proof still would be correct (except for this small change) – nir shahar Jun 7 '20 at 21:07
• So the second part just doubles the input and you get $R(M)R(M)$ which is accepted by $Q$, but then $M$ doesn't accept $R(M)$ by $(1)$ – stackoverload Jun 7 '20 at 21:14

## 1 Answer

Assume for contradiction $$\overline{L_{\epsilon}}$$ is semi-decidable. It's easily proven that $$L_{\epsilon}$$ is semi-decidable by reduction to the HALTING problem, i.e. $$L_{H}$$ is semi-decidable. If $$L_{\epsilon}$$ and $$\overline{L_{\epsilon}}$$ are semi-decidable, hence $$L_{\epsilon}$$ is decidable. This is a contradiction, as $$L_{\epsilon}$$ as well as $$L_{H}$$ are semi-decidable.

In this prove the following claim was used:

$$\textbf{Claim:} \text{ If L and \overline{L} are semi-decidable, then L is decidable}$$