¿Recursivamente enumerables idiomas están cerrados bajo la operación de min(L)?

Question

Definir $\min(L)$, una operación de más de un idioma, de la siguiente manera:

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

En palabras: todas las cadenas en el lenguaje L que no tiene un prefijo adecuado en $L$

Pregunta: Recursivamente enumerable idiomas (RE) son cerrados bajo $\min$? Es decir, si $L$ RE, es $\min(L)$ RE?

Creo que la respuesta es NO, porque para aceptar una cadena de $w$, la máquina de Turing para $\min(L)$ a prueba de todos los prefijos de $w$, asegurando que ninguno pertenece a $L$. Sin embargo, desde la $L$ RE, su máquina de Turing no está garantizada para detener en todas las entradas.

Incluso si mi explicación tiene sentido (¿?), no será aceptado como medio de prueba en mi examen final. Necesito mostrar una reducción de un conocido no VOLVER idioma a $\min(L)$. Pero no sé cómo :(

Alguien puede ayudar?

Gracias!

Answer 1

Que $K$ ser cualquier r.e. No recursivo establecido y definir $$ L = \{1^x0 : x \in K\} \cup \{1^x00 : x \in \mathbb{N}\}. $ $ claramente $L$ es r.e. y lenguaje $\min(L)$ $$ \min(L) = \{1^x0 : x \in K\} \cup \{1^x00 : x \notin K\}. $ $ $\min(L)$ r.e., hubiera entonces $K$ sería recursivo.