Subset of regular language $a^*$

Question

Given $L\subseteq a^*$, then

1. $L$ is definitely decidable
2. $L$ is definitely Turing – recognizable
3. $L$ may not be Turing – recognizable.
4. $L$ is regular

---

My attempt:

$L$ may not be regular, regular languages not closed under subset property $(L=a^{n^2})$.

$L$ can be CSL, so option $(2)$ can be true.

If $L$ is REC(Recursive) then option $(1)$ will be true.

If $L$ is RE(Recursively enumerable) then option $(2)$ will be true.

But, I stuck for $L$ : Is it RE or REC? Can you explain, please?

Answer 1

Let $ S \subseteq \mathbb{N} $ not be $ RE $.

Take $ L = \{ a^n \ | \ n \in S \} $.

Then $ L $ is not $ RE $.

You can also construct explicit examples of such sets, like $ L = \{ a^n \ | \text{ The } n^{\text{th}} \text{ Turing machine halts on all inputs} \} $.

To go even further, any infinite set has subsets which are not $ RE $. Let $ A \subseteq \mathbb{N} $ be an infinite set. If $ A $ is not $ RE $ take $ L = A $. If $ L $ is $ RE $, then a Turing machine exists which enumerates the elements of $ A $. let $ a_0, a_1 \dots $ be the sequence enumerated by such a Turing machine. Then take $ L = \{ a_n \ | \text{ The } n^{\text{th}} \text{ Turing machine halts on all inputs} \} $. If $ L $ is $ RE $, then we can recognize the set of Turing machines which halt on all inputs as follows: Given a Turing machine encoded as an integer $n$, compute $ a_n $ and check if it is in $ L $. Hence $ L $ is not $RE$.