4.6 Resultados basicos presentados en paradigma recursivo

En esta seccion presentaremos varios de los resultados basicos de computabilidad, expresados en el paradigma recursivo, ya que es el mas habitual y comodo. Varios de estos resultados ya han sido establecidos dentro del desarrollo de la computabilidad efectiva en el Capitulo [ParadigmaFilosofico]. A estos resultados los enunciaremos dentro del paradigma de Godel y daremos pruebas rigurosas matematicas de ellos usando la teoria desarrollada hasta ahora. Sin envargo, veremos que hay otros resultados que son dependientes del desarrollo matematico hecho y aportan nueva informacion al paradigma filosofico (la indecidibilidad del halting problem, por ejemplo).

4.6.1 Lema de division por casos para funciones \(\Sigma\)-recursivas

Proof. Probaremos el caso \(k=2\) y \(O=\Sigma^{\ast}\). Ademas 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. Ademas sabemos que la funcion \(Halt^{1,1}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. por lo cual resulta facilmente que \(H_{i}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Por el Teorema de Independencia del Alfabeto tenemos que \(H_{i}\) es \(\Sigma\)-p.r.. Entonces \(H_{i}\) es \(\Sigma\)-computable por lo cual tenemos que 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, 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}\] Notese que \(\mathcal{P}\) computa la funcion \(f_{1}\cup f_{2}\)  

La prueba del lema anterior es de naturaleza imperativa ya que da explicitamente un programa (de todas maneras usa el paradigma recursivo o Godeliano para justificar la existencia de los macros). A continuacion 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}\] Notese 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.. Tambien notese 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}\] Notese que \(g_{1}\) y \(g_{2}\) son \(\Sigma\)-recursivas y que \(D_{g_{1}}=D_{g_{2}}=D_{f_{1}}\cup D_{f_{2}}\), Ademas notese 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 continuacion probaremos los resultados basicos sobre conjuntos \(\Sigma\)-efectivamente computables y \(\Sigma\)-efectivamente enumerables, dados en las Secciones [definicion de conjunto sigma-efectivamente enumerable] y [definicion de conjunto sigma-efectivamente computable], 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 vacios ya que de lo contrario los resultados son triviales. Ademas supondremos que \(n=2\) y \(m=1\).  

(1). La idea de la prueba es la misma que la que usamos para probar que la union 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 Proposicion 4.10. Por hipotesis 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, \(\operatorname{Im}(F)=S_{1}\) y \(\operatorname{Im}(G)=S_{2}\). Ya que estas funciones tambien 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 \(Par\) es \(\Sigma\)-computable. Es decir 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 funcion \(D=\lambda x[\lfloor x/2\rfloor]\) es \(\Sigma\)-p.r., tenemos que \(D\) es \(\Sigma\)-computable. Es decir 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 facil ver que \(\mathcal{P}\) cumple a y b de (3) de la Proposicion 4.10 por lo cual \(S_{1}\cup S_{2}\) es \(\Sigma\)-enumerable.

(2). Es dejada al lector

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

