# Recursively enumerable languages are closed under the min(L) operation?

Define $\min(L)$, an operation over a language, as follows:

$$min(L) = \{ w \mid \nexists x \in L, y \in \Sigma^+ , w=xy \}$$

In words: all strings in language L that don't have a proper prefix in $L$

Question: Recursively enumerable languages (RE) are closed under $\min$? That is, if $L$ is RE, is $\min(L)$ also RE?

I think the answer is NO, because in order to accept a string $w$, the Turing machine for $\min(L)$ would have to test all prefixes of $w$, ensuring that none belongs to $L$. However, since $L$ is RE, its Turing machine is not guaranteed to halt on all inputs.

Even if my explanation makes sense (does it?), it will not be accepted as a proof in my final exam. I need to show a reduction from a known non-RE language to $\min(L)$. But I don't know how :(

Can anyone help?

Thanks!

-
I think there is a shortcut: it is easy to see its complement is RE but not R. So if $min(L)$ is also RE, then both $min(L)$ and its complement are R, a contradiction. – Popopo Jun 26 '12 at 23:50

Let $K$ be any non-recursive r.e. set, and define $$L = \{1^x0 : x \in K\} \cup \{1^x00 : x \in \mathbb{N}\}.$$ Clearly $L$ is r.e., and the language $\min(L)$ is $$\min(L) = \{1^x0 : x \in K\} \cup \{1^x00 : x \notin K\}.$$ If $\min(L)$ were r.e., then $K$ would be recursive.