¿Es la diferencia de dos conjuntos recursivamente enumerables, reducible a $K$ ?
$W_x/W_y=\{z|z \in W_x \& z \notin W_y\}$
$K=\{x|\Phi_x(x) \downarrow\}$
$W_x= \text{dom}(\Phi_x)$
Respuestas
¿Demasiados anuncios?
iturki
Puntos
106
No.
Dejemos que $\omega$ denotan el conjunto de números naturales. $K$ es c.e. pero incomputable. Si un conjunto $A$ y su complemento $\bar{A} = \omega - A$ es c.e., entonces $A$ debe ser computable. Por lo tanto, $\bar{K} = \omega - K$ el complemento de $K$ no es un conjunto c.e.
Está claro que $\omega$ el conjunto de los números naturales, es c.e. (es computable). $K$ es c.e. Por lo tanto
$\omega - K$ es una diferencia de dos conjuntos c.e. $\omega - K = \bar{K}$ que como se ha mencionado anteriormente no es c.e.
Supongamos que $\omega - K = \bar{K}$ era muchos a uno reducible a $K$ ; en las anotaciones $\bar{K} \leq_m K$ . Desde $K$ es c.e., $\bar{K}$ tendría que c.e. (ver el pequeño lema bajo la línea). Esto es una contradicción.
Si si dos conjuntos $A \leq_m B$ (son reducibles de muchos a uno) y $B$ es c.e., entonces $A$ es c.e.
Por definición de $A \leq_m B$ existe una función computable $f$ tal que
$x \in A$ si y sólo si $f(x) \in B$ .
Desde $B$ es c.e., $B = W_n$ para algunos $n$ . Definir una nueva función parcial computable
$\Psi(x) = \begin{cases} 0 & \quad \text{if }\Phi_n(f(x)) \downarrow \\ \uparrow & \quad \text{otherwise} \end{cases}$
Desde $\Psi$ es parcialmente computable, tiene un índice $p$ . Es decir, $\Psi = \Phi_p$ . Entonces $A = W_p$ desde $x \in A$ si y sólo si $f(x) \in B$ si y sólo si $\Phi_n(f(x)) \downarrow$ si y sólo si $\Phi_p(x) \downarrow$ . $A$ es c.e.
¿Qué tipo de reducción busca?
Es trivial Turing reducible porque si tienes un $K$ -oráculo disponible puedes simplemente decidir $W_x$ y $W_y$ .
No es muchos-uno reducible Sin embargo, porque se toma $W_x$ para ser todo, una reducción de muchos te diría que el complemento de un lenguaje r.e. es r.e. (lo que se sabe que es falso).
