Demuestra que EXT,TOT e INF no son enumerables recursivamente

Question

Actualmente estoy trabajando en el método de reducción para demostrar que un conjunto no es recursivamente enumerable, pero estoy luchando para encontrar funciones adecuadas para las reducciones. En concreto he empezado a trabajar en la demostración de que el conjunto EXT no es r.e.:

$$EXT=\{x|\phi_x \text{ is extensible to a total recursive function}\}$$

Mi intuición me lleva a intentar encontrar una reducción de $\overline{K}$ a EXT definiendo una función como ésta: $$f(x)=\left\{\begin{matrix} \text{extensible function} \quad \text{if } x \epsilon \overline{K} \\ \text{non-extensible function} \quad \text{if } x\epsilon K \end{matrix}\right.$$

utilizando una función ya total como función extensible (ya es total por lo que también debería ser extensible a total) y, para la función no extensible algo así:

$$g(x)=\left\{\begin{matrix} x \quad \text{if } x \epsilon K \\ \uparrow \quad \text{if } x\epsilon \overline{K} \end{matrix}\right.$$

que no puede extenderse al total ya que hacerlo implicaría que K es recursivo, lo que sabemos que no lo es. Sin embargo, no estoy seguro de si esto funcionaría dentro del método de reducción o no, ya que aplicaría g(x) sólo cuando x $\epsilon$ K.

En cuanto a los otros dos conjuntos: $$TOT=\{x|\phi_x \text{ is total}\} \\ INF=\{x|dom(\phi_x) \text{is infinite}\}$$

de nuevo, me indicaron que utilizara una reducción de $\overline{K}$ al conjunto, pero de nuevo me encuentro con dificultades para encontrar una función adecuada para la reducción. Agradeceré cualquier ayuda para comprender mejor el método.

EDIT: Pensé en el hecho de que la literatura por ahí podría no ser coherente. K es el conjunto de problemas de detención, lo que significa que: $$K= \{ x | \phi_x(x) \downarrow \}$$

Answer 1

En primer lugar, un breve comentario sobre la extensibilidad en general. La función $g$ usted describe es extensible a una función recursiva total, contrariamente a lo que afirmas - a saber, que es extensible por la función identidad $x\mapsto x$ . Cuando ampliamos una función recursiva parcial a una función recursiva total, tenemos no necesitan (a priori) seguir la pista del dominio original, por lo que el hecho de que $dom(g)$ se complica en modo alguno impide directamente $g$ de ser extensible.

Hay que esforzarse un poco más para obtener una función no extensible. Como una pista parcial, tenga en cuenta que (la fijación de algunos $x$ ) si tenemos algún $s$ de forma que sepamos $$\varphi_x(x)\downarrow\iff\varphi_x(x)[s]\downarrow,$$ entonces podemos saber si $x\in K$ simplemente ejecutando $\varphi_x(x)$ para $s$ -muchos pasos; a la inversa, para $x\in K$ podemos encontrar el escenario $s$ en cuyo momento $\varphi_x(x)\downarrow$ .

---

Pero digamos que hemos resuelto el problema anterior, y tenemos una función no extensible $h$ . Entonces, ¿cómo podemos utilizar esto para reducir $\overline{K}$ a $EXT$ ?

Bueno, supongamos que te dan un $x$ y quiere saber si $x\in \overline{K}$ . Para ello, se desea construir una función $f_x$ que se encuentra en $EXT$ si $x\in\overline{K}$ - es decir, si nunca vemos $\varphi_x(x)$ convergen.

La estrategia general para hacer este tipo de cosas es pensar en $f_x$ en términos de " hasta "a saber, que desea $f_x$ sonar como $$\mbox{"do [blah] until (if ever) $ \varphi_x(x) $ converges, after which point do [foo]."}$$ Aquí [blah] debe ser algún comportamiento que hace que $f_x$ parezca extensible, y [foo] debe ser algún comportamiento que haga que $f_x$ parecen improrrogables.

Parecer extensible es fácil - por ejemplo, podemos simplemente requerir $f_x(y)$ no se defina hasta que veamos $\varphi_x(x)$ convergen (la función indefinida en todas partes es definitivamente extensible). Buscar no extensibles es más difícil, pero aquí es donde nuestro $h$ - una vez que lo tenemos - entra: el $f_x$ que queremos debería ser "Parecer la función siempre indefinida hasta que veamos $\varphi_x(x)$ convergen, momento en el que se comportan como $h$ ." Ahora sólo tienes que precisarlo.