1
$\begingroup$

I'm not sure how to go about solving this.

I tried this:

Suppose L is a Turing decidable language. Turing Machine M1 is a decider of L and M2 is a decider of the complement L We construct a TM U that simulates M1 and M2 on a word w. For any word w in complement L (this is infinite as it is the set of all possible words), M1 will always reject but M2 will always accept w. However, we cannot test this for all words in complement L as it is infinitely large, therefore it is undecidable.

I'm not sure if that is even remotely correct, would really appreciate some guidance on obtaining the correct answer

$\endgroup$
  • $\begingroup$ This is false: "this [complement $L$] is infinite as it is the set of all possible words". Think, for example, of $L = \Sigma^*$, which is trivially decidable and whose complement is empty. $\endgroup$ – Steven Apr 10 at 13:47
  • $\begingroup$ Can you specify what is the language you want to check for semi-decidability? How are you encoding the Turing decidable language $L$ in input? One way would be to do so through a TM $T$ that decides $L$. I.e., your language would be $L' = \{ T : T \text{ always halts} \wedge \not\exists w \in \Sigma^* : T(w) \text{ accepts } \}$, and the task is to figure out whether $L'$ is semi-decidable. Is this what you want? $\endgroup$ – Steven Apr 10 at 14:14
  • $\begingroup$ isn't it logically understandable for the complement of the empty set to be the universal set? and also what does Σ^∗ mean? $\endgroup$ – Big geez Apr 10 at 14:24
  • $\begingroup$ $\Sigma$ is the alphabet you are working with. And $\Sigma^*$ is the language containing of all possible words. The complement of $L$ is $\Sigma^*$ only when $L$ is empty, but you don't know whether $L$ is empty! In principle $L$ could be $\Sigma^*$ (which is Turing decidable). I think that we need a precise description of the language $L'$ that you want to check for semi-decidability. What are the words contained in $L'$? $\endgroup$ – Steven Apr 10 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.