New answers tagged semi-decidability
0
Using contradiction suppose $L=\{\left< M_1,M_2 \right>|L(M_1)\subset L(M_2)\}$ is semi-decidable. So there exists Turing machine $T$ which for input $\left<M_1,M_2\right>$ if $L(M_1)\subset L(M_2)$ will halt and accept.
We should use this Turing machine $T$ to make another Turing machine $T'$ which halt and accept on input $\left<w,M\right&...
0
Q1: A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never ...
2
Just take for $L_2$ an undecidable language of $a^*$ and take $L_1 = L_2 \cup \{b\}$. Then $L_2$ is also undecidable and $L_2 - L_1 = \{b\}$ is regular.
2
As you suspected, it can happen that $L_1-L_2\not=a^*$. The assumption that $H$ does not contain $a^*$ does not imply that $\lnot H$ must contain $a^*$. For example, if $H\cap a^*= \{a^2\}$, then $\lnot H$ does not contain $a^2$, let alone $a^*$.
The technique to arrive at a simple solution is to let the regular part be disjoint with $L_2$.
Here is the ...
3
Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part.
Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define
$$L_2 = \lbrace b w \mid w \in H\rbrace$$
and
$$L_1 = L_2 \cup \lbrace a \rbrace.$$
Now it is obvious ...
Top 50 recent answers are included
