Un conjunto computablemente enumerable $m$ -se reduce al problema de detención

Question

Estoy tratando de mostrar que si $A$ es c.e., entonces $A\leq_m K$ , donde $K$ es el conjunto de todos los programas que se detienen sobre sí mismos.

Estoy tratando de utilizar esencialmente la misma estrategia que he descrito aquí .

$A$ es c.e., por lo que es el dominio de una función computable que es calculada por un programa $p$ . Considere la función $$V:N\times N\to N\\(n,x)\mapsto 1 \text{ if $ p $ halts on argument $ n $ in $ \N - x $ steps} $$ De lo contrario, $V$ es indefinido. Ahora desde la existencia de la función universal de Godel $U$ (definido aquí ) se deduce que existe un total computable $s:N\to N$ tal que para todo $x,n\in N$ $$V(n,x)=U(s(n),x).$$

• si $n\notin A$ entonces $V$ es siempre indefinido, por lo que $s(n)$ no se encuentra en $K$ (por lo demás $U(s(n),s(n))$ se habría definido).
• si $n\in A$ entonces $V$ se define para grandes $x$ . Quiero concluir que $V(s(n),s(n))$ se define (de modo que $s(n)\in K$ que concluiría la prueba), pero tal vez $V$ se define para $x$ s tal que $s(n)< x$ . ¿Cómo resolver este problema?

---

Después de ver la respuesta de HallaSurvivor, creo que puedo definir $V$ de la siguiente manera:

$$V:N\times N\to N\\ (n,x)=\chi_A(n)$$ donde $\chi_A$ es la función semicaracterística de $A$ . Se trata de una función computable porque $\chi_A$ es computable. Ahora bien, si $n\in A$ Entonces, en particular $U(s(n),x)$ se define para todos los $x$ (incluyendo $x=s(n)$ ), y de ello podemos concluir que $s(n)\in K$ .

Hágame saber si mi razonamiento no es correcto.

Answer 1

Dejemos que $A \subseteq \mathbb{N}$ ser c.e.

Para mostrar $A \leq_m K$ queremos encontrar una función computable $f : n \mapsto \ulcorner M_n \urcorner$ para que $n \in A \iff M_n(\ulcorner M_n \urcorner) \downarrow$ . Aquí estoy escribiendo $M_n(x) \downarrow$ si el cómputo se detiene, y $\ulcorner M \urcorner$ para alguna codificación de $M$ .

Dejemos que $\chi_A$ sea un semidecisor para $A$ . Es decir

$$\chi_A(n) = \begin{cases} 1 & n \in A \\ \text{undefined} & \text{otherwise} \end{cases}$$

Considere el programa $M_n(x)$ que ignora su entrada y calcula $\chi_A(n)$ . Entonces

$$n \in A \iff \chi_A(n) \downarrow \iff M_n(\ulcorner M_n \urcorner) \downarrow \iff \ulcorner M_n \urcorner \in K$$

Se puede argumentar por la tesis de la iglesia-turing que $n \mapsto \ulcorner M_n \urcorner$ es computable, pero con suficiente persistencia podrías hacerlo directamente.

---

Espero que esto ayude ^_^