5
$\begingroup$

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!

  • 1
    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.2012-06-26

1 Answers 1

5

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.