TITLE: Is L Recursively Enumerable or Not RE?
QUESTION [0 upvotes]: $L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) :  w \in a^*b^*|  
 \geq k \}$
My Interpretation of language is that L is a language which contains Turing machine whose language contains string less than k and also strings belong to $a^* b ^*$
My Analysis : Using Rice's Theorem, 
$T_{yes} = L$ and $T_{no} = a^*b^*$ 
By rice's first theorem we can say that this language is Undecidable and by using rice's second theorem we can say this it is not even recognizable because $T_{yes} \subset T_{no}$.
My intuitive approach : As we know language L is a set of TM which accept a set of strings length greater than k and are a subset of $a^* b^*$ then for language L to be Recursively Enumerable there must be yes cases for turing machines which are fulfilling the requirement and for no cases it might halt and reject or might stay in loop but the issue here is there might exist a string in $a^*b^*$ which might get accepted later and there are infinite such strings so turing machine can never give yes cases. Yes cases can only happen if TM checks all strings of ab and rejects which are not a part of language but this will not happen as there are infinite strings. 
This is not a proof but just my intuition.
Hence by using Rice's theorem we got to know that L is not even Recursively Enumerable but i've been told that my interpretation of language itself is wrong and L is Recursively Enumerable.

REPLY [1 votes]: Your interpretation of $L$ seems incorrect. The $|w \in L(M): w \in a^* b^*| \geq k$ is an unusual notation, but I'm sure it is meant in the sense of $|\{ w \in L(M): w \in a^* b^*\}| \geq k$, meaning "the set of $w$ in $L(M)$ that are in $a^*b^*$ is of size at least $k$", or in other words "$M$ accepts at least $k$ words from $a^*b^*$".
Based on this understanding, $L$ is recursively enumerable. Consider a TM $M'$ that iterates in lexicographic order over the tuples of the form $\langle M, k, l, s\rangle$ with $M$ TM and $k,l, s \in \mathbb N$ (since the set of all TM encodings and $\mathbb N$ are r.e., so is their product). For each such tuple, $M'$ simulates $M$ for at most $s$ steps on each word from $a^*b^*$ of length at most $l$. If $M$ accepts at least $k$ of these, $M'$ prints the pair $\langle M, k \rangle$.
You now have to argue that $M'$ recursively enumerates $L$: You have to show that $M'$ will eventually print each word of $L$ and never print a word not in $L$. This is straight-forward, but tedious depending on what level of formality is required of you. Your argument would be along the lines of:

Consider $\langle M, k \rangle \in L$. Thus for $W = \{ w \in L(M): w \in a^*b^*\}$, you have $|W| \geq k$. Let $W' \subseteq W$ be some subset with $|W'| = k$. Let $l$ be the length of the longest word in $W'$ and $s$ be the longest number of steps $M$ takes on a word from $W'$. You have $l$ and $s$ well-defined since $M$ halts on all $w \in W'$ by definition of $L(M)$ and $W'$ is finite. Then $M'$ will reach the tuple $\langle M, k, l, s \rangle$ after finitely many steps and after simulating $M$ on each word of length at most $l$ for at most $s$ steps will find all words from $W'$, thus finding at least $k$ words in $a^*b^*$ that $M$ accepts. Therefore $M'$ will emit $\langle M, k \rangle$.
Consider $w \notin L$. If $w$ is not of the form $\langle M, k \rangle$, then $M'$ can never emit $w$ by definition. If $w$ is of the form $\langle M, k \rangle$, then by definition of $L$, for $W = \{w \in L(M): w \in a^*b^*\}$, you have $|W| < k$. But then there can be no $s, l \in \mathbb N$, such that $M$ will accept at least $k$ words from $a^*b^*$ of length at most $l$ in at most $s$ steps. Therefore, $M'$ will never print $\langle M, k \rangle$.
{"set_name": "stack_exchange", "score": 0, "question_id": 3408438}