Are these languages RE? How would I determine this?

Question

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?

Answer 1

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!