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!