0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ can you expand on the definition of $TM_0$ here? $\endgroup$ – nir shahar Jun 7 '20 at 19:52
  • $\begingroup$ is it just the set of all turing machines? why is there a "0" subscript there? $\endgroup$ – nir shahar Jun 7 '20 at 19:53
  • $\begingroup$ $TM_0$ is a set of all TM over binary alphabet $\endgroup$ – stackoverload Jun 7 '20 at 21:04
  • $\begingroup$ 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) $\endgroup$ – nir shahar Jun 7 '20 at 21:07
  • $\begingroup$ 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)$ $\endgroup$ – stackoverload Jun 7 '20 at 21:14
0
$\begingroup$

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

$\endgroup$

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.