0
$\begingroup$

If $L$ is a decidable language, $M$ is a Turing machine that determines $L$. For $\forall s \in L$, M accepts, and for $\forall s \in \overline{L}$, M rejects

However, my question is that If $L$ is a recognizable undecidable language and $M$ is a Turing machine that recognizes $L$, for $\forall s \in L$, M accepts and for $\forall s \in \overline{L}$, M rejects or infinite loop? Or do both coexist, i.e., $\exists s \in \overline{L}$ and M rejects, and $\exists s \in \overline{L}$ and M infinitely loops?

$\endgroup$

1 Answer 1

0
$\begingroup$

If $L$ is recognizable but not decidable, and $M$ is a Turing machine that recognizes $L$ then, for each $s \in \overline{L}$, $M(s)$ either rejects or it does not halt.

The behaviour of $M$ can differ for different choices of $s \in \overline{L}$, so it is definitely possible that there are $s_1, s_2 \in \overline{L}$ such that $M(s_1)$ halts and rejects, while $M(s_2)$ does not halt.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.