4.6 Resultados básicos presentados en paradigma recursivo

En esta sección presentaremos varios de los resultados básicos de computabilidad, expresados en el paradigma recursivo, ya que es el mas habitual y cómodo. Varios de estos resultados ya han sido establecidos dentro del desarrollo de la computabilidad efectiva en el Capítulo Procedimientos Efectivos. A estos resultados los enunciaremos dentro del paradigma de Godel y daremos pruebas rigurosas matemáticas de ellos usando la teoría desarrollada hasta ahora. Sin embargo, veremos que hay otros resultados que son dependientes del desarrollo matemático hecho y aportan nueva información al paradigma filosófico (la indecidibilidad del halting problem, por ejemplo).

Como veremos muchas de las pruebas serán de naturaleza imperativa basadas en la equivalencia del paradigma de Godel con el imperativo de Neumann.

4.6.1 Lema de división por casos para funciones \(\Sigma\)-recursivas

Proof. Probaremos el caso \(k=2\) y \(O=\Sigma^{\ast}\). Además supondremos que \(n=m=1\). Sean \(\mathcal{P}_{1}\) y \(\mathcal{P}_{2}\) programas que computen las funciones \(f_{1}\) y \(f_{2}\), respectivamente. Para \(i=1,2\), definamos \[H_{i}=\lambda tx_{1}\alpha_{1}\left[Halt^{1,1}(t,x_{1},\alpha_{1},\mathcal{P}_{i})\right]\] Notar que \(D_{H_{i}}=\omega^{2}\times\Sigma^{\ast}\) y que \(H_{i}\) es \(\Sigma\)-mixta. Además sabemos que la función \(Halt^{1,1}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. por lo cual resulta fácilmente que \(H_{i}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Por Independencia del Alfabeto tenemos que \(H_{i}\) es \(\Sigma\)-p.r. y por lo tanto el Segundo Manantial de Macros nos dice que en \(\mathcal{S}^{\Sigma}\) hay un macro: \[\left[\mathrm{IF}\;H_{i}(\mathrm{V}1,\mathrm{V}2,\mathrm{W}1)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Para hacer mas intuitivo el uso de este macro lo escribiremos de la siguiente manera \[\left[\mathrm{IF}\;Halt^{1,1}(\mathrm{V}1,\mathrm{V}2,\mathrm{W}1,\mathcal{P}_{i})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Ya que cada \(f_{i}\) es \(\Sigma\)-computable, el Primer Manantial de Macros nos dice que en \(\mathcal{S}^{\Sigma}\) hay macros \[\begin{aligned} & \left[\mathrm{W}2\leftarrow f_{1}(\mathrm{V}1,\mathrm{W}1)\right]\\ & \left[\mathrm{W}2\leftarrow f_{2}(\mathrm{V}1,\mathrm{W}1)\right] \end{aligned}\] Sea \(\mathcal{P}\) el siguiente programa: \[\begin{array}{l} \mathrm{L}1\ \mathrm{N}20\leftarrow\mathrm{N}20+1\\ \left[\mathrm{IF}\;Halt^{1,1}(\mathrm{N}20,\mathrm{N}1,\mathrm{P}1,\mathcal{P}_{1})\;\mathrm{GOTO}\;\mathrm{L}2\right]\\ \left[\mathrm{IF}\;Halt^{1,1}(\mathrm{N}20,\mathrm{N}1,\mathrm{P}1,\mathcal{P}_{2})\;\mathrm{GOTO}\;\mathrm{L}3\right]\\ \mathrm{GOTO}\;\mathrm{L}1\\ \mathrm{L}2\ \left[\mathrm{P}1\leftarrow f_{1}(\mathrm{N}1,\mathrm{P}1)\right]\\ \mathrm{GOTO}\;\mathrm{L}4\\ \mathrm{L}3\ \left[\mathrm{P}1\leftarrow f_{2}(\mathrm{N}1,\mathrm{P}1)\right]\\ \mathrm{L}4\ \mathrm{SKIP} \end{array}\] Nótese que \(\mathcal{P}\) computa la función \(f_{1}\cup f_{2}\) por lo cual ya que sabemos que Godel vence a Neumann, la función \(f_{1}\cup f_{2}\) es \(\Sigma\)-recursiva.  

La prueba del lema anterior es de naturaleza imperativa ya que da explícitamente un programa (de todas maneras usa el paradigma recursivo o Godeliano para justificar la existencia de los macros). A continuación daremos una prueba la cual es mas recursiva (aunque aun usa el paradigma imperativo en la existencia de los programas \(\mathcal{P}_{i}\)).

Proof. Sean \(\mathcal{P}_{1}\) y \(\mathcal{P}_{2}\) programas que computen las funciones \(f_{1}\) y \(f_{2}\), respectivamente. Sean \[\begin{aligned} P_{1} & =\lambda t\vec{x}\vec{\alpha}\left[Halt^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}_{1})\right]\\ P_{2} & =\lambda t\vec{x}\vec{\alpha}\left[Halt^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}_{2})\right] \end{aligned}\] Nótese que \(D_{P_{1}}=D_{P_{2}}=\omega\times\omega^{n}\times\Sigma^{\ast m}\) y que \(P_{1}\) y \(P_{2}\) son \((\Sigma\cup\Sigma_{p})\)-p.r.. Ya que son \(\Sigma\)-mixtos, el Teorema 4.2 nos dice que son \(\Sigma\)-p.r.. También nótese que \(D_{M((P_{1}\vee P_{2}))}=D_{f_{1}}\cup D_{f_{2}}\). Definamos \[\begin{aligned} g_{1} & =\lambda\vec{x}\vec{\alpha}\left[E_{\ast1}^{n,m}(M\left((P_{1}\vee P_{2})\right)(\vec{x},\vec{\alpha}),\vec{x},\vec{\alpha},\mathcal{P}_{1})^{P_{1}(M\left((P_{1}\vee P_{2})\right)(\vec{x},\vec{\alpha}),\vec{x},\vec{\alpha})}\right]\\ g_{2} & =\lambda\vec{x}\vec{\alpha}\left[E_{\ast1}^{n,m}(M\left((P_{1}\vee P_{2})\right)(\vec{x},\vec{\alpha}),\vec{x},\vec{\alpha},\mathcal{P}_{2})^{P_{2}(M\left((P_{1}\vee P_{2})\right)(\vec{x},\vec{\alpha}),\vec{x},\vec{\alpha})}\right] \end{aligned}\] Nótese que \(g_{1}\) y \(g_{2}\) son \(\Sigma\)-recursivas y que \(D_{g_{1}}=D_{g_{2}}=D_{f_{1}}\cup D_{f_{2}}\), Además nótese que \[g_{1}(\vec{x},\vec{\alpha})=\left\{ \begin{array}{lll} f_{1}(\vec{x},\vec{\alpha}) & & \text{si }(\vec{x},\vec{\alpha})\in D_{f_{1}}\\ \varepsilon & & \text{caso contrario} \end{array}\right.\] \[g_{2}(\vec{x},\vec{\alpha})=\left\{ \begin{array}{lll} f_{2}(\vec{x},\vec{\alpha}) & & \text{si }(\vec{x},\vec{\alpha})\in D_{f_{2}}\\ \varepsilon & & \text{caso contrario} \end{array}\right.\] O sea que \(f_{1}\cup f_{2}=\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[g_{1},g_{2}\right]\) es \(\Sigma\)-recursiva.  

4.6.2 Conjuntos \(\Sigma\)-recursivos y \(\Sigma\)-recursivamente enumerables

A continuación probaremos los resultados básicos sobre conjuntos \(\Sigma\)-efectivamente computables y \(\Sigma\)-efectivamente enumerables, dados en el Capítulo Procedimientos Efectivos, pero enunciados dentro del paradigma de Godel.

Proof. Note que \[\begin{aligned} \lnot P & =\lambda xy\left[x\dot{-}y\right]\circ\left[C_{1}^{n,m},P\right]\\ (P\wedge Q) & =\lambda xy\left[x.y\right]\circ[P,Q]\\ (P\vee Q) & =\lnot(\lnot P\wedge\lnot Q). \end{aligned}\]  

Proof. Es directa del lema anterior.  

Proof. Podemos suponer que ni \(S_{1}\) ni \(S_{2}\) son vacíos ya que de lo contrario (1) y (2) se cumplen trivialmente. Además supondremos que \(n=2\) y \(m=1\).

(1). La idea de la prueba es la misma que la que usamos para probar que la unión de conjuntos \(\Sigma\)-efectivamente enumerables es \(\Sigma\)-efectivamente enumerable. Daremos usando macros un programa que enumera a \(S_{1}\cup S_{2}\) y luego aplicaremos la Caracterización de \(\Sigma\)-enumerabilidad. Por hipótesis hay funciones \(F:\omega\rightarrow\omega\times\omega\times\Sigma^{\ast}\) y \(G:\omega\rightarrow\omega\times\omega\times\Sigma^{\ast}\) tales que \(F_{(1)}\), \(F_{(2)}\), \(F_{(3)}\), \(G_{(1)}\), \(G_{(2)}\) y \(G_{(3)}\) son \(\Sigma\)-recursivas, \(\mathrm{Im}(F)=S_{1}\) y \(\mathrm{Im}(G)=S_{2}\). Ya que estas funciones también son \(\Sigma\)-computables, hay macros \[\begin{aligned} & \left[\mathrm{V}2\leftarrow F_{(1)}(\mathrm{V}1)\right]\\ & \left[\mathrm{V}2\leftarrow F_{(2)}(\mathrm{V}1)\right]\\ & \left[\mathrm{W}1\leftarrow F_{(3)}(\mathrm{V}1)\right]\\ & \left[\mathrm{V}2\leftarrow G_{(1)}(\mathrm{V}1)\right]\\ & \left[\mathrm{V}2\leftarrow G_{(2)}(\mathrm{V}1)\right]\\ & \left[\mathrm{W}1\leftarrow G_{(3)}(\mathrm{V}1)\right] \end{aligned}\] Ya que el predicado \(Par=\lambda x[x\) es par\(]\) es \(\Sigma\)-p.r., tenemos que hay un macro: \[[\mathrm{IF\ }Par(\mathrm{V}1)\ \mathrm{GOTO\ A}1]\] el cual escribiremos de la siguiente manera mas intuitiva \[[\mathrm{IF\ V}1\text{ es par }\mathrm{GOTO\ A}1]\] Ya que la función \(D=\lambda x[\lfloor x/2\rfloor]\) es \(\Sigma\)-p.r., tenemos que hay un macro: \[[\mathrm{V}2\leftarrow D(\mathrm{V}1)]\] el cual escribiremos de la siguiente manera mas intuitiva \[[\mathrm{V}2\leftarrow\lfloor\mathrm{V}1/2\rfloor]\] Sea \(\mathcal{P}\) el siguiente programa: \[\begin{array}{ll} & [\mathrm{IF\ N}1\text{ es par }\mathrm{GOTO\ L}1\\ & \mathrm{N}1\leftarrow\mathrm{N}1\dot{-}1\\ & [\mathrm{N}1111\leftarrow\lfloor\mathrm{N}1/2\rfloor]\\ & \left[\mathrm{N}1\leftarrow G_{(1)}(\mathrm{N}1111)\right]\\ & \left[\mathrm{N}2\leftarrow G_{(2)}(\mathrm{N}1111)\right]\\ & \left[\mathrm{P}1\leftarrow G_{(3)}(\mathrm{N}1111)\right]\\ & \mathrm{GOTO\ L}2\\ \mathrm{L}1 & [\mathrm{N}1111\leftarrow\lfloor\mathrm{N}1/2\rfloor]\\ & \left[\mathrm{N}1\leftarrow F_{(1)}(\mathrm{N}1111)\right]\\ & \left[\mathrm{N}2\leftarrow F_{(2)}(\mathrm{N}1111)\right]\\ & \left[\mathrm{P}1\leftarrow F_{(3)}(\mathrm{N}1111)\right]\\ \mathrm{L}2 & \mathrm{SKIP} \end{array}\] Es fácil ver que \(\mathcal{P}\) cumple (a) y (b) de (3) de la Caracterización de \(\Sigma\)-enumerabilidad por lo cual \(S_{1}\cup S_{2}\) es \(\Sigma\)-enumerable. Esto nos dice que \(S_{1}\cup S_{2}\) es \(\Sigma\)-r.e. ya que como vimos Godel vence a Neumann.

(2). Es dejada al lector  

Tal como veremos mas adelante hay conjuntos \(\Sigma\)-recursivamente enumerables los cuales no son \(\Sigma\)-recursivos. Sin embargo tenemos el siguiente interesante resultado.

Proof. (a)\(\Rightarrow\)(b). Si \(S=\emptyset\), por definición \(S\) es \(\Sigma\)-recursivamente enumerable. Supongamos entonces \(S\neq\emptyset\). Haremos el caso en el que \(n=m=1\) y \((0,\varepsilon)\in S\). Sea \(\leq\) un orden total sobre \(\Sigma\). Por hipótesis tenemos que \(\chi_{S}^{\omega\times\Sigma^{\ast}}\) es \(\Sigma\)-recursiva por lo cual hay un macro \[[\mathrm{IF\ }\chi_{S}^{\omega\times\Sigma^{\ast}}(\mathrm{V}1,\mathrm{W}1)\ \mathrm{GOTO\ A}1]\] Ya que la función \(f=\lambda x[(x)_{1}]\) es \(\Sigma\)-p.r. hay un macro \[[\mathrm{V}2\leftarrow f(\mathrm{V}1)]\] el cual escribiremos de la siguiente manera: \[[\mathrm{V}2\leftarrow(\mathrm{V}1)_{1}]\] Ya que la función \(g=\lambda x[\ast^{\leq}((x)_{2})]\) es \(\Sigma\)-p.r. hay un macro \[[\mathrm{W}1\leftarrow g(\mathrm{V}1)]\] el cual escribiremos de la siguiente manera: \[[\mathrm{W}1\leftarrow\ast^{\leq}((\mathrm{V}1)_{2})]\] (Dejamos al lector entender bien el funcionamiento de estos macros.) Sea \(\mathcal{P}\) el siguiente programa: \[\begin{array}{l} \mathrm{N}1\leftarrow\mathrm{N}1+1\\{} [\mathrm{N}2\leftarrow(\mathrm{N}1)_{1}]\\{} [\mathrm{P}2\leftarrow\ast^{\leq}(\mathrm{N}1)_{2}]\\{} [\mathrm{IF\ }\chi_{S}^{\omega\times\Sigma^{\ast}}(\mathrm{N}2,\mathrm{P}2)\ \mathrm{GOTO\ L}1\\ \mathrm{N}1\leftarrow0\\ \mathrm{P}1\leftarrow\varepsilon\\ \mathrm{GOTO\ L}2\\ \mathrm{L}1\ [\mathrm{N}1\leftarrow\mathrm{N}2]\\ \left[\mathrm{P}1\leftarrow\mathrm{P}2)\right]\\ \mathrm{L}2\ \mathrm{SKIP} \end{array}\] Nótese que \(\mathrm{Dom}(\left[\Psi_{\mathcal{P}}^{1,0,\#},\Psi_{\mathcal{P}}^{1,0,\ast}\right])=\omega\) y que \(\mathrm{Im}(\left[\Psi_{\mathcal{P}}^{1,0,\#},\Psi_{\mathcal{P}}^{1,0,\ast}\right])=S\) por lo cual \(S\) es \(\Sigma\)-enumerable lo que nos dice que \(S\) es \(\Sigma\)-recursivamente enumerable.

(b)\(\Rightarrow\)(a). Haremos el caso en que los conjuntos \(S\) y \((\omega^{n}\times\Sigma^{\ast m})-S\) son no vacíos. También supondremos \(n=m=1\). Por hipótesis hay funciones \(F:\omega\rightarrow\omega\times\Sigma^{\ast}\) y \(G:\omega\rightarrow\omega\times\Sigma^{\ast}\) tales que \(F_{(1)}\), \(F_{(2)}\), \(G_{(1)}\) y \(G_{(2)}\) son \(\Sigma\)-recursivas, \(\mathrm{Im}(F)=S\) y \(\mathrm{Im}(G)=(\omega\times\Sigma^{\ast})-S\). Hay macros \[\begin{aligned} & \left[\mathrm{V}2\leftarrow F_{(1)}(\mathrm{V}1)\right]\\ & \left[\mathrm{W}1\leftarrow F_{(2)}(\mathrm{V}1)\right]\\ & \left[\mathrm{V}1\leftarrow G_{(1)}(\mathrm{V}1)\right]\\ & \left[\mathrm{W}1\leftarrow G_{(2)}(\mathrm{V}1)\right] \end{aligned}\] Ya que los predicados \(D=\lambda xy[x\neq y]\) y \(D^{\prime}=\lambda\alpha\beta[\alpha\neq\beta]\) son \(\Sigma\)-p.r. hay macros \[\begin{aligned} & \left[\mathrm{IF}\;D(\mathrm{V}1,\mathrm{V}2)\;\mathrm{GOTO}\;\mathrm{A}1\right]\\ & \left[\mathrm{IF}\;D^{\prime}(\mathrm{W}1,\mathrm{W}2)\;\mathrm{GOTO}\;\mathrm{A}1\right] \end{aligned}\] los cuales para hacer mas amigable la lectura los escribiremos de la siguiente manera \[\begin{aligned} & \left[\mathrm{IF}\;\mathrm{V}1\neq\mathrm{V}2\;\mathrm{GOTO}\;\mathrm{A}1\right]\\ & \left[\mathrm{IF}\;\mathrm{W}1\neq\mathrm{W}2\;\mathrm{GOTO}\;\mathrm{A}1\right] \end{aligned}\] También usaremos el macro \[[\mathrm{V}1\leftarrow C_{1}^{0,0}(\lozenge)]\] (asociado a la función \(\Sigma\)-p.r. \(C_{1}^{0,0}\)), el cual escribiremos de la siguiente manera \[[\mathrm{V}1\leftarrow1]\] Sea \(\mathcal{P}\) el siguiente programa: \[\begin{array}{l} \mathrm{L}1\ [\mathrm{N}2\leftarrow F_{(1)}(\mathrm{N}20)]\\{} [\mathrm{P}2\leftarrow F_{(2)}(\mathrm{N}20)]\\ \left[\mathrm{IF}\;\mathrm{N}2\neq\mathrm{N}1\;\mathrm{GOTO}\;\mathrm{L}2\right]\\ \left[\mathrm{IF}\;\mathrm{P}2\neq\mathrm{P}1\;\mathrm{GOTO}\;\mathrm{L}2\right]\\{} [\mathrm{N}1\leftarrow1]\\ \mathrm{GOTO}\;\mathrm{L}3\\ \mathrm{L}2\ [\mathrm{N}2\leftarrow G_{(1)}(\mathrm{N}20)]\\{} [\mathrm{P}2\leftarrow G_{(2)}(\mathrm{N}20)]\\ \left[\mathrm{IF}\;\mathrm{N}2\neq\mathrm{N}1\;\mathrm{GOTO}\;\mathrm{L}4\right]\\ \left[\mathrm{IF}\;\mathrm{P}2\neq\mathrm{P}1\;\mathrm{GOTO}\;\mathrm{L}4\right]\\ \mathrm{N}1\leftarrow0\\ \mathrm{GOTO}\;\mathrm{L}3\\ \mathrm{L}4\ \mathrm{N}20\leftarrow\mathrm{N}20+1\\ \mathrm{GOTO}\;\mathrm{L}1\\ \mathrm{L}3\ \mathrm{SKIP} \end{array}\] Nótese que \(\mathcal{P}\) computa a la función \(\chi_{S}^{\omega\times\Sigma^{\ast}}\) por lo cual \(\chi_{S}^{\omega\times\Sigma^{\ast}}\) es \(\Sigma\)-computable lo que nos dice que es \(\Sigma\)-recursiva. Esto por definición nos dice que \(S\) es \(\Sigma\)-recursivo  

Proof. Si \(S=\emptyset\), entonces \(f|_{S}=\emptyset\) y por lo tanto \(f|_{S}\) es \(\Sigma\)-recursiva. Supongamos \(S\neq\emptyset\). Haremos el caso \(n=m=1\) y \(O=\Sigma^{\ast}\). Tenemos que hay una \(F:\omega\rightarrow\omega\times\Sigma^{\ast}\) tal que \(\mathrm{Im}F=S\) y \(F_{(1)}\), \(F_{(2)}\) son \(\Sigma\)-recursivas. Ya que \(f\), \(F_{(1)}\) y \(F_{(2)}\) son \(\Sigma\)-recursivas, hay macros \[\begin{aligned} & \left[\mathrm{W}2\leftarrow f(\mathrm{V}1,\mathrm{W}1)\right]\\ & \left[\mathrm{V}2\leftarrow F_{(1)}(\mathrm{V}1)\right]\\ & \left[\mathrm{W}1\leftarrow F_{(2)}(\mathrm{V}1)\right] \end{aligned}\] Usaremos los macros \[\begin{aligned} & \left[\mathrm{IF}\;\mathrm{V}1\neq\mathrm{V}2\;\mathrm{GOTO}\;\mathrm{A}1\right]\\ & \left[\mathrm{IF}\;\mathrm{W}1\neq\mathrm{W}2\;\mathrm{GOTO}\;\mathrm{A}1\right] \end{aligned}\] Sea \(\mathcal{P}\) el siguiente programa \[\begin{array}{ll} \mathrm{L}2 & [\mathrm{N}2\leftarrow F_{(1)}(\mathrm{N}20)]\\ & [\mathrm{P}2\leftarrow F_{(2)}(\mathrm{N}20)]\\ & \left[\mathrm{IF}\;\mathrm{N}1\neq\mathrm{N}2\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ & \left[\mathrm{IF}\;\mathrm{P}1\neq\mathrm{P}2\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ & \left[\mathrm{P}1\leftarrow f(\mathrm{N}1,\mathrm{P}1)\right]\\ & \mathrm{GOTO}\;\mathrm{L}3\\ \mathrm{L}1 & \mathrm{N}20\leftarrow\mathrm{N}20+1\\ & \mathrm{GOTO}\;\mathrm{L}2\\ \mathrm{L}3 & \mathrm{SKIP} \end{array}\] Es fácil ver que \(\mathcal{P}\) computa a \(f|_{S}\)  

Ahora probaremos el análogo recursivo del Teorema 3.2.

Proof. El caso \(n=m=0\) es fácil y es dejado al lector. Supongamos entonces que \(n+m\geq1\).

(2)\(\Rightarrow\)(3). Haremos el caso \(k=l=1\) y \(n=m=2\). El caso general es completamente análogo. Nótese que entonces tenemos que \(S\subseteq\omega^{2}\times\Sigma^{\ast2}\) y \(F:D_{F}\subseteq\omega\times\Sigma^{\ast}\rightarrow\omega^{2}\times\Sigma^{\ast2}\) es tal que \(\mathrm{Im}F=S\) y \(F_{(1)}\), \(F_{(2)}\), \(F_{(3)}\), \(F_{(4)}\) son \(\Sigma\)-recursivas. Para cada \(i\in\{1,2,3,4\}\), sea \(\mathcal{P}_{i}\) un programa el cual computa a \(F_{(i)}\). Sea \(\leq\) un orden total sobre \(\Sigma\). Definamos \[H_{i}=\lambda tx_{1}\alpha_{1}\left[\lnot Halt^{1,1}(t,x_{1},\alpha_{1},\mathcal{P}_{i})\right]\] Notar que \(D_{H_{i}}=\omega^{2}\times\Sigma^{\ast}\) y que \(H_{i}\) es \(\Sigma\)-mixta. Además sabemos que la función \(Halt^{1,1}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. por lo cual resulta fácilmente que \(H_{i}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Por Independencia del Alfabeto tenemos que \(H_{i}\) es \(\Sigma\)-p.r., por lo cual el Segundo Manantial de Macros nos dice que hay un macro: \[\left[\mathrm{IF}\;H_{i}(\mathrm{V}2,\mathrm{V}1,\mathrm{W}1)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Para hacer mas intuitivo el uso de este macro lo escribiremos de la siguiente manera \[\left[\mathrm{IF}\;\lnot Halt^{1,1}(\mathrm{V}2,\mathrm{V}1,\mathrm{W}1,\mathcal{P}_{i})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Para \(i=1,2\), definamos \[E_{i}=\lambda xtx_{1}\alpha_{1}\left[x\neq E_{\#1}^{1,1}(t,x_{1},\alpha_{1},\mathcal{P}_{i})\right]\] Para \(i=3,4\), definamos \[E_{i}=\lambda tx_{1}\alpha_{1}\alpha\left[\alpha\neq E_{\ast1}^{1,1}(t,x_{1},\alpha_{1},\mathcal{P}_{i})\right]\] Dejamos al lector probar que las funciones \(E_{i}\) son \(\Sigma\)-p.r.. O sea que para cada \(i\in\{1,2\}\) hay un macro \[\left[\mathrm{IF}\;E_{i}(\mathrm{V}2,\mathrm{V}3,\mathrm{V}1,\mathrm{W}1)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] y para cada \(i\in\{3,4\}\) hay un macro \[\left[\mathrm{IF}\;E_{i}(\mathrm{V}2,\mathrm{V}1,\mathrm{W}1,\mathrm{W}2)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Haremos mas intuitiva la forma de escribir estos macros, por ejemplo para \(i=1\), lo escribiremos de la siguiente manera \[\left[\mathrm{IF}\;\mathrm{V}2\neq E_{\#1}^{1,1}(\mathrm{V}3,\mathrm{V}1,\mathrm{W}1,\mathcal{P}_{1})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Ya que la función \(f=\lambda x[(x)_{1}]\) es \(\Sigma\)-p.r., hay un macro \[[\mathrm{V}2\leftarrow f(\mathrm{V}1)]\] el cual escribiremos de la siguiente manera: \[[\mathrm{V}2\leftarrow(\mathrm{V}1)_{1}]\] Similarmente hay macros: \[[\mathrm{W}1\leftarrow\ast^{\leq}(\mathrm{V}1)_{3}]\] \[[\mathrm{V}2\leftarrow(\mathrm{V}1)_{2}]\] (dejamos al lector entender bien el funcionamiento de estos macros). Sea \(\mathcal{P}\) el siguiente programa de \(\mathcal{S}^{\Sigma}\): \[\begin{array}{l} \mathrm{L}1\ \mathrm{N}20\leftarrow\mathrm{N}20+1\\{} [\mathrm{N}10\leftarrow(\mathrm{N}20)_{1}]\\{} [\mathrm{N}3\leftarrow(\mathrm{N}20)_{2}]\\{} [\mathrm{P}3\leftarrow\ast^{\leq}(\mathrm{N}20)_{3}]\\ \left[\mathrm{IF}\;\lnot Halt^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{1})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ \left[\mathrm{IF}\;\lnot Halt^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{2})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ \left[\mathrm{IF}\;\lnot Halt^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{3})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ \left[\mathrm{IF}\;\lnot Halt^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{4})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ \left[\mathrm{IF}\;\mathrm{N}1\neq E_{\#1}^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{1})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ \left[\mathrm{IF}\;\mathrm{N}2\neq E_{\#1}^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{2})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ \left[\mathrm{IF}\;\mathrm{P}1\neq E_{\ast1}^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{3})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ \left[\mathrm{IF}\;\mathrm{P}2\neq E_{\ast1}^{1,1}(\mathrm{N}10,\mathrm{N}3,\mathrm{P}3,\mathcal{P}_{4})\;\mathrm{GOTO}\;\mathrm{L}1\right] \end{array}\] Dejamos al lector la tarea de comprender el funcionamiento de este programa y convencerse de que computa la función \(p_{1}^{2,2}|_{S}\). Pero entonces \(p_{1}^{2,2}|_{S}\) es \(\Sigma\)-computable por lo cual es \(\Sigma\)-recursiva, lo cual prueba (3) ya que \(\mathrm{Dom}(p_{1}^{2,2}|_{S})=S\).

(3)\(\Rightarrow\)(4). Supongamos \(S\neq\emptyset\). Sea \((z_{1},...,z_{n},\gamma_{1},...,\gamma_{m})\in S\) fijo. Sea \(\mathcal{P}\) un programa el cual compute a \(f\) y Sea \(\leq\) un orden total sobre \(\Sigma\). Sea \(P:\mathbf{N}\rightarrow\omega\) dado por \(P(x)=1\) sii \[Halt^{n,m}\left((x)_{n+m+1},(x)_{1},...,(x)_{n},\ast^{\leq}((x)_{n+1}),...,\ast^{\leq}((x)_{n+m})),\mathcal{P}\right)=1\] Es fácil ver que \(P\) es \((\Sigma\cup\Sigma_{p})\)-p.r. por lo cual es \(\Sigma\)-p.r.. Sea \(\bar{P}=P\cup C_{0}^{1,0}|_{\{0\}}\). Para \(i=1,...,n\), definamos \(F_{i}:\omega\rightarrow\omega\) de la siguiente manera \[F_{i}(x)=\left\{ \begin{array}{ccc} (x)_{i} & \text{si} & \bar{P}(x)=1\\ z_{i} & \text{si} & \bar{P}(x)\neq1 \end{array}\right.\] Para \(i=n+1,...,n+m\), definamos \(F_{i}:\omega\rightarrow\Sigma^{\ast}\) de la siguiente manera \[F_{i}(x)=\left\{ \begin{array}{lll} \ast^{\leq}((x)_{i}) & \text{si} & \bar{P}(x)=1\\ \gamma_{i-n} & \text{si} & \bar{P}(x)\neq1 \end{array}\right.\] Por el Lema de División por Casos, cada \(F_{i}\) es \(\Sigma\)-p.r.. Es fácil ver que \(F=[F_{1},...,F_{n+m}]\) cumple (4).  

La prueba de (2)\(\Rightarrow\)(3) del teorema anterior es de naturaleza imperativa ya que da explícitamente un programa (de todas maneras usa el paradigma recursivo o Godeliano para justificar la existencia de los macros). A continuación daremos una prueba de (2)\(\Rightarrow\)(3) la cual es mas recursiva (aunque aun usa el paradigma imperativo en la existencia de los programas \(\mathcal{P}_{i}\)).

Proof. (De (2)\(\Rightarrow\)(3)). Para \(i=1,...,n+m\), sea \(\mathcal{P}_{i}\) un programa el cual computa a \(F_{(i)}\) y Sea \(\leq\) un orden total sobre \(\Sigma\). Sea \(P:\mathbf{N}\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) dado por \(P(t,\vec{x},\vec{\alpha})=1\) sii se cumplen las siguientes condiciones \[\begin{aligned} Halt^{k,l}(\left((t)_{k+l+1},(t)_{1},...,(t)_{k},\ast^{\leq}((t)_{k+1}),...,\ast^{\leq}((t)_{k+l})),\mathcal{P}_{1}\right) & =1\\ & \vdots\\ Halt^{k,l}\left((t)_{k+l+1},(t)_{1}...(t)_{k},\ast^{\leq}((t)_{k+1})...\ast^{\leq}((t)_{k+l})),\mathcal{P}_{n+m}\right) & =1\\ E_{\#1}^{k,l}((t)_{k+l+1},(t)_{1},...,(t)_{k},\ast^{\leq}((t)_{k+1}),...,\ast^{\leq}((t)_{k+l})),\mathcal{P}_{1}) & =x_{1}\\ & \vdots\\ E_{\#1}^{k,l}((t)_{k+l+1},(t)_{1},...,(t)_{k},\ast^{\leq}((t)_{k+1}),...,\ast^{\leq}((t)_{k+l})),\mathcal{P}_{n}) & =x_{n}\\ E_{\ast1}^{k,l}((t)_{k+l+1},(t)_{1},...,(t)_{k},\ast^{\leq}((t)_{k+1}),...,\ast^{\leq}((t)_{k+l})),\mathcal{P}_{n+1}) & =\alpha_{1}\\ & \vdots\\ E_{\ast1}^{k,l}((t)_{k+l+1},(t)_{1},...,(t)_{k},\ast^{\leq}((t)_{k+1}),...,\ast^{\leq}((t)_{k+l})),\mathcal{P}_{n+m}) & =\alpha_{m} \end{aligned}\] Note que \(P\) es \((\Sigma\cup\Sigma_{p})\)-p.r. y por lo tanto \(P\) es \(\Sigma\)-p.r.. Pero entonces \(M(P)\) es \(\Sigma\)-r. lo cual nos dice que se cumple (3) ya que \(D_{M(P)}=I_{F}=S\).  

Proof. Por el teorema anterior \(S=D_{g}\), para alguna función \(\Sigma\)-recursiva \(g\). Note que \(f^{-1}(S)=D_{g\circ f}\), lo cual nuevamente por el teorema anterior nos dice que \(f^{-1}(S)\) es \(\Sigma\)-r.e..  

Dejamos como ejercicio dar una prueba imperativa del corolario anterior. Los Lemas 4.63 y 4.62 pueden obtenerse fácilmente como corolarios del teorema anterior. Se gana en elegancia y simplicidad pero cabe destacar que se pierde en intuición.

Proof. Supongamos \(O=\Sigma^{\ast}\). Por el teorema anterior \(S=D_{g}\), para alguna función \(\Sigma\)-recursiva \(g\). Nótese que componiendo adecuadamente podemos suponer que \(I_{g}=\{\varepsilon\}.\) O sea que tenemos \(f|_{S}=\lambda\alpha\beta\left[\alpha\beta\right]\circ[f,g]\).  

Proof. Por el teorema anterior \(S_{i}=D_{g_{i}}\), con \(g_{1},g_{2}\) funciones \(\Sigma\)-recursivas\(.\) Nótese que podemos suponer que \(I_{g_{1}},I_{g_{2}}\subseteq\omega\) por lo que \(S_{1}\cap S_{2}=D_{\lambda xy\left[xy\right]\circ[g_{1},g_{2}]}\) es \(\Sigma\)-r.e.\(.\)  

Proof. Supongamos \(S_{1}\neq\emptyset\neq S_{2}.\) Sean \(F,G:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tales que \(I_{F}=S_{1}\), \(I_{G}=S_{2}\) y las funciones \(F_{(i)}\) y \(G_{(i)}\) son \(\Sigma\)-recursivas. Sean \(f=\lambda x\left[Q(x,2)\right]\) y \(g=\lambda x\left[Q(x\dot{-}1,2)\right].\) Sea \(H:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) dada por \[H_{(i)}=(F_{(i)}\circ f)\mathrm{|}_{\{x:x\mathrm{\ es\ par}\}}\cup(G_{(i)}\circ g)\mathrm{|}_{\{x:x\mathrm{\ es\ impar}\}}\] Por el Lema 4.63 y el Lema 4.59, cada \(H_{i}\) es \(\Sigma\)-recursiva. Ya que \(I_{H}=S_{1}\cup S_{2}\), tenemos que \(S_{1}\cup S_{2}\) es \(\Sigma\)-r.e.  

A continuación dejamos un sketch de una prueba alternativa del Teorema 4.11. Dejamos al lector completar los detalles. Proof. (a)\(\Rightarrow\)(b)\(.\) Note que \(S=D_{Pred\circ\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}}.\)  

(b)\(\Rightarrow\)(a). Note que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}=C_{1}^{n,m}\)\(|\)\(_{S}\cup C_{0}^{n,m}\)\(|\)\(_{(\omega^{n}\times\Sigma^{\ast m})-S}\).

Los dos siguientes teoremas, nos agregan una equivalencia mas al Teorema 4.12, para el caso \(n=0\), \(m=1\).

Proof. La prueba es similar a la del Teorema 4.7 asique solo daremos un skech de la misma. Por el Teorema 4.12 \(L=D_{f}\) para alguna función \(f\) la cual es \(\Sigma\)-recursiva. Nótese que podemos suponer que \(\mathrm{Im}f\subseteq\Sigma^{\ast}\). Ya que \(f\) es \(\Sigma\)-recursiva, también es \(\Sigma\)-computable. Por el Lema 4.58 existe \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) el cual computa \(f\) y tiene las propiedades (1) y (2). Sea \(k=N(\mathcal{P})\) y sea \(M_{sim}\) la máquina de Turing con unit que simula a \(\mathcal{P}\) respecto de \(k\). Sea \(M_{1}\) una máquina de Turing con un solo estado final \(q_{f}\) (del cual no salen flechas) y tal que para todo \(\alpha\in\Sigma^{\ast}\), \[\left\lfloor q_{0}B\alpha\right\rfloor \overset{\ast}{\vdash}\left\lfloor q_{f}B^{k+1}\alpha\right\rfloor\] Note que la concatenación de \(M_{1}\) con \(M\) produce una máquina de Turing \(M_{2}\) tal que \(H(M_{2})=L(M_{2})=L\). Dejamos al lector los detalles de la construcción de \(M_{2}.\)  

Proof. Veamos que \(L(M)\) es \(\Sigma\)-recursivamente enumerable. Sea \(P\) el siguiente predicado \((\Gamma\cup Q)\)-mixto \[\lambda n\alpha\left[(\exists d\in Des)\;\left\lfloor q_{0}B\alpha\right\rfloor \underset{M}{\overset{n}{\vdash}}d\wedge St(d)\in F\right]\] Nótese que \(D_{P}=\omega\times\Gamma^{\ast}\). Dejamos al lector probar que \(P\) es \((\Gamma\cup Q)\)-p.r.. Sea \(P^{\prime}=P|_{\omega\times\Sigma^{\ast}}\). Nótese que \(P^{\prime}(n,\alpha)=1\) sii \(\alpha\in L(M)\) atestiguado por una computación de longitud \(n\). Ya que \(P^{\prime}\) es \((\Gamma\cup Q)\)-p.r. (por que?) y además es \(\Sigma\)-mixto, el Teorema 4.2 nos dice que \(P^{\prime}\) es \(\Sigma\)-p.r.. Ya que \(L(M)=D_{M(P^{\prime})}\), el Teorema 4.12 nos dice que \(L(M)\) es \(\Sigma\)-r.e..  

Dejamos al lector la prueba parecida de que \(H(M)\) es \(\Sigma\)-recursivamente enumerable.

4.6.3 El halting problem y los conjuntos \(A\) y \(N\)

Cuando \(\Sigma\supseteq\Sigma_{p}\), podemos definir \[AutoHalt^{\Sigma}=\lambda\mathcal{P}\left[(\exists t\in\omega)\;Halt^{0,1}(t,\mathcal{P},\mathcal{P})\right]\text{.}\] Notar que el dominio de \(AutoHalt^{\Sigma}\) es \(\mathrm{Pro}^{\Sigma}\) y que para cada \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) tenemos que

1. adhocprefix(*)adhocsufix \(AutoHalt^{\Sigma}(\mathcal{P})=1\) sii \(\mathcal{P}\) se detiene partiendo del estado \(\left\Vert \mathcal{P}\right\Vert\).

Proof. Supongamos \(AutoHalt^{\Sigma}\) es \(\Sigma\)-recursivo. Por el Segundo Manantial de Macros tenemos que hay un macro \[\left[\mathrm{IF}\;AutoHalt^{\Sigma}(\mathrm{W}1)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Sea \(\mathcal{P}_{0}\) el siguiente programa de \(\mathcal{S}^{\Sigma}\) \[\mathrm{L}1\;\left[\mathrm{IF}\;AutoHalt^{\Sigma}(\mathrm{P}1)\;\mathrm{GOTO}\;\mathrm{L}1\right]\] Note que

1. adhocprefix-adhocsufix \(\mathcal{P}_{0}\) termina partiendo desde \(\left\Vert \mathcal{P}_{0}\right\Vert\) sii \(AutoHalt^{\Sigma}(\mathcal{P}_{0})=0\),

lo cual produce una contradicción si tomamos en (*) \(\mathcal{P}=\mathcal{P}_{0}\).  

Usando el lema anterior y la Tesis de Church podemos probar el siguiente impactante resultado.

Proof. Si \(AutoHalt^{\Sigma}\) fuera \(\Sigma\)-efectivamente computable, la Tesis de Church nos diría que es \(\Sigma\)-recursivo, contradiciendo el lema anterior.  

Nótese que \(AutoHalt^{\Sigma}\) provee de un ejemplo natural en el cual la cuantificación (no acotada) de un predicado \(\Sigma\)-p.r. con dominio rectangular no es \(\Sigma\)-efectivamente computable

Ahora estamos en condiciones de dar un ejemplo natural de un conjunto \(A\) que es \(\Sigma\)-recursivamente enumerable pero el cual no es \(\Sigma\)-recursivo.

Proof. Para ver que \(A\) es \(\Sigma\)-r.e. se lo puede hacer imperativamente dando un programa (usando macros) que enumere a \(A\). De esta forma probaríamos que \(A\) es \(\Sigma\)-enumerable y por lo tanto es \(\Sigma\)-r.e.. Daremos ahora una prueba no imperativa de este hecho, es decir mas propia del paradigma funcional. Sea \(P=\lambda t\mathcal{P}\left[Halt^{0,1}(t,\mathcal{P},\mathcal{P})\right]\). Note que \(P\) es \(\Sigma\)-p.r. por lo que \(M(P)\) es \(\Sigma\)-r.. Además note que \(D_{M(P)}=A\), lo cual implica que \(A\) es \(\Sigma\)-r.e..

Supongamos ahora que \(N\) es \(\Sigma\)-r.e.. Entonces la función \(C_{0}^{0,1}|_{N}\) es \(\Sigma\)-recursiva ya que \(C_{0}^{0,1}\) lo es. Además ya que \(A\) es \(\Sigma\)-r.e. tenemos que \(C_{1}^{0,1}|_{A}\) es \(\Sigma\)-recursiva. Ya que \[AutoHalt^{\Sigma}=C_{1}^{0,1}|_{A}\cup C_{0}^{0,1}|_{N}\] el Lema 4.59 nos dice que \(AutoHalt^{\Sigma}\) es \(\Sigma\)-recursivo, contradiciendo el Lema 4.64. Esto prueba que \(N\) no es \(\Sigma\)-r.e..

Finalmente supongamos \(A\) es \(\Sigma\)-recursivo. Entonces el conjunto \[N=\left(\Sigma^{\ast}-A\right)\cap\mathrm{Pro}^{\Sigma}\] debería serlo, lo cual es absurdo. Hemos probado entonces que \(A\) no es \(\Sigma\)-recursivo.  

Cabe destacar aquí que el dominio de una función \(\Sigma\)-recursiva no siempre será un conjunto \(\Sigma\)-recursivo. Por ejemplo si tomamos \(\Sigma\) tal que \(\Sigma\supseteq\Sigma_{p}\), entonces \(C_{1}^{0,1}|_{A}\) es una función \(\Sigma\)-recursiva ya que es la restricción de la función \(\Sigma\)-recursiva \(C_{1}^{0,1}\) al conjunto \(\Sigma\)-r.e. \(A\), pero \(\mathrm{Dom}(C_{1}^{0,1}|_{A})=A\) no es \(\Sigma\)-recursivo.

Usando la Tesis de Church obtenemos el siguiente resultado.

Con los resultados anteriores estamos en condiciones de dar un ejemplo de un predicado \(\Sigma\)-recursivo, cuya minimización no es \(\Sigma\)-efectivamente computable (y por lo tanto es no \(\Sigma\)-recursiva).

Proof. Nótese que \(D_{M(P)}=\mathrm{Pro}^{\Sigma}\) y que para cada \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) se tiene que \[M(P)(\mathcal{P})=0\text{ sii }\mathcal{P}\in A\] O sea que \(AutoHalt^{\Sigma}=\lambda x[x=0]\circ M(P)\) lo cual nos dice que \(M(P)\) no es \(\Sigma\)-recursiva ya que si lo fuese lo seria también \(AutoHalt^{\Sigma}\). Por la Tesis de Church \(M(P)\) tampoco es \(\Sigma\)-efectivamente computable  

Supongamos \(\Sigma\supseteq\Sigma_{p}\). Sea \(f=\lambda\mathcal{P}\left[T^{0,1}(\mathcal{P},\mathcal{P})\right]\). Note que \(D_{f}=A\) y \(f(\mathcal{P})\) es la cantidad de pasos en la que \(\mathcal{P}\) se detiene partiendo de \(\left\Vert \mathcal{P}\right\Vert\).

Proof. Supongamos hay una tal \(F\). Nótese que \(AutoHalt^{\Sigma}=\lambda\mathcal{P}\left[Halt^{0,1}(F(\mathcal{P}),\mathcal{P},\mathcal{P})\right]\) lo cual nos dice que \(AutoHalt^{\Sigma}\) es \(\Sigma\)-recursiva, llegando a una contradicción.