3
$\begingroup$

Let $L_{1}$ and $L_{2}$ be two languages defined as follows :
$L_1 = \{ \langle M\rangle \mid L(M) \neq \emptyset \}$
$L_2 = \{ \langle M\rangle \mid L(M) = \emptyset \}$
where $\langle M\rangle$ denotes the encoding of a Turing Machine $M$. $L_{1}$ is the set of encodings of TMs that accept at least one string (i.e. the with non-empty languages), and $L_{2}$ is the set of encodings of TMs that do not accept any string (i.e. with empty lanugages). By making a language out of such encodings, I am essentially asking a Turing Machine to decide on another Turing machine as to whether the second TM has an empty language or not. This is essentially the halting problem, and so both languages are undecidable.

Now, I am not able to characterize $L_{1}$ and $L_{2}$ from among

  • not recursively enumerable
  • recursively enumerable but not recursive
  • recursive
$\endgroup$

migrated from cstheory.stackexchange.com Jan 10 '13 at 2:48

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ I notice that you've posted several questions along the same lines in quick succession. Perhaps it would help your learning to wait a moment and see the answers you receive, as your questions are closely related. Or do you have an assignment due today? $\endgroup$ – Luke Mathieson Jan 10 '13 at 3:57
  • $\begingroup$ No @LukeMathieson I did not have an assignment due. These are questions that I have sat on for some time now. My examination is approaching, so I put them all in one shot to the wrong site (unfortunately) $\endgroup$ – Arjun J Rao Jan 14 '13 at 7:28
  • $\begingroup$ @ArjunJRao, good luck in your exam then! $\endgroup$ – Luke Mathieson Jan 14 '13 at 8:56
3
$\begingroup$

As you note, both languages are undecidable, so neither are recursive. Then the remaining possiblities are recursively enumerable or not.

Note that $L_{1} = \overline{L_{2}}$, so if they were both recursively enumerable, then they would both be recursive, so we know at least one is not even recursively enumerable.

It turns out that $L_{1}$ is recursively enumerable, given an input $\langle M\rangle$ we can simulate $M$ on all strings over the alphabet by interleaving the execution of $M$ on each string. It may take a long time, but if $M$ accepts something, we eventually (in finite time) find it, so we can recognise that $\langle M\rangle \in L_{1}$.

Then simply by logical deduction, $L_{2}$ can't be recursively enumerable, as it is already co-r.e., but not recursive.

$\endgroup$
  • $\begingroup$ What does you mean when you say 'interleave the execution of M on each string' ? $\endgroup$ – Arjun J Rao Jan 14 '13 at 15:26
  • $\begingroup$ @ArjunJRao The technique is also called dovetailing; in phase $i$, you execute $i$ steps in each of the tasks $1,\dots,i$. $\endgroup$ – Raphael Jan 14 '13 at 20:40

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.