3
$\begingroup$

Are these languages recursively enumerable?

  1. $L = \{ \langle A\rangle \mid x\in L(A)\implies |x|\leq 13\}$
  2. $L = \{\langle A\rangle \mid L(A) \subseteq \overline{L_{\mathrm{uni}}}\}$, where $L_{\mathrm{uni}} = \{\langle T\rangle x \in \{0,1\}^*\mid x \in L(T)\}$.

How would I prove / disprove that these languages are RE?

$\endgroup$
8
  • 4
    $\begingroup$ What do you think? In the exam you won't be able to use stackexchange... $\endgroup$ Jun 9, 2013 at 16:06
  • $\begingroup$ I don´t count on using stackexchange when writing exam.. I am learning and I don`t know how to solve this additional exercises, that is why I posted them here.. $\endgroup$
    – Jane
    Jun 9, 2013 at 18:16
  • $\begingroup$ @Jane: Sorry, I didn't see the title. Now that you are willing to show, that they are RE, I wonder whether you meant "$\dots\mid\forall x: |x|\leq 13\implies x\in L(A)$" instead of what I assumed. $\endgroup$
    – frafl
    Jun 9, 2013 at 19:25
  • 1
    $\begingroup$ some words with length $\leq 13$, exactly the words with length $\leq 13$, all those words (and possibly others) or only words with length $\leq 13$ (the last is not in RE, the first three are in RE (alternated enumeration)). $\endgroup$
    – frafl
    Jun 9, 2013 at 20:53
  • 1
    $\begingroup$ @babou $\langle . \rangle$ typically denotes some (binary) encoding of the given object, using a computable bijection. $\endgroup$
    – Raphael
    Jun 10, 2013 at 10:40

1 Answer 1

2
$\begingroup$

Neither of these languages are RE.

Here's an intuitive way to think about this - a language $L$ is RE iff for any string $w$, there is some finite piece of information you could provide about $w$ that could convince a computer that $w$ belongs to $L$.

In the case of language (1), what information could you give me that would convince me that a TM belonged to this language? To show that a TM belonged to that language, you'd need to convince me that every string ever accepted by that TM has length at most 13. It doesn't seem likely that there is any finite piece of information you could give me that could convince me that the TM has this property. (On the other hand, if a TM didn't have this property, it's easy to convince me of this - give me a string that the TM accepts that is longer than length 13, and I could confirm it by running the TM on that string and observing it accept).

To formally prove that language (1) is not RE, you could try doing a reduction from a language that's already known to not be RE. One good example of this would be the diagonalization language $L_D$:

$$ L_D = \{ \langle M \rangle | M \mbox{ is a TM and } \langle M \rangle \notin L(M) \}$$

This is the set of all descriptions of TMs that don't accept themselves. You can reduce $L_D$ to your language $L$ using the following reduction: given a TM $M$, build a new TM $N$ that does the following:

When $N$ receives an input string $w$, it first runs $M$ on $\langle M \rangle$. If $M$ accepts its own description, then $N$ accepts $w$. If $M$ rejects its own description, then $N$ rejects $w$. (Implicitly, if $M$ loops on its own description, then $N$ loops on $w$)

This machine has the property that if $M$ does not accept itself, then $N$ never accepts anything at all, and so $\langle N \rangle \in L$. On the other hand, if $M$ does accept itself, then $N$ accepts everything, so $\langle N \rangle \notin L$. This is a mapping reduction from $L_D$ to $L$, and since $L_D \notin RE$, this shows $L \notin RE$.

I'll leave the second of these as an exercise. Use the same intuition as before to think about why the language isn't $RE$, then try using a mapping reduction from $L_D$ to formalize it.

Hope this helps!

$\endgroup$
1
  • $\begingroup$ One more question.. What about complements? I think, that first one is RE as we can find TM which can accepts words of length more than 13, but I don´t know for second one.. $\endgroup$
    – Jane
    Jun 10, 2013 at 5:38

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.