Proof. (a)\(\Rightarrow\)(b). Si \(S=\emptyset\), por definicion \(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 hipotesis tenemos que \(\chi_{S}^{\omega\times\Sigma^{\ast}}\) es \(\Sigma\)-recursiva por lo cual es \(\Sigma\)-computable. O sea que tenemos un macro \[[\mathrm{IF\ }\chi_{S}^{\omega\times\Sigma^{\ast}}(\mathrm{V}1,\mathrm{W}1)\ \mathrm{GOTO\ A}1]\] Ya que la funcion \(f=\lambda x[(x)_{1}]\) es \(\Sigma\)-p.r., ella es \(\Sigma\)-computable por lo cual 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 funcion \(g=\lambda x[\ast^{\leq}((x)_{2})]\) es \(\Sigma\)-p.r., ella es \(\Sigma\)-computable por lo cual 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}\] Notese que \(\mathrm{Dom}(\left[\Psi_{\mathcal{P}}^{1,0,\#},\Psi_{\mathcal{P}}^{1,0,\ast}\right])=\omega\) y que \(\operatorname{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 vacios. Tambien supondremos \(n=m=1\). Por hipotesis 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, \(\operatorname{Im}(F)=S\) y \(\operatorname{Im}(G)=(\omega\times\Sigma^{\ast})-S\). Ya que estas funciones tambien son \(\Sigma\)-computables, 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\)-computables, 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 escribieremos 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}\] Tambien usaremos el macro \[[\mathrm{V}1\leftarrow C_{1}^{0,0}(\Diamond)]\] (asociado a la funcion \(\Sigma\)-computable \(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}\] Notese que \(\mathcal{P}\) computa a la funcion \(\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 definicion 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 \(\operatorname{Im}F=S\) y \(F_{(1)}\), \(F_{(2)}\) son \(\Sigma\)-recursivas. Ya que \(f\), \(F_{(1)}\) y \(F_{(2)}\) son \(\Sigma\)-computables, 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 facil ver que \(\mathcal{P}\) computa a \(f|_{S}\)  

Ahora probaremos el analogo recursivo del Teorema 3.2.

Proof. El caso \(n=m=0\) es facil 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 analogo. Notese 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 \(\operatorname{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. Ademas sabemos que la funcion \(Halt^{1,1}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. por lo cual resulta facilmente que \(H_{i}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Por la Proposicion de Independencia del Alfabeto tenemos que \(H_{i}\) es \(\Sigma\)-p.r.. Entonces \(H_{i}\) es \(\Sigma\)-computable por lo cual tenemos 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 son \(\Sigma\)-computables por lo cual 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 funcion \(f=\lambda x[(x)_{1}]\) es \(\Sigma\)-p.r., ella es \(\Sigma\)-computable por lo cual 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 convenserse de que computa la funcion \(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 facil 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 division por casos, cada \(F_{i}\) es \(\Sigma\)-p.r.. Es facil 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 explicitamente un programa (de todas maneras usa el paradigma recursivo o Godeliano para justificar la existencia de los macros). A continuacion 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. [(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 funcion \(\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.59 y 4.58 pueden obtenerse facilmente como corolarios del teorema anterior. Se gana en elegancia y simplicidad pero cabe destacar que se pierde en intuicion

Proof. Supongamos \(O=\Sigma^{\ast}\). Por el teorema anterior \(S=D_{g}\), para alguna funcion \(\Sigma\)-recursiva \(g\). Notese 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\(.\) Notese 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)}%TCIMACRO{\U{b4}}%%BeginExpansion\acute{}%EndExpansions\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\) y \(G_{(i)}%TCIMACRO{\U{b4}}%%BeginExpansion\acute{}%EndExpansions\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\ensuremath{}\) 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.59 y el Lema 4.55, 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 continuacion 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 funcion \(f\) la cual es \(\Sigma\)-recursiva. Notese que podemos suponer que \(\operatorname{Im}f\subseteq\Sigma^{\ast}\). Ya que \(f\) es \(\Sigma\)-recursiva, tambien es \(\Sigma\)-computable. Por el Lema 4.54 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 maquina de Turing con unit que simula a \(\mathcal{P}\) respecto de \(k\). Sea \(M_{1}\) una maquina 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 concatenacion de \(M_{1}\) con \(M\) produce una maquina de Turing \(M_{2}\) tal que \(H(M_{2})=L(M_{2})=L\). Dejamos al lector los detalles de la construccion 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]\] Notese 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}}\). Notese que \(P^{\prime}(n,\alpha)=1\) sii \(\alpha\in L(M)\) atestiguado por una computacion de longitud \(n\). Ya que \(P^{\prime}\) es \((\Gamma\cup Q)\)-p.r. (por que?) y ademas 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(\mathcal{P})=1\) sii \(\mathcal{P}\) se detiene partiendo del estado \(\left\Vert \mathcal{P}\right\Vert\).

Proof. Supongamos \(AutoHalt^{\Sigma}\) es \(\Sigma\)-recursivo y por lo tanto \(\Sigma\)-computable. Por la proposicion de existencia 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 contradiccion 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 diria que es \(\Sigma\)-recursivo, contradiciendo el lema anterior.  

Notese que \(AutoHalt^{\Sigma}\) provee de un ejemplo natural en el cual la cuantificacion (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 probariamos 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.. Ademas 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 funcion \(C_{0}^{0,1}|_{N}\) es \(\Sigma\)-recursiva ya que \(C_{0}^{0,1}\) lo es. Ademas 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.55 nos dice que \(AutoHalt^{\Sigma}\) es \(\Sigma\)-recursivo, contradiciendo el Lema 4.60. 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}\] deberia serlo, lo cual es absurdo. Hemos probado entonces que \(A\) no es \(\Sigma\)-recursivo.  

Cabe destacar aqui que el dominio de una funcion \(\Sigma\)-recursiva no siempre sera un conjunto \(\Sigma\)-recursivo. Por ejemplo si tomamos \(\Sigma\) tal que \(\Sigma\supseteq\Sigma_{p}\), entonces \(C_{1}^{0,1}|_{A}\) es una funcion \(\Sigma\)-recursiva ya que es la restriccion de la funcion \(\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 minimizacion no es \(\Sigma\)-efectivamente computable (y por lo tanto es no \(\Sigma\)-recursiva).

Proof. Notese 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 tambien \(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\). Notese 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 contradiccion.