Batallas entre paradigmas

En esta seccion compararemos los tres paradigmas de computabilidad efectiva que hemos desarrollado anteriormente. Para esto probaremos que cada uno de dichos paradigmas "vence" al otro en el sentido que incluye por lo menos todas las funciones que incluye el otro en su modelizacion del concepto de funcion \(\Sigma\)-efectivamente computable.

4.4.1 Neumann vence a Godel

Usando macros podemos ahora probar que el paradigma imperativo de Neumann es por lo menos tan abarcativo como el funcional de Godel. Mas concretamente:

El caso \(k=0\) es dejado al lector. Supongamos (*) vale para \(k\), veremos que vale para \(k+1\). Sea \(h\in\mathrm{R}_{k+1}^{\Sigma}-\mathrm{R}_{k}^{\Sigma}.\) Hay varios casos

Caso 1. Supongamos \(h=M(P)\), con \(P:\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), un predicado perteneciente a \(\mathrm{R}_{k}^{\Sigma}\). Por hipotesis inductiva, \(P\) es \(\Sigma\)-computable y por lo tanto tenemos un macro \[\left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\overline{n+1},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] lo cual nos permite realizar el siguiente programa \[\begin{array}{ll} \mathrm{L}2 & \left[\mathrm{IF}\;P(\mathrm{N}\overline{n+1},\mathrm{N}1,...,\mathrm{N}\bar{n},\mathrm{P}1,...,\mathrm{P}\bar{m})\;\mathrm{GOTO}\;\mathrm{L}1\right]\\ & \mathrm{N}\overline{n+1}\leftarrow\mathrm{N}\overline{n+1}+1\\ & \mathrm{GOTO}\;\mathrm{L}2\\ \mathrm{L}1 & \mathrm{N}1\leftarrow\mathrm{N}\overline{n+1} \end{array}\] Es facil chequear que este programa computa \(h.\)

Caso 2. Supongamos \(h=R(f,\mathcal{G})\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\\ \mathcal{G}_{a} & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}\text{, }a\in\Sigma \end{aligned}\] elementos de \(\mathrm{R}_{k}^{\Sigma}\). Sea \(\Sigma=\{a_{1},...,a_{r}\}.\) Por hipotesis inductiva, las funciones \(f\), \(\mathcal{G}_{a}\), \(a\in\Sigma\), son \(\Sigma\)-computables y por lo tanto tenemos macros \[\left[\mathrm{W}\overline{m+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\] \[\left[\mathrm{W}\overline{m+3}\leftarrow\mathcal{G}_{a_{i}}(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m},\mathrm{W}\overline{m+1},\mathrm{W}\overline{m+2})\right]\text{, }i=1,...,r\] Podemos entonces hacer el siguiente programa: \[\begin{array}{rl} & \left[\mathrm{P}\overline{m+3}\leftarrow f(\mathrm{N}1,...,\mathrm{N}\bar{n},\mathrm{P}1,...,\mathrm{P}\bar{m})\right]\\ \mathrm{L}\overline{r+1} & \mathrm{IF}\;\mathrm{P}\overline{m+1}\ \mathrm{BEGINS\ }a_{1}\text{ }\mathrm{GOTO}\;\mathrm{L}1\\ & \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ & \mathrm{IF}\;\mathrm{P}\overline{m+1}\ \mathrm{BEGINS\ }a_{r}\text{ }\mathrm{GOTO}\;\mathrm{L}\bar{r}\\ & \mathrm{GOTO}\;\mathrm{L}\overline{r+2}\\ \mathrm{L}1 & \mathrm{P}\overline{m+1}\leftarrow\text{ }^{\curvearrowright}\mathrm{P}\overline{m+1}\\ & \left[\mathrm{P}\overline{m+3}\leftarrow\mathcal{G}_{a_{1}}(\mathrm{N}1,...,\mathrm{N}\bar{n},\mathrm{P}1,...,\mathrm{P}\bar{m},\mathrm{P}\overline{m+2},\mathrm{P}\overline{m+3})\right]\\ & \mathrm{P}\overline{m+2}\leftarrow\mathrm{P}\overline{m+2}.a_{1}\\ & \mathrm{GOTO}\;\mathrm{L}\overline{r+1}\\ & \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ \mathrm{L}\bar{r} & \mathrm{P}\overline{m+1}\leftarrow\text{ }^{\curvearrowright}\mathrm{P}\overline{m+1}\\ & \left[\mathrm{P}\overline{m+3}\leftarrow\mathcal{G}_{a_{r}}(\mathrm{N}1,...,\mathrm{N}\bar{n},\mathrm{P}1,...,\mathrm{P}\bar{m},\mathrm{P}\overline{m+2},\mathrm{P}\overline{m+3})\right]\\ & \mathrm{P}\overline{m+2}\leftarrow\mathrm{P}\overline{m+2}.a_{r}\\ & \mathrm{GOTO}\;\mathrm{L}\overline{r+1}\\ \mathrm{L}\overline{r+2} & \mathrm{P}1\leftarrow\mathrm{P}\overline{m+3} \end{array}\] Es facil chequear que este programa computa \(h.\)

4.12 (Segundo Manatial de Macros). Sea \(\Sigma\) un alfabeto finito. Si \[\begin{aligned} f & :D_{f}\subseteq\omega^{n}\times\Sigma^{\ast}{}^{m}\rightarrow\omega\\ g & :D_{g}\subseteq\omega^{n}\times\Sigma^{\ast}{}^{m}\rightarrow\Sigma^{\ast}\\ P & :D_{P}\subseteq\omega^{n}\times\Sigma^{\ast}{}^{m}\rightarrow\{0,1\} \end{aligned}\] son \(\Sigma\)-recursivas, entonces en \(\mathcal{S}^{\Sigma}\) hay macros \[\begin{aligned} & \left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\\ & \left[\mathrm{W}\overline{m+1}\leftarrow g(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\\ & \left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right] \end{aligned}\]

4.4.1.1 Se lleno de macros

Cabe destacar que el Segundo Manantial de Macros nos dice que en \(\mathcal{S}^{\Sigma}\) hay macros \[\begin{aligned} & \left[\mathrm{V}\overline{n+1}\leftarrow f(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\\ & \left[\mathrm{W}\overline{m+1}\leftarrow g(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\right]\\ & \left[\mathrm{IF}\;P(\mathrm{V}1,...,\mathrm{V}\bar{n},\mathrm{W}1,...,\mathrm{W}\bar{m})\;\mathrm{GOTO}\;\mathrm{A}1\right] \end{aligned}\] para todas las funciones \(\Sigma\)-mixtas y predicados \(\Sigma\)-mixtos que hemos trabajado hasta el momento en la materia ya que todas eran \(\Sigma\)-p.r.. Esto fortalece mucho al lenguaje \(\mathcal{S}^{\Sigma}\) ya que ahora tenemos macros para todas las funciones y predicados cotidianos en la matematica, ademas de tener macros para todas las funciones y predicados \(\Sigma\)-computables, debido al Primer Manantial de Macros. Veamos un ejemplo:

4.42. Supongamos \(S_{1},S_{2}\subseteq\omega^{n}\times\Sigma^{\ast m}\) son conjuntos \(\Sigma\)-enumerables. Entonces \(S_{1}\cup S_{2}\) es \(\Sigma\)-enumerable.

Proof. Podemos suponer que ni \(S_{1}\) ni \(S_{2}\) son vacios ya que de lo contrario el resultado es trivial. Ademas supondremos que \(n=2\) y \(m=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 Caracterizacion de \(\Sigma\)-enumerabilidad. 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\)-computables, \(\mathrm{Im}(F)=S_{1}\) y \(\mathrm{Im}(G)=S_{2}\). O sea que nuestro Primer Manantial de Macros nos dice que en \(\mathcal{S}^{\Sigma}\) 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., el Segundo Manantial de Macros nos dice que en \(\mathcal{S}^{\Sigma}\) 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., el Segundo Manantial de Macros nos dice 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 Caracterizacion de \(\Sigma\)-enumerabilidad por lo cual \(S_{1}\cup S_{2}\) es \(\Sigma\)-enumerable.

En forma analoga a lo hecho recien, se pueden probar, copiando la respectiva idea en el paradigma de la computabilidad efectiva, los siguientes resultados:

O sea que con el uso de nuestros poderosos macros asociados a funciones y predicados \(\Sigma\)-p.r. (gracias al Segundo Manatial) mas los que provee el Primer Manatial podemos simular los procedimientos efectivos realizados dentro del paradigma filosofico con programas concretos del lenguaje \(\mathcal{S}^{\Sigma}\). Pero esto no es del todo asi, ya que los ejemplos vistos recien no hacen uso del concepto de “ejecucion de una cantidad de pasos”, idea que en muchos diseños de nuestros procedimentos efectivos es usada. Por ejemplo si queremos “copiar” dentro del paradigama imperativo la prueba del resultado

notaremos la dificultad de aun no poder hablar de cantidad de pasos en la ejecucion del programa que compute a \(f\). O sea nuestro Primer Manatial nos da un macro de asignacion para \(f\) pero no es claro de como correr una expansion de dicho macro una cierta cantidad de veces. Esto lo lograremos usando macros asociados a las funciones \(Halt^{n,m}\), \(E_{\#}^{n,m}\) y \(E_{\ast}^{n,m}\) las cuales se usan en la batalla Godel vence a Neumann que viene a continuacion. Estas funciones seran clave a la hora de simular con programas a procedimientos efectivos que en su funcionamiento involucran el funcionamiento de otros procedimientos efectivos.

O sea que luego de ambas batallas entre Godel y Neumann, el paradigma imperativo se vera fortalecido sustancialmente. Tambien mas adelante en la Seccion Resultados basicos presentados en paradigma recursivo veremos como los desarrollos hechos en ambas batallas entre Godel y Neumann fortalecen al paradigma funcional. Otro ejemplo de esto ultimo es la Forma Normal de Kleene donde se prueba que toda funcion \(\Sigma\)-recursiva es expresable en la forma \(g\circ M(P)\) donde \(g\) es una funcion \(\Sigma\)-p.r. y \(P\) es un predicado \(\Sigma\)-p.r..

4.4.2 Godel vence a Neumann

Para probar que toda funcion \(\Sigma\)-computable es \(\Sigma\)-recursiva debemos hacer un profundo estudio de la recursividad del lenguaje \(\mathcal{S}^{\Sigma}\). Primero analizaremos la recursividad de la sintaxis de \(\mathcal{S}^{\Sigma}\).

4.4.2.1 Analisis de la recursividad de la sintaxis de \(\mathcal{S}^{\Sigma}\)

Primero probaremos dos lemas que muestran que la sintaxis de \(\mathcal{S}^{\Sigma}\) es \((\Sigma\cup\Sigma_{p})\)-recursiva primitiva. Recordemos que \(Sig:Num^{\ast}\rightarrow Num^{\ast}\) fue definida de la siguiente manera \[\begin{aligned} Sig(\varepsilon) & =1\\ Sig(\alpha0) & =\alpha1\\ Sig(\alpha1) & =\alpha2\\ Sig(\alpha2) & =\alpha3\\ Sig(\alpha3) & =\alpha4\\ Sig(\alpha4) & =\alpha5\\ Sig(\alpha5) & =\alpha6\\ Sig(\alpha6) & =\alpha7\\ Sig(\alpha7) & =\alpha8\\ Sig(\alpha8) & =\alpha9\\ Sig(\alpha9) & =Sig(\alpha)0 \end{aligned}\] Y tambien definimos \(Dec:\omega\rightarrow Num^{\ast}\) de la siguiente manera \[\begin{aligned} Dec(0) & =\varepsilon\\ Dec(n+1) & =Sig(Dec(n)) \end{aligned}\] Recordemos tambien que para hacer mas agil la notacion escribimos \(\bar{n}\) en lugar de \(Dec(n)\).

4.43. Sea \(\Sigma\) un alfabeto cualquiera. La funcion \(Dec\) es \((\Sigma\cup\Sigma_{p})\)-p.r..

Proof. Es facil ver que \(Dec\) es \(Num\)-p.r.. Ya que tambien es \((\Sigma\cup\Sigma_{p})\)-mixta, el Teorema 4.2 nos dice que es \((\Sigma\cup\Sigma_{p})\)-p.r.. En el Lema 4.12 se da una prueba facil de este hecho, sin recurrir al citado teorema.

4.44. Para cada \(n,x\in\omega\), tenemos que \(\left\vert \bar{n}\right\vert \leq x\) si y solo si \(n\leq10^{x}-1\)

4.45. \(\mathrm{Ins}^{\Sigma}\) es un conjunto \((\Sigma\cup\Sigma_{p})\)-p.r..

Proof. Para simplificar la prueba asumiremos que \(\Sigma=\{@,\blacktriangle\}\). Ya que \(\mathrm{Ins}^{\Sigma}\) es union de los siguientes conjuntos \[\begin{aligned} L_{1} & =\left\{ \mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{k}+1:k\in\mathbf{N}\right\} \\ L_{2} & =\left\{ \mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{k}\dot{-}1:k\in\mathbf{N}\right\} \\ L_{3} & =\left\{ \mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{n}:k,n\in\mathbf{N}\right\} \\ L_{4} & =\left\{ \mathrm{N}\bar{k}\leftarrow0:k\in\mathbf{N}\right\} \\ L_{5} & =\left\{ \mathrm{IF}\;\mathrm{N}\bar{k}\neq0\;\mathrm{GOTO}\;\mathrm{L}\bar{m}:k,m\in\mathbf{N}\right\} \\ L_{6} & =\left\{ \mathrm{P}\bar{k}\leftarrow\mathrm{P}\bar{k}.@:k\in\mathbf{N}\right\} \\ L_{7} & =\left\{ \mathrm{P}\bar{k}\leftarrow\mathrm{P}\bar{k}.\blacktriangle:k\in\mathbf{N}\right\} \\ L_{8} & =\left\{ \mathrm{P}\bar{k}\leftarrow\text{ }^{\curvearrowright}\mathrm{P}\bar{k}:k\in\mathbf{N}\right\} \\ L_{9} & =\left\{ \mathrm{P}\bar{k}\leftarrow\mathrm{P}\bar{n}:k,n\in\mathbf{N}\right\} \\ L_{10} & =\left\{ \mathrm{P}\bar{k}\leftarrow\varepsilon:k\in\mathbf{N}\right\} \\ L_{11} & =\left\{ \mathrm{IF}\;\mathrm{P}\bar{k}\;\mathrm{BEGINS}\;@\;\mathrm{GOTO}\;\mathrm{L}\bar{m}:k,m\in\mathbf{N}\right\} \\ L_{12} & =\left\{ \mathrm{IF}\;\mathrm{P}\bar{k}\;\mathrm{BEGINS}\;\blacktriangle\;\mathrm{GOTO}\;\mathrm{L}\bar{m}:k,m\in\mathbf{N}\right\} \\ L_{13} & =\left\{ \mathrm{GOTO}\;\mathrm{L}\bar{m}:m\in\mathbf{N}\right\} \\ L_{14} & =\left\{ \mathrm{SKIP}\right\} \\ L_{15} & =\left\{ \mathrm{L}\bar{k}\alpha:k\in\mathbf{N\;}\text{y }\alpha\in L_{1}\cup...\cup L_{14}\right\} \end{aligned}\] solo debemos probar que \(L_{1},...,L_{15}\) son \((\Sigma\cup\Sigma_{p})\)-p.r.. Veremos primero por ejemplo que \[L_{11}=\left\{ \mathrm{IFP}\bar{k}\mathrm{BEGINS}@\mathrm{GOTOL}\bar{m}:k,m\in\mathbf{N}\right\}\] es \((\Sigma\cup\Sigma_{p})\)-p.r.. Primero notese que \(\alpha\in L_{11}\) si y solo si existen \(k,m\in\mathbf{N}\) tales que \[\alpha=\mathrm{IFP}\bar{k}\mathrm{BEGINS}@\mathrm{GOTOL}\bar{m}\] Mas formalmente tenemos que \(\alpha\in L_{11}\) si y solo si \[(\exists k\in\mathbf{N})(\exists m\in\mathbf{N})\;\alpha=\mathrm{IFP}\bar{k}\mathrm{BEGINS}@\mathrm{GOTOL}\bar{m}\] Ya que cuando existen tales \(k,m\) tenemos que \(\bar{k}\) y \(\bar{m}\) son subpalabras de \(\alpha\), el lema anterior nos dice que \(\alpha\in L_{11}\) si y solo si \[(\exists k\in\mathbf{N})_{k\leq10^{\left\vert \alpha\right\vert }}(\exists m\in\mathbf{N})_{m\leq10^{\left\vert \alpha\right\vert }}\;\alpha=\mathrm{IFP}\bar{k}\mathrm{BEGINS}@\mathrm{GOTOL}\bar{m}\] Sea \[P=\lambda mk\alpha\left[\alpha=\mathrm{IFP}\bar{k}\mathrm{BEGINS}@\mathrm{GOTOL}\bar{m}\right]\] Ya que \(D_{\lambda k\left[\bar{k}\right]}=\omega\), tenemos que \(D_{P}=\omega^{2}\times(\Sigma\cup\Sigma_{p})^{\ast}\). Notese que \[P=\lambda\alpha\beta\left[\alpha=\beta\right]\circ\left[p_{3}^{2,1},f\right]\] donde \[f=\lambda\alpha_{1}\alpha_{2}\alpha_{3}\alpha_{4}\left[\alpha_{1}\alpha_{2}\alpha_{3}\alpha_{4}\right]\circ\left[C_{\mathrm{IFP}}^{2,1},\lambda k\left[\bar{k}\right]\circ p_{2}^{2,1},C_{\mathrm{BEGINS}@\mathrm{GOTOL}}^{2,1},\lambda k\left[\bar{k}\right]\circ p_{1}^{2,1}\right]\] lo cual nos dice que \(P\) es \((\Sigma\cup\Sigma_{p})\)-p.r..

Notese que \[\chi_{L_{11}}^{(\Sigma\cup\Sigma_{p})^{\ast}}=\lambda\alpha\left[(\exists k\in\mathbf{N})_{k\leq10^{\left\vert \alpha\right\vert }}(\exists m\in\mathbf{N})_{m\leq10^{\left\vert \alpha\right\vert }}\;P(m,k,\alpha)\right]\] Esto nos dice que podemos usar dos veces el Lema 4.22 para ver que \(\chi_{L_{11}}^{(\Sigma\cup\Sigma_{p})^{\ast}}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Veamos como. Sea \[Q=\lambda k\alpha\left[(\exists m\in\mathbf{N})_{m\leq10^{\left\vert \alpha\right\vert }}\;P(m,k,\alpha)\right]\] Por el Lema 4.22 tenemos que \[\lambda xk\alpha\left[(\exists m\in\mathbf{N})_{m\leq x}\;P(m,k,\alpha)\right]\] es \((\Sigma\cup\Sigma_{p})\)-p.r. lo cual nos dice que \[Q=\lambda xk\alpha\left[(\exists m\in\mathbf{N})_{m\leq x}\;P(m,k,\alpha)\right]\circ\left[\lambda\alpha\left[10^{\left\vert \alpha\right\vert }\right]\circ p_{2}^{1,1},p_{1}^{1,1},p_{2}^{1,1}\right]\] lo es. Ya que \[\chi_{L_{11}}^{(\Sigma\cup\Sigma_{p})^{\ast}}=\lambda\alpha\left[(\exists k\in\mathbf{N})_{k\leq10^{\left\vert \alpha\right\vert }}\;Q(k,\alpha)\right]\] podemos en forma similar aplicar el Lema 4.22 y obtener finalmente que \(\chi_{L_{11}}^{(\Sigma\cup\Sigma_{p})^{\ast}}\) es \((\Sigma\cup\Sigma_{p})\)-p.r..

En forma similar podemos probar que \(L_{1},...,L_{14}\) son \((\Sigma\cup\Sigma_{p})\)-p.r.. Esto nos dice que \(L_{1}\cup...\cup L_{14}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Notese que \(L_{1}\cup...\cup L_{14}\) es el conjunto de las instrucciones basicas de \(\mathcal{S}^{\Sigma}\). Llamemos \(\mathrm{InsBas}^{\Sigma}\) a dicho conjunto. Para ver que \(L_{15}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. notemos que \[\chi_{L_{15}}^{(\Sigma\cup\Sigma_{p})^{\ast}}=\lambda\alpha\left[(\exists k\in\mathbf{N})_{k\leq10^{\left\vert \alpha\right\vert }}(\exists\beta\in\mathrm{InsBas}^{\Sigma})_{\left\vert \beta\right\vert \leq\left\vert \alpha\right\vert }\;\alpha=\mathrm{L}\bar{k}\beta\right]\] lo cual nos dice que aplicando dos veces el Lema 4.22 obtenemos que \(\chi_{L_{15}}^{(\Sigma\cup\Sigma_{p})^{\ast}}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Ya que \(\mathrm{Ins}^{\Sigma}=\mathrm{InsBas}^{\Sigma}\cup L_{15}\) tenemos que \(\mathrm{Ins}^{\Sigma}\) es \((\Sigma\cup\Sigma_{p})\)-p.r..

Recordemos que \(Bas:\mathrm{Ins}^{\Sigma}\rightarrow(\Sigma\cup\Sigma_{p})^{\ast}\), fue definida por \[Bas(I)=\left\{ \begin{array}{ccl} J & & \text{si }I\text{ es de la forma }\mathrm{L}\bar{k}J\text{, con }k\in\mathbf{N}\text{ y }J\in\mathrm{Ins}^{\Sigma}\\ I & & \text{caso contrario} \end{array}\right.\] Definamos \(Lab:\mathrm{Ins}^{\Sigma}\rightarrow(\Sigma\cup\Sigma_{p})^{\ast}\) de la siguiente manera \[Lab(I)=\left\{ \begin{array}{lll} \mathrm{L}\bar{k} & & \text{si }I\text{ es de la forma }\mathrm{L}\bar{k}J\text{, con }k\in\mathbf{N}\text{ y }J\in\mathrm{Ins}^{\Sigma}\\ \varepsilon & & \text{caso contrario} \end{array}\right.\]

4.46. \(Bas\) y \(Lab\) son funciones \((\Sigma\cup\Sigma_{p})\)-p.r.

Proof. Sea \(\leq\) un orden total sobre \(\Sigma\cup\Sigma_{p}\). Sea \(L=\{\mathrm{L}\bar{k}:k\in\mathbf{N}\}\cup\{\varepsilon\}\). Dejamos al lector probar que \(L\) es un conjunto \((\Sigma\cup\Sigma_{p})\)-p.r.. Sea \[P=\lambda I\alpha\left[\alpha\in\mathrm{Ins}^{\Sigma}\wedge I\in\mathrm{Ins}^{\Sigma}\wedge[\alpha]_{1}\neq\mathrm{L}\wedge(\exists\beta\in L)\ I=\beta\alpha\right]\] Note que \(D_{P}=(\Sigma\cup\Sigma_{p})^{\ast2}\). Dejamos al lector probar que \(P\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Notese ademas que cuando \(I\in\mathrm{Ins}^{\Sigma}\) tenemos que \(P(I,\alpha)=1\) sii \(\alpha=Bas(I)\). Dejamos al lector probar que \(Bas=M^{\leq}\left(P\right)\) por lo que para ver que \(Bas\) es \((\Sigma\cup\Sigma_{p})\)-p.r., solo nos falta ver que la funcion \(Bas\) es acotada por alguna funcion \((\Sigma\cup\Sigma_{p})\)-p.r. y \((\Sigma\cup\Sigma_{p})\)-total. Pero esto es trivial ya que \(\left\vert Bas(I)\right\vert \leq\left\vert I\right\vert =\lambda\alpha[\left\vert \alpha\right\vert ](I)\), para cada \(I\in\mathrm{Ins}^{\Sigma}\).

Finalmente note que \[Lab=M^{\leq}\left(\lambda I\alpha\left[\alpha Bas(I)=I\right]\right)\] lo cual nos dice que \(Lab\) es \((\Sigma\cup\Sigma_{p})\)-p.r..

Recordemos que dado un programa \(\mathcal{P}\) habiamos definido \(I_{i}^{\mathcal{P}}=\varepsilon\), para \(i=0\) o \(i>n(\mathcal{P}).\) O sea que la funcion \((\Sigma\cup\Sigma_{p})\)-mixta \(\lambda i\mathcal{P}\left[I_{i}^{\mathcal{P}}\right]\) tiene dominio igual a \(\omega\times\mathrm{Pro}^{\Sigma}\). Notese que usamos notacion lambda respecto del alfabeto \(\Sigma\cup\Sigma_{p}\). Ademas notese que usamos la variable \(\mathcal{P}\) en la notacion lambda por un tema de comodidad psicologica dado que la expresion \(I_{i}^{\alpha}\) esta definida solo cuando \(\alpha\) es un programa pero podriamos haber escrito \(\lambda i\alpha\left[I_{i}^{\alpha}\right]\) y sigue siendo la misma funcion.

4.47.

adhocprefix(a)adhocsufix \(\mathrm{Pro}^{\Sigma}\) es un conjunto \((\Sigma\cup\Sigma_{p})\)-p.r.
adhocprefix(b)adhocsufix \(\lambda\mathcal{P}\left[n(\mathcal{P})\right]\) y \(\lambda i\mathcal{P}\left[I_{i}^{\mathcal{P}}\right]\) son funciones \((\Sigma\cup\Sigma_{p})\)-p.r..

Proof. Ya que \(\mathrm{Pro}^{\Sigma}=D_{\lambda\mathcal{P}\left[n(\mathcal{P})\right]}\) tenemos que (b) implica (a). Para probar (b) Sea \(\leq\) un orden total sobre \(\Sigma\cup\Sigma_{p}\). Sea \(P\) el siguiente predicado

\(\lambda x\left[Lt(x)>0\wedge(\forall t\in\mathbf{N})_{t\leq Lt(x)}\;\ast^{\leq}((x)_{t})\in\mathrm{Ins}^{\Sigma}\wedge\right.\)

\(\ \ \ \ \ \ \ \ \ \ \ \ (\forall t\in\mathbf{N})_{t\leq Lt(x)}(\forall m\in\mathbf{N})\;\lnot(\mathrm{L}\bar{m}\ \)t-final \(\ast^{\leq}((x)_{t}))\vee\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left.(\exists j\in\mathbf{N})_{j\leq Lt(x)}(\exists\alpha\in(\Sigma\cup\Sigma_{p})-Num)\;\mathrm{L}\bar{m}\alpha\ \text{t-inicial}\ast^{\leq}((x)_{j})\right]\)

Notese que \(D_{P}=\mathbf{N}\) y que \(P(x)=1\) sii \(Lt(x)>0\), \(\ast^{\leq}((x)_{t})\in\mathrm{Ins}^{\Sigma}\), para cada \(t=1,...,Lt(x)\) y ademas \(\subset_{t=1}^{t=Lt(x)}\ast^{\leq}((x)_{t})\in\mathrm{Pro}^{\Sigma}\). Para ver que \(P\) es \((\Sigma\cup\Sigma_{p})\)-p.r. solo nos falta acotar el cuantificador \((\forall m\in\mathbf{N})\) de la expresion lambda que define a \(P\). Ya que nos interesan los valores de \(m\) para los cuales \(\bar{m}\) es posiblemente una subpalabra de alguna de las palabras \(\ast^{\leq}((x)_{j})\), el Lema 4.44 nos dice que una cota posible es \(10^{\max\{\left\vert \ast^{\leq}((x)_{j})\right\vert :1\leq j\leq Lt(x)\}}-1\). Dejamos al lector los detalles de la prueba de que \(P\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Sea \[Q=\lambda x\alpha\left[P(x)\wedge\alpha=\subset_{t=1}^{t=Lt(x)}\ast^{\leq}((x)_{t})\right]\text{.}\] Note que \(D_{Q}=\mathbf{N}\times(\Sigma\cup\Sigma_{p})^{\ast}\). Claramente \(Q\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Ademas note que \(D_{M(Q)}=\mathrm{Pro}^{\Sigma}\). Notese que para \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\), tenemos que \(M(Q)(\mathcal{P})\) es aquel numero tal que pensado como infinitupla (via mirar su secuencia de exponentes) codifica la secuencia de instrucciones que forman a \(\mathcal{P}\). Es decir \[M(Q)(\mathcal{P})=\left\langle \#^{\leq}(I_{1}^{\mathcal{P}}),\#^{\leq}(I_{2}^{\mathcal{P}}),...,\#^{\leq}(I_{n(\mathcal{P})}^{\mathcal{P}}),0,0,...\right\rangle\] Por (b) del Lema 4.25, \(M(Q)\) es \((\Sigma\cup\Sigma_{p})\)-p.r. ya que para cada \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) tenemos que \[\begin{aligned} M(Q)(\mathcal{P}) & =\left\langle \#^{\leq}(I_{1}^{\mathcal{P}}),\#^{\leq}(I_{2}^{\mathcal{P}}),...,\#^{\leq}(I_{n(\mathcal{P})}^{\mathcal{P}}),0,0,...\right\rangle \\ & =\underset{i=1}{\overset{n(\mathcal{P})}{\Pi}}pr(i)^{\#^{\leq}(I_{1}^{\mathcal{P}})}\\ & \leq\underset{i=1}{\overset{\left\vert \mathcal{P}\right\vert }{\Pi}}pr(i)^{\#^{\leq}(\mathcal{P})} \end{aligned}\] Ademas tenemos que \[\begin{aligned} \lambda\mathcal{P}\left[n(\mathcal{P})\right] & =\lambda x\left[Lt(x)\right]\circ M(Q)\\ \lambda i\mathcal{P}\left[I_{i}^{\mathcal{P}}\right] & =\ast^{\leq}\circ g\circ\left[p_{1}^{1,1},M(Q)\circ p_{2}^{1,1}\right] \end{aligned}\] donde \(g=C_{0}^{1,1}|_{\{0\}\times\omega}\cup\lambda ix\left[(x)_{i}\right]\), lo cual dice que \(\lambda\mathcal{P}\left[n(\mathcal{P})\right]\) y \(\lambda i\mathcal{P}\left[I_{i}^{\mathcal{P}}\right]\) son funciones \((\Sigma\cup\Sigma_{p})\)-p.r..

4.4.2.2 Analisis de la recursividad de la semantica de \(\mathcal{S}^{\Sigma}\)

Para estudiar la recursividad de la semantica de \(\mathcal{S}^{\Sigma}\) deberemos definir varias funciones que tienen que ver con el funcionamiento de un programa y estudiar su recursividad.

Las funciones \(i^{n,m}\), \(E_{\#}^{n,m}\) y \(E_{\ast}^{n,m}\)

Sean \(n,m\geq0\) fijos. Definamos entonces las funciones \[\begin{aligned} i^{n,m} & :\omega\times\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\rightarrow\omega\\ E_{\#}^{n,m} & :\omega\times\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\rightarrow\omega^{[\mathbf{N}]}\\ E_{\ast}^{n,m} & :\omega\times\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\rightarrow\Sigma^{\ast[\mathbf{N}]} \end{aligned}\] de la siguiente manera \[\begin{aligned} (i^{n,m}(0,\vec{x},\vec{\alpha},\mathcal{P}),E_{\#}^{n,m}(0,\vec{x},\vec{\alpha},\mathcal{P}),E_{\ast}^{n,m}(0,\vec{x},\vec{\alpha},\mathcal{P})) & =(1,(x_{1},...,x_{n},0,...),(\alpha_{1},...,\alpha_{m},\varepsilon,...))\\ (i^{n,m}(t+1,\vec{x},\vec{\alpha},\mathcal{P}),E_{\#}^{n,m}(t+1,\vec{x},\vec{\alpha},\mathcal{P}),E_{\ast}^{n,m}(t+1,\vec{x},\vec{\alpha},\mathcal{P})) & =S_{\mathcal{P}}(i^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),E_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),E_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P})) \end{aligned}\] Notese que \[(i^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),E_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),E_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}))\] es la descripcion instantanea que se obtiene luego de correr \(\mathcal{P}\) una cantidad \(t\) de pasos partiendo del estado \[((x_{1},...,x_{n},0,...),(\alpha_{1},...,\alpha_{m},\varepsilon,...))\] Es importante notar que si bien \(i^{n,m}\) es una funcion \((\Sigma\cup\Sigma_{p})\)-mixta, ni \(E_{\#}^{n,m}\) ni \(E_{\ast}^{n,m}\) lo son.

Definamos para cada \(j\in\mathbf{N}\), funciones \[\begin{aligned} E_{\#j}^{n,m} & :\omega\times\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\rightarrow\omega\\ E_{\ast j}^{n,m} & :\omega\times\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\rightarrow\Sigma^{\ast} \end{aligned}\] de la siguiente manera \[\begin{aligned} E_{\#j}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}) & =j\text{-esima coordenada de }E_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P})\\ E_{\ast j}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}) & =j\text{-esima coordenada de }E_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}) \end{aligned}\] Notese que \[\begin{aligned} E_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}) & =(E_{\#1}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),E_{\#2}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),...)\\ E_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}) & =(E_{\ast1}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),E_{\ast2}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),...) \end{aligned}\] Nuestro proximo objetivo es mostrar que las funciones \(i^{n,m}\), \(E_{\#j}^{n,m}\), \(E_{\ast j}^{n,m}\) son \((\Sigma\cup\Sigma_{p})\)-p.r.

Para esto primero debemos probar un lema el cual muestre que una ves codificadas las descripciones instantaneas en forma numerica, las funciones que dan la descripcion instantanea sucesora son \((\Sigma\cup\Sigma_{p})\)-p.r.. Dado un orden total \(\leq\) sobre \(\Sigma\cup\Sigma_{p}\), codificaremos las descripciones instantaneas haciendo uso de las biyecciones \[\begin{array}{rcl} \omega^{\left[\mathbf{N}\right]} & \rightarrow & \mathbf{N}\\ (s_{1},s_{2},...) & \rightarrow & \left\langle s_{1},s_{2},...\right\rangle \end{array}\;\;\;\;\;\;\;\;\;\;\;\;\begin{array}{rcl} \Sigma^{\ast\left[\mathbf{N}\right]} & \rightarrow & \mathbf{N}\\ (\sigma_{1},\sigma_{2},...) & \rightarrow & \left\langle \#^{\leq}(\sigma_{1}),\#^{\leq}(\sigma_{2}),...\right\rangle \end{array}\] Es decir que a la descripcion instantanea \[(i,(s_{1},s_{2},...),(\sigma_{1},\sigma_{2},...))\] la codificaremos con la terna \[(i,\left\langle s_{1},s_{2},...\right\rangle ,\left\langle \#^{\leq}(\sigma_{1}),\#^{\leq}(\sigma_{2}),...\right\rangle )\in\omega\times\mathbf{N}\times\mathbf{N}\] Es decir que una terna \((i,x,y)\in\omega\times\mathbf{N}\times\mathbf{N}\) codificara a la descripcion instantanea \[(i,((x)_{1},(x)_{2},...),(\ast^{\leq}((y)_{1}),\ast^{\leq}((y)_{2}),...))\] Definamos \[\begin{aligned} s & :\omega\times\mathbf{N}\times\mathbf{N}\times\mathrm{Pro}^{\Sigma}\rightarrow\omega\\ S_{\#} & :\omega\times\mathbf{N}\times\mathbf{N}\times\mathrm{Pro}^{\Sigma}\rightarrow\omega\\ S_{\ast} & :\omega\times\mathbf{N}\times\mathbf{N}\times\mathrm{Pro}^{\Sigma}\rightarrow\omega \end{aligned}\] de la siguiente manera \[\begin{array}[t]{ll} s(i,x,y,\mathcal{P})= & \text{primera coordenada de la codificacion de la descripcion instantanea}\\ & \text{sucesora de }(i,((x)_{1},(x)_{2},...),(\ast^{\leq}((y)_{1}),\ast^{\leq}((y)_{2}),...))\text{ en }\mathcal{P} \end{array}\] \[\begin{array}[t]{ll} S_{\#}(i,x,y,\mathcal{P})= & \text{segunda coordenada de la codificacion de la descripcion instantanea}\\ & \text{sucesora de }(i,((x)_{1},(x)_{2},...),(\ast^{\leq}((y)_{1}),\ast^{\leq}((y)_{2}),...))\text{ en }\mathcal{P} \end{array}\] \[\begin{array}[t]{ll} S_{\ast}(i,x,y,\mathcal{P})= & \text{tercera coordenada de la codificacion de la descripcion instantanea}\\ & \text{sucesora de }(i,((x)_{1},(x)_{2},...),(\ast^{\leq}((y)_{1}),\ast^{\leq}((y)_{2}),...))\text{ en }\mathcal{P} \end{array}\] Notese que la definicion de estas funciones depende del orden total \(\leq\) sobre \(\Sigma\cup\Sigma_{p}\).

4.48. Dado un orden total \(\leq\) sobre \(\Sigma\cup\Sigma_{p}\), las funciones \(s\), \(S_{\#}\) y \(S_{\ast}\) son \((\Sigma\cup\Sigma_{p})\)-p.r..

Proof. Necesitaremos algunas funciones \((\Sigma\cup\Sigma_{p})\)-p.r.. Dada una instruccion \(I\) en la cual al menos ocurre una variable, usaremos \(\#Var1(I)\) para denotar el numero de la primer variable que ocurre en \(I\). Por ejemplo \[\#Var1\left(\mathrm{L}\bar{n}\;\mathrm{IF\;N}\bar{k}\neq0\;\mathrm{GOTO\;L}\bar{m}\right)=k\] Notese que \(\lambda I[\#Var1(I)]\) tiene dominio igual a \(\mathrm{Ins}^{\Sigma}-L\), donde \(L\) es la union de los siguientes conjuntos \[\begin{gathered} \{\mathrm{GOTO\ L}\bar{m}:m\in\mathbf{N\}\cup}\{\mathrm{L}\bar{k}\ \mathrm{GOTO\ L}\bar{m}:k,m\in\mathbf{N\}}\\ \left\{ \mathrm{SKIP}\right\} \mathbf{\cup}\{\mathrm{L}\bar{k}\ \mathrm{SKIP}:k\in\mathbf{N\}} \end{gathered}\] Dada una instruccion \(I\) en la cual ocurren dos variables, usaremos \(\#Var2(I)\) para denotar el numero de la segunda variable que ocurre en \(I\). Por ejemplo \[\#Var2\left(\mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{m}\right)=m\] Notese que el dominio de \(\lambda I[\#Var2(I)]\) es igual a la union de los siguientes conjuntos \[\begin{aligned} \{\mathrm{N}\bar{k} & \leftarrow\mathrm{N}\bar{m}:k,m\in\mathbf{N\}\cup}\{\mathrm{L}\bar{j}\ \mathrm{N}\bar{k}\leftarrow\mathrm{N}\bar{m}:j,k,m\in\mathbf{N\}}\\ \{\mathrm{P}\bar{k} & \leftarrow\mathrm{P}\bar{m}:k,m\in\mathbf{N\}\cup}\{\mathrm{L}\bar{j}\ \mathrm{P}\bar{k}\leftarrow\mathrm{P}\bar{m}:j,k,m\in\mathbf{N\}} \end{aligned}\] Ademas notese que para una instruccion \(I\) tenemos que \[\begin{aligned} \#Var1(I) & =\min_{k}(\mathrm{N}\bar{k}\mathrm{\leftarrow}\text{ }\mathrm{ocu}\text{ }I\vee\mathrm{N}\bar{k}\mathrm{\neq}\text{ }\mathrm{ocu}\text{ }I\vee\mathrm{P}\bar{k}\mathrm{\leftarrow}\text{ }\mathrm{ocu}\text{ }I\vee\mathrm{P}\bar{k}\mathrm{B}\;\mathrm{ocu}\text{ }I)\\ \#Var2(I) & =\min_{k}(\mathrm{N}\bar{k}\ \text{t-final }I\vee\mathrm{N}\bar{k}\mathrm{+}\text{ }\mathrm{ocu}\text{ }I\vee\mathrm{N}\bar{k}\mathrm{\dot{-}}\text{ }\mathrm{ocu}\text{ }I\vee\mathrm{P}\bar{k}\ \text{t-final }I\vee\mathrm{P}\bar{k}.\text{ }\mathrm{ocu}\text{ }I) \end{aligned}\] Esto nos dice que si llamamos \(P\) al predicado \[\lambda k\alpha\left[\alpha\in\mathrm{Ins}^{\Sigma}\wedge(\mathrm{N}\bar{k}\mathrm{\leftarrow}\text{ }\mathrm{ocu}\text{ }\alpha\vee\mathrm{N}\bar{k}\mathrm{\neq}\text{ }\mathrm{ocu}\text{ }\alpha\vee\mathrm{P}\bar{k}\mathrm{\leftarrow}\text{ }\mathrm{ocu}\text{ }\alpha\vee\mathrm{P}\bar{k}\mathrm{B}\;\mathrm{ocu}\text{ }\alpha)\right]\] entonces \(\lambda I[\#Var1(I)]=M(P)\) por lo cual \(\lambda I[\#Var1(I)]\) es \((\Sigma\cup\Sigma_{p})\)-p.r. Similarmente se puede ver que \(\lambda I[\#Var2(I)]\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Sea \[\begin{array}{rll} F_{\dot{-}}:\mathbf{N}\times\mathbf{N} & \rightarrow & \omega\\ (x,j) & \rightarrow & \left\langle (x)_{1},....,(x)_{j-1},(x)_{j}\dot{-}1,(x)_{j+1},...\right\rangle \end{array}\] Ya que \[F_{\dot{-}}(x,j)=\left\{ \begin{array}{lll} Q(x,pr(j)) & & \text{si }pr(j)\text{ divide }x\\ x & & \text{caso contrario} \end{array}\right.\] tenemos que \(F_{\dot{-}}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Sea \[\begin{array}{rll} F_{+}:\mathbf{N}\times\mathbf{N} & \rightarrow & \omega\\ (x,j) & \rightarrow & \left\langle (x)_{1},....,(x)_{j-1},(x)_{j}+1,(x)_{j+1},...\right\rangle \end{array}\] Ya que \(F_{+}(x,j)=x.pr(j)\) tenemos que \(F_{+}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Sea \[\begin{array}{rll} F_{\leftarrow}:\mathbf{N}\times\mathbf{N}\times\mathbf{N} & \rightarrow & \omega\\ (x,j,k) & \rightarrow & \left\langle (x)_{1},....,(x)_{j-1},(x)_{k},(x)_{j+1},...\right\rangle \end{array}\] Ya que \(F_{\leftarrow}(x,j,k)=Q(x,pr(j)^{(x)_{j}}).pr(j)^{(x)_{k}}\) tenemos que \(F_{\leftarrow}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Sea \[\begin{array}{rll} F_{0}:\mathbf{N}\times\mathbf{N} & \rightarrow & \omega\\ (x,j) & \rightarrow & \left\langle (x)_{1},....,(x)_{j-1},0,(x)_{j+1},...\right\rangle \end{array}\] Es facil ver que \(F_{0}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Para cada \(a\in\Sigma\), sea \[\begin{array}{rll} F_{a}:\mathbf{N}\times\mathbf{N} & \rightarrow & \omega\\ (x,j) & \rightarrow & \left\langle (x)_{1},....,(x)_{j-1},\#^{\leq}(\ast^{\leq}((x)_{j})a),(x)_{j+1},...\right\rangle \end{array}\] Es facil ver que \(F_{a}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. En forma similar puede ser probado que \[\begin{array}{rll} F_{\curvearrowright}:\mathbf{N}\times\mathbf{N} & \rightarrow & \omega\\ (x,j) & \rightarrow & \left\langle (x)_{1},....,(x)_{j-1},\#^{\leq}(^{\curvearrowright}(\ast^{\leq}((x)_{j}))),(x)_{j+1},...\right\rangle \end{array}\] es \((\Sigma\cup\Sigma_{p})\)-p.r.

Dado \((i,x,y,\mathcal{P})\in\omega\times\mathbf{N}\times\mathbf{N}\times\mathrm{Pro}^{\Sigma}\), tenemos varios casos en los cuales los valores \(s(i,x,y,\mathcal{P}),S_{\#}(i,x,y,\mathcal{P})\) y \(S_{\ast}(i,x,y,\mathcal{P})\) pueden ser obtenidos usando las funciones antes definidas:

O sea que los casos anteriores nos permiten definir conjuntos \(S_{1},...,S_{15}\), los cuales son disjuntos de a pares y cuya union da el conjunto \(\omega\times\mathbf{N}\times\mathbf{N}\times\mathrm{Pro}^{\Sigma}\), de manera que cada una de las funciones \(s,S_{\#}\) y \(S_{\ast}\) pueden escribirse como union disjunta de funciones \((\Sigma\cup\Sigma_{p})\)-p.r. restrinjidas respectivamente a los conjuntos \(S_{1},...,S_{15}\). Ya que los conjuntos \(S_{1},...,S_{15}\) son \((\Sigma\cup\Sigma_{p})\)-p.r. el Lema 4.19 nos dice que \(s,S_{\#}\) y \(S_{\ast}\) lo son.

Aparte del lema anterior, para probar que las funciones \(i^{n,m}\), \(E_{\#j}^{n,m}\) y \(E_{\ast j}^{n,m}\) son \((\Sigma\cup\Sigma_{p})\)-p.r., nos sera necesario el siguiente resultado. Recordemos que para \(x_{1},...,x_{n}\in\omega\), usabamos \(\left\langle x_{1},...,x_{n}\right\rangle\) para denotar \(\left\langle x_{1},...,x_{n},0,...\right\rangle\). Ademas recordemos que en el Lema 4.28 probamos que para cada \(n\geq1\), la funcion \(\lambda x_{1}...x_{n}\left[\left\langle x_{1},...,x_{n}\right\rangle \right]\) es \(\emptyset\)-p.r.

4.49. Sean \[\begin{aligned} f_{i} & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\\ g_{i} & :\omega^{k}\times\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\\ F_{i} & :\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega \end{aligned}\] con \(i=1,...,k\), funciones \(\Sigma\)-mixtas. Supongamos que \[\begin{aligned} F_{i}(0,\vec{x},\vec{\alpha}) & =f_{i}(0,\vec{x},\vec{\alpha})\\ F_{i}(t+1,\vec{x},\vec{\alpha}) & =g_{i}(F_{1}(t,\vec{x},\vec{\alpha}),...,F_{k}(t,\vec{x},\vec{\alpha}),t,\vec{x},\vec{\alpha}) \end{aligned}\] para cada \(i=1,...,k\), \(t\in\omega\) y \((\vec{x},\vec{\alpha})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). Entonces si las funciones \(f_{1},...,f_{k},g_{1},...,g_{k}\) son \(\Sigma\)-p.r., las funciones \(F_{1},...,F_{k}\) lo son.

Proof. Para mayor claridad haremos el caso \(k=2\). Sea \[F=\lambda t\vec{x}\vec{\alpha}\left[\left\langle F_{1}(t,\vec{x},\vec{\alpha}),F_{2}(t,\vec{x},\vec{\alpha})\right\rangle \right]\] Es claro que si \(F\) es \(\Sigma\)-p.r., entonces lo es cada \(F_{i}\). Notese que \[\begin{aligned} F(0,\vec{x},\vec{\alpha}) & =\left\langle f_{1}(\vec{x},\vec{\alpha}),f_{2}(\vec{x},\vec{\alpha})\right\rangle \\ F(t+1,\vec{x},\vec{\alpha}) & =\left\langle g_{1}((F(t,\vec{x},\vec{\alpha}))_{1},(F(t,\vec{x},\vec{\alpha}))_{2},t,\vec{x},\vec{\alpha}),g_{2}((F(t,\vec{x},\vec{\alpha}))_{1},(F(t,\vec{x},\vec{\alpha}))_{2},t,\vec{x},\vec{\alpha})\right\rangle \end{aligned}\] lo cual nos dice que \(F=R(f,g)\) donde \[\begin{aligned} f & =\lambda\vec{x}\vec{\alpha}\left[\left\langle f_{1}(\vec{x},\vec{\alpha}),f_{2}(\vec{x},\vec{\alpha})\right\rangle \right]\\ g & =\lambda At\vec{x}\vec{\alpha}\left[\left\langle g_{1}((A)_{1},(A)_{2},t,\vec{x},\vec{\alpha}),g_{2}((A)_{1},(A)_{2},t,\vec{x},\vec{\alpha})\right\rangle \right] \end{aligned}\]

Ahora usando los dos lemas anteriores podemos probar el siguiente importante resultado.

Proof. Sea \(\leq\) un orden total sobre \(\Sigma\cup\Sigma_{p}\) y sean \(s\), \(S_{\#}\) y \(S_{\ast}\) las funciones definidas previamente al Lema 4.48. Definamos \[\begin{aligned} K_{\#}^{n,m} & =\lambda t\vec{x}\vec{\alpha}\mathcal{P}\left[\left\langle E_{\#1}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),E_{\#2}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),...\right\rangle \right]\\ K_{\ast}^{n,m} & =\lambda t\vec{x}\vec{\alpha}\mathcal{P}\left[\left\langle \#^{\leq}(E_{\ast1}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P})),\#^{\leq}(E_{\ast2}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P})),...\right\rangle \right] \end{aligned}\] Notese que \[\begin{aligned} i^{n,m}(0,\vec{x},\vec{\alpha},\mathcal{P}) & =1\\ K_{\#}^{n,m}(0,\vec{x},\vec{\alpha},\mathcal{P}) & =\left\langle x_{1},...,x_{n}\right\rangle \\ K_{\ast}^{n,m}(0,\vec{x},\vec{\alpha},\mathcal{P}) & =\left\langle \#^{\leq}(\alpha_{1}),...,\#^{\leq}(\alpha_{m})\right\rangle \\ i^{n,m}(t+1,\vec{x},\vec{\alpha},\mathcal{P}) & =s(i^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),K_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),K_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}))\\ K_{\#}^{n,m}(t+1,\vec{x},\vec{\alpha},\mathcal{P}) & =S_{\#}(i^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),K_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),K_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}))\\ K_{\ast}^{n,m}(t+1,\vec{x},\vec{\alpha},\mathcal{P}) & =S_{\ast}(i^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),K_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}),K_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P})) \end{aligned}\] Por el Lema 4.49 tenemos que \(i^{n,m}\), \(K_{\#}^{n,m}\) y \(K_{\ast}^{n,m}\) son \((\Sigma\cup\Sigma_{p})\)-p.r.. Ademas notese que \[\begin{aligned} E_{\#j}^{n,m} & =\lambda t\vec{x}\vec{\alpha}\mathcal{P}\left[(K_{\#}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}))_{j}\right]\\ E_{\ast j}^{n,m} & =\lambda t\vec{x}\vec{\alpha}\mathcal{P}\left[\ast^{\leq}((K_{\ast}^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P}))_{j})\right] \end{aligned}\] por lo cual las funciones \(E_{\#j}^{n,m}\), \(E_{\ast j}^{n,m}\), \(j=1,2,...\), son \((\Sigma\cup\Sigma_{p})\)-p.r.

Las funciones \(Halt^{n,m}\) y \(T^{n,m}\).

Dados \(n,m\in\omega\), definamos: \[Halt^{n,m}=\lambda t\vec{x}\vec{\alpha}\mathcal{P}\left[i^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P})=n(\mathcal{P})+1\right]\] Notese que \(D_{Halt^{n,m}}=\omega\times\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\) (ojo que aqui la notacion lambda es respecto del alfabeto \(\Sigma\cup\Sigma_{p}\)). Ademas notese que usamos la variable \(\mathcal{P}\) en la notacion lambda por un tema de comodidad psicologica dado que \(i^{n,m}\) esta definida solo cuando la ultima coordenada es un programa pero podriamos haber escrito \(\lambda t\vec{x}\vec{\alpha}\alpha\left[i^{n,m}(t,\vec{x},\vec{\alpha},\alpha)=n(\alpha)+1\right]\) y sigue siendo la misma funcion.

Cabe destacar que \(Halt^{n,m}\) tiene una descripcion muy intuitiva, ya que dado \((t,\vec{x},\vec{\alpha},\mathcal{P})\in\omega\times\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\), tenemos que \(Halt^{n,m}(t,\vec{x},\vec{\alpha},\mathcal{P})=1\) si y solo si el programa \(\mathcal{P}\) se detiene luego de \(t\) pasos partiendo desde el estado \(\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert\).

4.50. \(Halt^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.

Proof. Notar que \(Halt^{n,m}=\lambda xy[x=y]\circ\left[i^{n,m},\lambda\mathcal{P}[n(\mathcal{P})+1]\circ p_{1+n+m+1}^{1+n,m+1}\right]\).

Ahora definamos \(T^{n,m}=M(Halt^{n,m})\). Notese que \[D_{T^{n,m}}=\{(\vec{x},\vec{\alpha},\mathcal{P}):\mathcal{P}\text{ se detiene partiendo de }\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert \}\] y para \((\vec{x},\vec{\alpha},\mathcal{P})\in D_{T^{n,m}}\) tenemos que \(T^{n,m}(\vec{x},\vec{\alpha},\mathcal{P})=\) cantidad de pasos necesarios para que \(\mathcal{P}\) se detenga partiendo de \(\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert\). En algun sentido, la funcion \(T^{n,m}\) mide el tiempo que tarda en detenerse \(\mathcal{P}\)

Proof. Es directo del Lema 4.25 ya que \(Halt^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.

Las funciones \(\Phi_{\#}^{n,m}\) y \(\Phi_{\ast}^{n,m}\).

Para \(n,m\in\omega\) definamos la funcion \(\Phi_{\#}^{n,m}\) de la siguiente manera: \[\begin{aligned} D_{\Phi_{\#}^{n,m}} & =\left\{ (\vec{x},\vec{\alpha},\mathcal{P})\in\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}:(\vec{x},\vec{\alpha})\in D_{\Psi_{\mathcal{P}}^{n,m,\#}}\right\} \\ \Phi_{\#}^{n,m}(\vec{x},\vec{\alpha},\mathcal{P}) & =\Psi_{\mathcal{P}}^{n,m,\#}(\vec{x},\vec{\alpha})\text{, para cada }(\vec{x},\vec{\alpha},\mathcal{P})\in D_{\Phi_{\#}^{n,m}} \end{aligned}\] Notese que \[D_{\Phi_{\#}^{n,m}}=\{(\vec{x},\vec{\alpha},\mathcal{P}):\mathcal{P}\text{ se detiene partiendo de }\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert \}\] y para cada \((\vec{x},\vec{\alpha},\mathcal{P})\in D_{\Phi_{\#}^{n,m}}\), se tiene que \(\Phi_{\#}^{n,m}(\vec{x},\vec{\alpha},\mathcal{P})=\) valor que queda en la variable \(\mathrm{N}1\) cuando \(\mathcal{P}\) se detiene partiendo de \(\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert\).

Similarmente, definamos la funcion \(\Phi_{\ast}^{n,m}\) de la siguiente manera: \[\begin{aligned} D_{\Phi_{\ast}^{n,m}} & =\left\{ (\vec{x},\vec{\alpha},\mathcal{P})\in\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}:(\vec{x},\vec{\alpha})\in D_{\Psi_{\mathcal{P}}^{n,m,\ast}}\right\} \\ \Phi_{\ast}^{n,m}(\vec{x},\vec{\alpha},\mathcal{P}) & =\Psi_{\mathcal{P}}^{n,m,\ast}(\vec{x},\vec{\alpha})\text{, para cada }(\vec{x},\vec{\alpha},\mathcal{P})\in D_{\Phi_{\ast}^{n,m}} \end{aligned}\] Notese que \[\begin{aligned} \Phi_{\#}^{n,m} & =\lambda\vec{x}\vec{\alpha}\mathcal{P}\left[\Psi_{\mathcal{P}}^{n,m,\#}(\vec{x},\vec{\alpha})\right]\\ \Phi_{\ast}^{n,m} & =\lambda\vec{x}\vec{\alpha}\mathcal{P}\left[\Psi_{\mathcal{P}}^{n,m,\ast}(\vec{x},\vec{\alpha})\right] \end{aligned}\]

Proof. Veremos que \(\Phi_{\#}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-recursiva. Notar que \(D_{T^{n,m}}=D_{\Phi_{\#}^{n,m}}\). Notese que para \((\vec{x},\vec{\alpha},\mathcal{P})\in D_{T^{n,m}}=D_{\Phi_{\#}^{n,m}}\) tenemos que \[\Phi_{\#}^{n,m}(\vec{x},\vec{\alpha},\mathcal{P})=E_{\#1}^{n,m}\left(T^{n,m}(\vec{x},\vec{\alpha},\mathcal{P}),\vec{x},\vec{\alpha},\mathcal{P}\right)\] lo cual con un poco mas de trabajo nos permite probar que \[\Phi_{\#}^{n,m}=E_{\#1}^{n,m}\circ\left[T^{n,m},p_{1}^{n,m+1},...,p_{n+m+1}^{n,m+1}\right]\] Ya que la funcion \(E_{\#1}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. y \(T^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-r., tenemos que \(\Phi_{\#}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-r.

4.4.2.3 Godel vence a Neumann

Ahora nos sera facil probar que el paradigma de Godel es por lo menos tan abarcativo como el imperativo de Von Neumann. Mas concretamente:

Proof. Haremos el caso \(O=\Sigma^{\ast}\). Sea \(\mathcal{P}_{0}\) un programa que compute a \(f\). Primero veremos que \(f\) es \((\Sigma\cup\Sigma_{p})\)-recursiva. Note que \[f=\Phi_{\ast}^{n,m}\circ\left[p_{1}^{n,m},...,p_{n+m}^{n,m},C_{\mathcal{P}_{0}}^{n,m}\right]\] donde cabe destacar que \(p_{1}^{n,m},...,p_{n+m}^{n,m}\) son las proyecciones respecto del alfabeto \(\Sigma\cup\Sigma_{p}\), es decir que tienen dominio \(\omega^{n}\times(\Sigma\cup\Sigma_{p})^{\ast m}\). Ya que \(\Phi_{\ast}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-recursiva tenemos que \(f\) lo es. O sea que el Teorema 4.2 nos dice que \(f\) es \(\Sigma\)-recursiva.

Un corolario interesante que se puede obtener del teorema anterior es que toda funcion \(\Sigma\)-recursiva puede obtenerse combinando las reglas basicas en una forma muy particular.

4.4 (Forma Normal de Kleene). Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) es \(\Sigma\)-recursiva, entonces existe un predicado \(\Sigma\)-p.r. \(P:\mathbf{N}\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y una funcion \(\Sigma\)-p.r. \(g:\mathbf{N}\rightarrow O\) tales que \(f=g\circ M(P).\)

Proof. Supongamos que \(O=\Sigma^{\ast}\). Sea \(\mathcal{P}_{0}\) un programa el cual compute a \(f\). Sea \(\leq\) un orden total sobre \(\Sigma\). Note que podemos tomar \[\begin{aligned} P & =\lambda t\vec{x}\vec{\alpha}[Halt^{n,m}\left((t)_{1},\vec{x},\vec{\alpha},\mathcal{P}_{0}\right)\wedge(t)_{2}=\#^{\leq}(E_{\ast1}^{n,m}((t)_{1},\vec{x},\vec{\alpha},\mathcal{P}_{0}))]\\ g & =\lambda t\left[\ast^{\leq}((t)_{2})\right] \end{aligned}\] (Justifique por que \(P\) es \(\Sigma\)-p.r..)

A continuacion veremos ejemplos naturales de funciones \((\Sigma\cup\Sigma_{p})\)-recursivas que no son \((\Sigma\cup\Sigma_{p})\)-recursivas primitivas. Cabe destacar que la prueba se basa en la Proposicion 4.6 (enunciada sin demostracion) la cual nos dice que cualquiera sea el alfabeto finito \(\Sigma\), siempre hay una funcion que es \(\Sigma\)-recursiva y no es \(\Sigma\)-recursiva primitiva.

Proof. Fijemos \(n,m\in\omega\). Probaremos que \(\Phi_{\#}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. sii \(\Phi_{\#}^{0,0}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Sean \(f_{1},f_{2}:\omega^{n}\times\Sigma^{\ast m}\rightarrow(\Sigma\cup\Sigma_{p})^{\ast}\) dadas por \[\begin{aligned} f_{1}(\vec{x},\vec{\alpha}) & =(\mathrm{N}1\leftarrow\mathrm{N}1+1)^{x_{1}}...(\mathrm{N}\bar{n}\leftarrow\mathrm{N}\bar{n}+1)^{x_{n}}\\ f_{1}(\vec{x},\vec{\alpha}) & =\left(\subset_{i=1}^{i=\left\vert \alpha_{1}\right\vert }\mathrm{P}1\leftarrow\mathrm{P}1.[\alpha_{1}]_{i}\right)...\left(\subset_{i=1}^{i=\left\vert \alpha_{m}\right\vert }\mathrm{P}1\leftarrow\mathrm{P}1.[\alpha_{m}]_{i}\right) \end{aligned}\] Sea \(f:\omega^{n}\times\Sigma^{\ast m}\times\mathrm{Pro}^{\Sigma}\rightarrow(\Sigma\cup\Sigma_{p})^{\ast}\) dada por \[f(\vec{x},\vec{\alpha},\mathcal{P})=f_{1}(\vec{x},\vec{\alpha})f_{1}(\vec{x},\vec{\alpha})\mathcal{P}\] Es facil ver que \(f\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Notese que \(\Phi_{\#}^{n,m}=\Phi_{\#}^{0,0}\circ f\). Ademas notese que \[\Phi_{\#}^{0,0}=\Phi_{\#}^{n,m}\circ\left[C_{0}^{0,1},...,C_{0}^{0,1},C_{\varepsilon}^{0,1},...,C_{\varepsilon}^{0,1},p_{1}^{0,1}\right]\] Ya que \(f\) y las funciones \(C_{0}^{0,1},C_{\varepsilon}^{0,1},p_{1}^{0,1}\) son \((\Sigma\cup\Sigma_{p})\)-p.r., tenemos que \(\Phi_{\#}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. sii \(\Phi_{\#}^{0,0}\) lo es.

Supongamos ahora que para algunos \(k,l\in\omega\) se tiene que \(\Phi_{\#}^{k,l}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Llegaremos a un absurdo. Por lo antes probado tenemos que \(\Phi_{\#}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r., cualesquiera sean \(n,m\in\omega\). Notese que de la prueba del teorema anterior sigue que toda funcion \(\Sigma\)-computable con imagen contenida en \(\omega\) es de la forma \(\Phi_{\#}^{n,m}\circ\left[p_{1}^{n,m},...,p_{n+m}^{n,m},C_{\mathcal{P}_{0}}^{n,m}\right]\), para algunos \(n,m\in\omega\) y \(\mathcal{P}_{0}\in\mathrm{Pro}^{\Sigma}\). Pero entonces toda funcion \(\Sigma\)-computable con imagen contenida en \(\omega\) es \((\Sigma\cup\Sigma_{p})\)-p.r., lo cual por la batalla Neumann vence a Godel nos dice que toda funcion \(\Sigma\)-recursiva con imagen contenida en \(\omega\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Por el Teorema de Independencia del Alfabeto tenemos que toda funcion \(\Sigma\)-recursiva con imagen contenida en \(\omega\) es \(\Sigma)\)-p.r., lo cual contradice la Proposicion 4.6.

Ahora supongamos que hay \(n,m\in\omega\) tales que \(T^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Llegaremos a un absurdo. Como ya vimos en la prueba de un teorema reciente, se tiene que \[\Phi_{\#}^{n,m}=E_{\#1}^{n,m}\circ\left[T^{n,m},p_{1}^{n,m+1},...,p_{n+m+1}^{n,m+1}\right]\] Pero entonces ya que \(E_{\#1}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r., tenemos que \(\Phi_{\#}^{n,m}\) es \((\Sigma\cup\Sigma_{p})\)-p.r., lo cual como ya vimos recien no es cierto. El absurdo nos dice que \(T^{n,m}\) no es \((\Sigma\cup\Sigma_{p})\)-p.r..

4.4.2.4 Uso de macros asociados a las funciones \(Halt^{n,m}\), \(E_{\#}^{n,m}\) y \(E_{\ast}^{n,m}\)

Aqui veremos, con ejemplos, como ciertos macros nos permitiran dentro de un programa hablar acerca del funcionamiento de otro programa. En este sentido los desarrollos de las dos batallas entre Neumann y Godel nos permiten fortalecer notablemente al paradigma imperativo en su roll modelizador (o simulador) de los procedimientos efectivos. Esto es importante ya que el paradigma mas comodo, amplio e intuitivo es sin duda el filosofico de Leibniz.

Notese que \(0\in S\) por lo cual \(S\) es no vacio asique en virtud de la Caracterizacion de \(\Sigma\)-enumerabilidad deberemos encontrar un programa \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) que enumere a \(S\), es decir tal que \(\mathrm{Dom}\Psi_{\mathcal{P}}^{1,0,\#}=\omega\) y \(\mathrm{Im}\Psi_{\mathcal{P}}^{1,0,\#}=S\). Dicho en palabras, el programa \(\mathcal{P}\) debera cumplir:

Sea \(\mathcal{P}_{0}\in\mathrm{Pro}^{\Sigma}\) un programa que compute a \(f\). Usaremos \(\mathcal{P}_{0}\) para diseñar \(\mathcal{P}\). A continuacion daremos una descripcion intuitiva del funcionamiento de \(\mathcal{P}\) (pseudocodigo) para luego escribirlo correctamente usando macros. El programa \(\mathcal{P}\) comenzara del estado \(\left\Vert x\right\Vert\) y hara las siguientes tareas

Notese que la descripcion anterior no es ni mas ni menos que un procedimiento efectivo (efectivisable) que enumera a \(S\), y nuestra mision es simularlo dentro del lenguaje \(\mathcal{S}^{\Sigma}\). Para esto usaremos varios macros. Ya que la funcion \(f=\lambda x[(x)_{1}]\) es \(\Sigma\)-p.r., el Segundo Manantial de Macros nos dice que hay un macro: \[[\mathrm{V}2\leftarrow f(\mathrm{V}1)]\] el cual escribiremos de la siguiente manera mas intuitiva: \[[\mathrm{V}2\leftarrow(\mathrm{V}1)_{1}]\] Similarmente hay un macro: \[[\mathrm{V}2\leftarrow(\mathrm{V}1)_{2}]\] Tambien, ya que el predicado \(P=\lambda x[x=0]\) es \(\Sigma\)-recursivo, hay un macro: \[\left[\mathrm{IF}\;P(\mathrm{V}1)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] el cual escribiremos de la siguiente manera: \[\left[\mathrm{IF}\;\mathrm{V}1=0\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Definamos \[H=\lambda tx\left[Halt^{1,0}(t,x,\mathcal{P}_{0})\right]\] Notar que \(D_{H}=\omega^{2}\) y que \(H\) es \(\Sigma\)-mixta. Ademas sabemos que la funcion \(Halt^{1,0}\) es \((\Sigma\cup\Sigma_{p})\)-p.r. por lo cual resulta facilmente que \(H\) es \((\Sigma\cup\Sigma_{p})\)-p.r.. Por Independencia del Alfabeto tenemos que \(H\) es \(\Sigma\)-p.r.. O sea que el Segundo Manatial nos dice que hay un macro de \(\mathcal{S}^{\Sigma}\): \[\left[\mathrm{IF}\;H(\mathrm{V}1,\mathrm{V}2)\;\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,0}(\mathrm{V}1,\mathrm{V}2,\mathcal{P}_{0})\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Sea \[g=\lambda tx\left[E_{\#1}^{1,0}(t,x,\mathcal{P}_{0})\right]\] Ya que \(g\) es \(\Sigma\)-recursiva (por que?), hay un macro: \[\left[\mathrm{V}3\leftarrow g(\mathrm{V}1,\mathrm{V}2)\right]\] Para hacer mas intuitivo el uso de este macro lo escribiremos de la siguiente manera \[\left[\mathrm{V}3\leftarrow E_{\#1}^{1,0}(\mathrm{V}1,\mathrm{V}2,\mathcal{P}_{0})\right]\] Ahora si podemos dar nuestro programa \(\mathcal{P}\) que enumera a \(S\): \[\begin{array}{ll} & \mathrm{IF}\;\mathrm{N}1\neq0\;\mathrm{GOTO}\;\mathrm{L}1\\ & \mathrm{GOTO}\;\mathrm{L}2\\ \mathrm{L}1 & [\mathrm{N}3\leftarrow(\mathrm{N}1)_{1}]\\ & [\mathrm{N}4\leftarrow(\mathrm{N}1)_{2}]\\ & \left[\mathrm{IF}\;Halt^{1,0}(\mathrm{N}4,\mathrm{N}3,\mathcal{P}_{0})\;\mathrm{GOTO}\;\mathrm{L}3\right]\\ & \mathrm{GOTO}\;\mathrm{L}2\\ \mathrm{L}3 & \left[\mathrm{N}5\leftarrow E_{\#1}^{1,0}(\mathrm{N}4,\mathrm{N}3,\mathcal{P}_{0})\right]\\ & [\mathrm{IF}\;\mathrm{N}5=0\;\mathrm{GOTO}\;\mathrm{L}2]\\ & \mathrm{N}1\leftarrow\mathrm{N}3\\ & \mathrm{GOTO}\;\mathrm{L}4\\ \mathrm{L}2 & \mathrm{N}1\leftarrow0\\ \mathrm{L}4 & \mathrm{SKIP} \end{array}\]

Enumeracion de conjuntos de programas

Ya que los programas de \(\mathcal{S}^{\Sigma}\) son palabras del alfabeto \(\Sigma\cup\Sigma_{p}\), nos podemos preguntar cuando un conjunto \(L\) de programas es \((\Sigma\cup\Sigma_{p})\)-enumerable. Daremos un ejemplo. Sea \(\Sigma=\{@,!\}\) y sea \[L=\{\mathcal{P}\in\mathrm{Pro}^{\Sigma}:\Psi_{\mathcal{P}}^{1,0,\#}(10)=10\}\] Veremos que \(L\) es \((\Sigma\cup\Sigma_{p})\)-enumerable, dando un programa \(\mathcal{Q}\in\mathrm{Pro}^{\Sigma\cup\Sigma_{p}}\) que enumere a \(L\), es decir tal que Dom\((\Psi_{\mathcal{Q}}^{1,0,\ast})=\omega\) y \(\mathrm{Im}(\Psi_{\mathcal{Q}}^{1,0,\ast})=L\). Cabe destacar que aqui hay en juego dos versiones de nuestro lenguaje imperativo, es decir enumeraremos un conjunto de programas de \(\mathcal{S}^{\Sigma}\) usando un programa de \(\mathcal{S}^{\Sigma\cup\Sigma_{p}}\). Sea \(\leq\) un orden total sobre el conjunto \(\Sigma\cup\Sigma_{p}\).

A continuacion daremos una descripcion intuitiva del funcionamiento de \(\mathcal{Q}\) (pseudocodigo) para luego escribirlo correctamente usando macros. Notese que \(\mathrm{SKIP}\in L\). El programa \(\mathcal{Q}\) comenzara del estado \(\left\Vert x\right\Vert\) y hara las siguientes tareas

Notese que la descripcion anterior no es ni mas ni menos que un procedimiento efectivo que enumera a \(L\), y nuestra mision es simularlo dentro del lenguaje \(\mathcal{S}^{\Sigma\cup\Sigma_{p}}\). Para esto usaremos varios macros. Es importante notar que los macros que usaremos corresponden al lenguaje \(\mathcal{S}^{\Sigma\cup\Sigma_{p}}\) ya que los usaremos en \(\mathcal{Q}\) el cual sera un programa de \(\mathcal{S}^{\Sigma\cup\Sigma_{p}}\).

Ya que las funciones \(\lambda x[(x)_{1}]\) y \(\lambda x[(x)_{2}]\) son \((\Sigma\cup\Sigma_{p})\)-recursivas el Segundo Manantial nos dice que hay macros en \(\mathcal{S}^{\Sigma\cup\Sigma_{p}}\) asociados a estas funciones los cuales escribiremos de la siguiente manera mas intuitiva: \[\begin{aligned} \\{} [\mathrm{V}2 & \leftarrow(\mathrm{V}1)_{2}] \end{aligned}\] Ya que el predicado \(P=\lambda x[x=10]\) es \((\Sigma\cup\Sigma_{p})\)-recursivo tenemos en \(\mathcal{S}^{\Sigma\cup\Sigma_{p}}\) su macro asociado el cual escribiremos de la siguiente manera: \[\left[\mathrm{IF}\;\mathrm{V}1=10\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Por un lema anterior sabemos que \(\mathrm{Pro}^{\Sigma}\) es un conjunto \((\Sigma\cup\Sigma_{p})\)-p.r., por lo cual \(\chi_{\mathrm{Pro}^{\Sigma}}^{(\Sigma\cup\Sigma_{p})^{\ast}}\) es \((\Sigma\cup\Sigma_{p})\)-p.r., y por lo tanto hay un macro \[\left[\mathrm{IF}\;\chi_{\mathrm{Pro}^{\Sigma}}^{(\Sigma\cup\Sigma_{p})^{\ast}}(\mathrm{W}1)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] el cual escribiremos de la siguiente manera \[\left[\mathrm{IF}\;\mathrm{W}1\in\mathrm{Pro}^{\Sigma}\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Ya que el predicado \(Halt^{1,0}\) es \((\Sigma\cup\Sigma_{p})\)-recursivo tenemos un macro asociado a el, el cual escribiremos de la siguiente forma \[\left[\mathrm{IF}\;Halt^{1,0}(\mathrm{V}1,\mathrm{V}2,\mathrm{W}1)\;\mathrm{GOTO}\;\mathrm{A}1\right]\] Ya que \(E_{\#1}^{1,0}\) es \((\Sigma\cup\Sigma_{p})\)-recursivo tenemos un macro asociado a ella, el cual escribiremos de la siguiente forma \[\left[\mathrm{V}3\leftarrow E_{\#1}^{1,0}(\mathrm{V}1,\mathrm{V}2,\mathrm{W}1)\right]\] Tambien usaremos macros \[\begin{gathered} \\ \left[\mathrm{W}1\leftarrow\mathrm{SKIP}\right] \end{gathered}\] (dejamos al lector hacerlos a mano o tambien se puede justificar su existencia via el Segundo Manantial aplicado a las funciones \(C_{10}^{0,0}\) y \(C_{\mathrm{SKIP}}^{0,0}\)).

Ahora si podemos hacer el programa \(\mathcal{Q}\) de \(\mathcal{S}^{\Sigma\cup\Sigma_{p}}\) que enumera a \(L\): \[\begin{array}{ll} & \mathrm{IF}\;\mathrm{N}1\neq0\;\mathrm{GOTO}\;\mathrm{L}1\\ & \mathrm{GOTO}\;\mathrm{L}2\\ \mathrm{L}1 & [\mathrm{N}2\leftarrow(\mathrm{N}1)_{1}]\\ & [\mathrm{N}3\leftarrow(\mathrm{N}1)_{2}]\\ & [\mathrm{P}1\leftarrow\ast^{\leq}(\mathrm{N}2)]\\ & \left[\mathrm{IF}\;\mathrm{P}1\in\mathrm{Pro}^{\Sigma}\;\mathrm{GOTO}\;\mathrm{L}3\right]\\ & \mathrm{GOTO}\;\mathrm{L}2\\ \mathrm{L}3 & [\mathrm{N}4\leftarrow10]\\ & \left[\mathrm{IF}\;Halt^{1,0}(\mathrm{N}3,\mathrm{N}4,\mathrm{P}1)\;\mathrm{GOTO}\;\mathrm{L}4\right]\\ & \mathrm{GOTO}\;\mathrm{L}2\\ \mathrm{L}4 & \left[\mathrm{N}5\leftarrow E_{\#1}^{1,0}(\mathrm{N}3,\mathrm{N}4,\mathrm{P}1)\right]\\ & [\mathrm{IF}\;\mathrm{N}5=10\;\mathrm{GOTO}\;\mathrm{L}5]\\ \mathrm{L}2 & \left[\mathrm{P}1\leftarrow\mathrm{SKIP}\right]\\ \mathrm{L}5 & \mathrm{SKIP} \end{array}\]

Cuando \(\Sigma\supseteq\Sigma_{p}\) la cosa se pone mas loca.

Cuando \(\Sigma\supseteq\Sigma_{p}\) podemos correr un programa \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) partiendo de un estado que asigne a sus variables alfabeticas programas (ya que los programas son meras palabras de \(\Sigma^{\ast}\)). En particular podriamos correr un programa \(\mathcal{P}\) desde el estado \(\left\Vert \mathcal{P}\right\Vert\). Llamaremos \(A\) al conjunto formado por aquellos programas \(\mathcal{P}\) tales que \(\mathcal{P}\) se detiene partiendo del estado \(\left\Vert \mathcal{P}\right\Vert\). Es decir \[A=\{\mathcal{P}\in\mathrm{Pro}^{\Sigma}:\exists t\in\omega\text{ tal que }Halt^{0,1}(t,\mathcal{P},\mathcal{P})=1\}\] Por ejemplo \(\mathrm{SKIP}\in A\). Dicho rapida y sugestivamente \(A\) es el conjunto formado por aquellos programas que se detienen partiendo de si mismos. Dejamos al lector hacer un programa que enumere a \(A\). Como veremos mas adelante este conjunto, si bien es \(\Sigma\)-enumerable, no es \(\Sigma\)-computable.

Ahora consiremos el conjunto \[L=\{\mathcal{P}\in\mathrm{Pro}^{\Sigma}:\Psi_{\mathcal{P}}^{0,0,*}(\lozenge)=\mathcal{P}\}\] En palabras, un programa \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) estara en \(L\) si y solo si \(\mathcal{P}\) termina desde \(((0,0,...),(\varepsilon,\varepsilon,...))\) dejando en \(\mathrm{P}1\) la palabra \(\mathcal{P}\). En algun sentido los elementos de \(L\) son programas que se autopropagandean ya que “de la nada ellos terminan dandose a si mismos como salida”. Dejamos al lector la tarea de reflexionar hasta entender que resulta dificil encontrar “a mano” un elemento de \(L\). En algun sentido, para lograr hacer un programa que este en \(L\) debemos ir escribiendo instrucciones que a su ves vayan garantizando que ellas mismas vayan quedando en el contenido de la variable \(\mathrm{P}1\). Sin embargo el Teorema de la Recursion (de Kleene) nos garantiza que \(L\) es no vacio! Dejamos al lector la tarea de hacer un programa que enumere a \(L\) (obviamente utilizando un elemento fijo de \(L\)).

Consideremos ahora el conjunto \[S=\{(\mathcal{P}_{1},\mathcal{P}_{2})\in\mathrm{Pro}^{\Sigma}\times\mathrm{Pro}^{\Sigma}:\Psi_{\mathcal{P}_{1}}^{0,0,\ast}(\lozenge)=\mathcal{P}_{1}\mathcal{P}_{2}=\Psi_{\mathcal{P}_{2}}^{0,0,\ast}(\lozenge)\}\] Note que nuevamente es dificil imaginar como uno programaria un par de programas \(\mathcal{P}_{1}\text{ y }\mathcal{P}_{2}\) de manera que \((\mathcal{P}_{1},\mathcal{P}_{2})\) este en \(S\). El Teorema de la Recursion Doble (de Smullyan) nos garantiza que \(S\) es no vacio! Dejamos al lector la tarea de hacer un programa que enumere a \(L\) (obviamente utilizando un elemento fijo de \(S\)).

4.4.3 Godel vence a Turing

Para probar que toda funcion \(\Sigma\)-Turing computable es \(\Sigma\)-recursiva debemos estudiar la recursividad del funcionamiento de las maquinas de Turing. Cabe destacar que tal como se lo explico en la Subseccion [BasicosMaquinasDeTuring] supondremos siempre que el conjunto de estados de una maquina de Turing \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,F\right)\) es un alfabeto disjunto con \(\Gamma\).

4.51. Sea \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,F\right)\) una maquina de Turing. Entonces

adhocprefix(1)adhocsufix \(Des\) es un conjunto \((\Gamma\cup Q)\)-p.r.
adhocprefix(2)adhocsufix \(St:Des\rightarrow Q\) es una funcion \((\Gamma\cup Q)\)-p.r.

Notese que la funcion \(\delta\) de una maquina de Turing \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,F\right)\) no es \((\Gamma\cup Q)\)-mixta. Sin envargo los siguientes predicados \((\Gamma\cup Q)\)-mixtos contienen toda la informacion de \(\delta\): \[\begin{array}{rcl} P_{L}:Q\times\Gamma\times Q\times\Gamma & \rightarrow & \omega\\ (p,\sigma,q,\gamma) & \rightarrow & \left\{ \begin{array}{ccl} 1 & & \text{si }\delta(q,\gamma)=(p,\sigma,L)\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] \[\begin{array}{rcl} P_{L}:Q\times\Gamma\times Q\times\Gamma & \rightarrow & \omega\\ (p,\sigma,q,\gamma) & \rightarrow & \left\{ \begin{array}{ccl} 1 & & \text{si }(p,\sigma,L)\in\delta(q,\gamma)\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] \[\begin{array}{rcl} P_{R}:Q\times\Gamma\times Q\times\Gamma & \rightarrow & \omega\\ (p,\sigma,q,\gamma) & \rightarrow & \left\{ \begin{array}{ccl} 1 & & \text{si }\delta(q,\gamma)=(p,\sigma,R)\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] \[\begin{array}{rcl} P_{K}:Q\times\Gamma\times Q\times\Gamma & \rightarrow & \omega\\ (p,\sigma,q,\gamma) & \rightarrow & \left\{ \begin{array}{ccl} 1 & & \text{si }\delta(q,\gamma)=(p,\sigma,K)\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\]

4.52. Sea \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,F\right)\) una maquina de Turing. Entonces los predicados \(P_{L},P_{R}\) y \(P_{K}\) son \((\Gamma\cup Q)\)-p.r.

Proof. Ya que los tres predicados tienen dominio finito, el Corolario 4.2 nos dice que son \((\Gamma\cup Q)\)-p.r.

Recordemos que dado \(\alpha\in(Q\cup\Gamma)^{\ast}\), definimos \(\left\lfloor \alpha\right\rfloor\) de la siguiente manera \[\begin{aligned} \left\lfloor \varepsilon\right\rfloor & =\varepsilon\\ \left\lfloor \alpha\sigma\right\rfloor & =\alpha\sigma\text{, si }\sigma\neq B\\ \left\lfloor \alpha B\right\rfloor & =\left\lfloor \alpha\right\rfloor \end{aligned}\] Es decir \(\left\lfloor \alpha\right\rfloor\) es el resultado de remover de \(\alpha\) el tramo final mas grande de la forma \(B^{n}\).

Tambien dada cualquier palabra \(\alpha\) definimos \[\begin{aligned} ^{\curvearrowright}\alpha & =\left\{ \begin{array}{lll} \left[\alpha\right]_{2}...\left[\alpha\right]_{\left\vert \alpha\right\vert } & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right.\\ \alpha^{\curvearrowleft} & =\left\{ \begin{array}{lll} \left[\alpha\right]_{1}...\left[\alpha\right]_{\left\vert \alpha\right\vert -1} & \text{si} & \left\vert \alpha\right\vert \geq2\\ \varepsilon & \text{si} & \left\vert \alpha\right\vert \leq1 \end{array}\right. \end{aligned}\]

4.53. Las funciones \(\lambda\alpha[\left\lfloor \alpha\right\rfloor ]\), \(\lambda\alpha[^{\curvearrowright}\alpha]\) y \(\lambda\alpha[\alpha^{\curvearrowleft}]\) son \((\Gamma\cup Q)\)-p.r.. (Notar que la notacion \(\lambda\) aqui es respecto del alfabeto \(\Gamma\cup Q\) por lo cual las tres funciones tienen dominio igual a \((\Gamma\cup Q)^{\ast}\).)

Notese que dada una maquina de Turing \(M\), la expresion \(d\underset{M}{\vdash}d^{\prime}\) fue definida solo en el caso en que \(d\) y \(d^{\prime}\) son descripciones instantaneas. Es decir que el predicado \(\lambda dd^{\prime}\left[d\vdash d^{\prime}\right]\) tiene dominio igual a \(Des\times Des\).

4.54. El predicado \(\lambda dd^{\prime}\left[d\underset{M}{\vdash}d^{\prime}\right]\) es \((\Gamma\cup Q)\)-p.r..

Proof. Sea \(\tilde{P}_{L}:Des\times Des\times\Gamma\times\Gamma^{\ast}\times\Gamma^{\ast}\times Q\times Q\rightarrow\omega\) definido por \(\tilde{P}_{L}(d,d^{\prime},\sigma,\alpha,\beta,p,q)=1\) sii \[d=\alpha p\beta\wedge(q,\sigma,L)=\delta\left(p,\left[\beta B\right]_{1}\right)\wedge\alpha\neq\varepsilon\wedge d^{\prime}=\left\lfloor \alpha^{\curvearrowleft}q\left[\alpha\right]_{\left\vert \alpha\right\vert }\sigma^{\curvearrowright}\beta\right\rfloor\] Sea \(\tilde{P}_{R}:Des\times Des\times\Gamma\times\Gamma^{\ast}\times\Gamma^{\ast}\times Q\times Q\rightarrow\omega\) definido por \(\tilde{P}_{R}(d,d^{\prime},\sigma,\alpha,\beta,p,q)=1\) sii \[d=\alpha p\beta\wedge(q,\sigma,R)=\delta\left(p,\left[\beta B\right]_{1}\right)\wedge d^{\prime}=\alpha\sigma q^{\curvearrowright}\beta\] Sea \(\tilde{P}_{K}:Des\times Des\times\Gamma\times\Gamma^{\ast}\times\Gamma^{\ast}\times Q\times Q\rightarrow\omega\) definido por \(\tilde{P}_{K}(d,d^{\prime},\sigma,\alpha,\beta,p,q)=1\) sii \[d=\alpha p\beta\wedge(q,\sigma,K)=\delta\left(p,\left[\beta B\right]_{1}\right)\wedge d^{\prime}=\left\lfloor \alpha q\sigma^{\curvearrowright}\beta\right\rfloor\] Se deja al lector la verificacion de que estos predicados son \((\Gamma\cup Q)\)-p.r.. Notese que \(\lambda dd^{\prime}\left[d\underset{M}{\vdash}d^{\prime}\right]\) es igual al predicado \[\lambda dd^{\prime}\left[(\exists\sigma\in\Gamma)(\exists\alpha,\beta\in\Gamma^{\ast})(\exists p,q\in Q)(\tilde{P}_{R}\vee\tilde{P}_{L}\vee\tilde{P}_{K})(d,d^{\prime},\sigma,\alpha,\beta,p,q)\right]\] lo cual por el Lema 4.22 nos dice que \(\lambda dd^{\prime}\left[d\underset{M}{\vdash}d^{\prime}\right]\) es \((\Gamma\cup Q)\)-p.r.

Proof. Sea \(Q=\lambda dd^{\prime}\left[d\underset{M}{\vdash}d^{\prime}\right]\cup C_{0}^{0,2}|_{(\Gamma\cup Q)^{\ast2}-Des^{2}}\) es decir \(Q\) es el resultado de extender con el valor \(0\) al predicado \(\lambda dd^{\prime}\left[d\underset{M}{\vdash}d^{\prime}\right]\) de manera que este definido en todo \((\Gamma\cup Q)^{\ast2}\). Sea \(\leq\) un orden total sobre \(\Gamma\cup Q\) y sea \(Q_{1}:\mathbf{N}\times Des\times Des\rightarrow\omega\) definido por \(Q_{1}(x,d,d^{\prime})=1\) sii

\(\left((\forall i\in\mathbf{N})_{i\leq Lt(x)}\ast^{\leq}((x)_{i})\in Des\right)\wedge\ast^{\leq}((x)_{1})=d\wedge\)

\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ast^{\leq}((x)_{Lt(x)})=d^{\prime}\wedge\left((\forall i\in\mathbf{N})_{i\leq Lt(x)\dot{-}1}\;Q(\ast^{\leq}((x)_{i}),\ast^{\leq}((x)_{i+1}))\right)\)

Notese que dicho rapidamente \(Q_{1}(x,d,d^{\prime})=1\) sii \(x\) codifica una computacion que parte de \(d\) y llega a \(d^{\prime}\). Se deja al lector la verificacion de que este predicado es \((\Gamma\cup Q)\)-p.r.. Notese que \[\lambda ndd^{\prime}\left[d\underset{M}{\overset{n}{\vdash}}d^{\prime}\right]=\lambda ndd^{\prime}\left[\left(\exists x\in\mathbf{N}\right)\;Lt(x)=n+1\wedge Q_{1}(x,d,d^{\prime})\right]\] Es decir que solo nos falta acotar el cuantificador existencial, para poder aplicar el lema de cuantificacion acotada. Ya que cuando \(d_{1},...,d_{n+1}\in Des\) son tales que \(d_{1}\underset{M}{\vdash}d_{2}\underset{M}{\vdash}\cdots\underset{M}{\vdash}d_{n+1}\) tenemos que \[\left\vert d_{i}\right\vert \leq\left\vert d_{1}\right\vert +n\text{, para }i=1,...,n\] una posible cota para dicho cuantificador es \[\prod_{i=1}^{n+1}pr(i)^{\left\vert \Gamma\cup Q\right\vert ^{\left\vert d\right\vert +n}}\text{.}\] O sea que, por el lema de cuantificacion acotada, tenemos que el predicado \(\lambda ndd^{\prime}\left[d\underset{M}{\overset{n}{\vdash}}d^{\prime}\right]\) es \((\Gamma\cup Q)\)-p.r.

Proof. Supongamos \(O=\Sigma^{\ast}\) y sea \(M=\left(Q,\Sigma,\Gamma,\delta,q_{0},B,\shortmid,F\right)\) una maquina de Turing con unit la cual compute a \(f\). Sea \(\leq\) un orden total sobre \(\Sigma\). Notese que por el Teorema 4.2, la funcion \(\ast^{\leq}\) es \((\Gamma\cup Q)\)-p.r.. Sea \(P:\mathbf{N}\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) dado por \(P(x,\vec{x},\vec{\alpha})=1\) sii

Dejamos al lector la prueba de que \(P\) es \((\Gamma\cup Q)\)-p.r.. Ya que \(P\) es \(\Sigma\)-mixto, el Teorema 4.2 nos dice que \(P\) es \(\Sigma\)-p.r.. Notese que \[f=\lambda\vec{x}\vec{\alpha}\left[\ast^{\leq}\left(\left(\min_{x}P(x,\vec{x},\vec{\alpha})\right)_{2}\right)\right]\text{,}\] lo cual nos dice que \(f\) es \(\Sigma\)-recursiva.

4.4.4 Turing vence a Neumann

Probaremos que toda funcion \(\Sigma\)-computable es \(\Sigma\)-Turing computable. Para esto probaremos un resultado general que nos enseñara a simular el comportamiento de un programa con una maquina de Turing. Es importante notar que la simulacion que nos interesa que haga la maquina simuladora no es a nivel de la funcion que computa el programa sino a un nivel mas general, es decir nos interesa que simule a dicho programa como transformador de estados. En particular y usada adecuadamente, la maquina simuladora nos servira para confeccionar una maquina que compute una funcion computada por un programa dado.

4.4.4.1 Construccion de la maquina simuladora de un programa

Dado \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\), definamos \[\begin{aligned} N(\mathcal{P}) & =\mathrm{menor}\ k\in\mathbf{N}\ \mathrm{tal\ que\ las\ variables\ que\ ocurren\ en\ }\mathcal{P}\\ & \mathrm{esta}\text{n}\mathrm{\ todas\ en\ la\ lista\ N}1,...,\mathrm{N}\bar{k},\mathrm{P}1,...,\mathrm{P}\bar{k} \end{aligned}\] Por ejemplo si \(\mathcal{P}\) es el siguiente programa (aqui \(\Sigma=\{\blacktriangle,\#\}\)) \[\begin{array}{ll} \mathrm{L}1 & \mathrm{N}4\leftarrow\mathrm{N}4+1\\ & \mathrm{P}1\leftarrow\mathrm{P}1.\blacktriangle\\ & \mathrm{IF\ N}1\neq0\ \mathrm{GOTO}\;\mathrm{L}1 \end{array}\] entonces tenemos \(N(\mathcal{P})=4\)

Sea \(\mathcal{P}\) un programa y sea \(k\) fijo y mayor o igual a \(N(\mathcal{P})\). La construccion de la maquina simuladora dependera de \(\mathcal{P}\) y de \(k\). Notese que cuando \(\mathcal{P}\) se corre desde algun estado de la forma \[\left\Vert x_{1},...,x_{k},\alpha_{1},...,\alpha_{k}\right\Vert\] los sucesivos estados por los que va pasando son todos de la forma \[\left\Vert y_{1},...,y_{k},\beta_{1},...,\beta_{k}\right\Vert\] es decir en todos ellos las variables con indice mayor que \(k\) valen \(0\) o \(\varepsilon\). La razon es simple: ya que en \(\mathcal{P}\) no figuran las variables \[\begin{aligned} & \mathrm{N}\overline{k+1},\mathrm{N}\overline{k+2},...\\ & \mathrm{P}\overline{k+1},\mathrm{P}\overline{k+2},... \end{aligned}\] estas variables quedan con valores \(0\) y \(\varepsilon\), respectivamente a lo largo de toda la computacion.

La maquina simuladora que construiremos simulara a \(\mathcal{P}\) en cuanto a su funcionamiento cuando partimos de estados de la forma \(\left\Vert x_{1},...,x_{k},\alpha_{1},...,\alpha_{k}\right\Vert\). Necesitaremos tener alguna manera de representar en la cinta los diferentes estados por los cuales se va pasando, a medida que corremos a \(\mathcal{P}\). Esto lo haremos de la siguiente forma: al estado \[\left\Vert x_{1},...,x_{k},\alpha_{1},...,\alpha_{k}\right\Vert\] lo representaremos en la cinta de la siguiente manera \[B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}BBBB....\] Por ejemplo consideremos el programa \(\mathcal{P}\) mostrado recien y fijemos \(k=6\). Entonces al estado \[\left\Vert 3,2,5,0,4,2,\blacktriangle,\blacktriangle\blacktriangle,\varepsilon,\#\blacktriangle,\#,\#\#\#\right\Vert\] lo representaremos en la cinta de la siguiente manera \[B\mathrm{\shortmid\shortmid\shortmid}B\mathrm{\shortmid\shortmid}B\mathrm{\shortmid\shortmid\shortmid\shortmid\shortmid}BB\mathrm{\shortmid\shortmid\shortmid\shortmid}B\mathrm{\shortmid\shortmid}B\blacktriangle B\blacktriangle\blacktriangle BB\#\blacktriangle B\#B\#\#\#BBBBB....\] A lo que queda entre dos blancos consecutivos (es decir que no hay ningun blanco entre ellos) lo llamaremos "bloque", por ejemplo en la cinta de arriba tenemos que los primeros 12 bloques son \[\shortmid\shortmid\shortmid\ \ \ \shortmid\shortmid\ \ \ \shortmid\shortmid\shortmid\shortmid\shortmid\ \ \ \ \varepsilon\ \ \ \ \shortmid\shortmid\shortmid\shortmid\ \ \ \shortmid\shortmid\ \ \ \blacktriangle\ \ \ \ \ \blacktriangle\blacktriangle\ \ \ \ \ \varepsilon\ \ \ \ \ \#\blacktriangle\ \ \ \ \ \#\ \ \ \ \ \#\#\#\] y despues los bloques siguientes (que son infinitos ya que la cinta es infinita hacia la derecha) son todos iguales a \(\varepsilon\).

Una observacion importante es que esta forma de representacion de estados en la cinta depende del \(k\) elejido, es decir si tomaramos otro \(k\), por ejemplo \(k=9\), entonces el estado anterior se representaria de otra forma en la cinta. Aqui se ve claramente que la maquina simuladora que construiremos dependera del \(k\) elejido.

Armaremos la maquina simuladora como concatenacion de maquinas las cuales simularan, via la representacion anterior, el funcionamiento de las distintas instrucciones de \(\mathcal{P}\). Asumiremos que en \(\mathcal{P}\) no hay instrucciones de la forma \(\mathrm{GOTO}\;\mathrm{L}\bar{m}\) ni de la forma \(\mathrm{L}\bar{n}\ \mathrm{GOTO}\;\mathrm{L}\bar{m}\). Esto simplificara un poco la construccion de la maquina simuladora y de hecho lo podemos hacer ya que toda funcion \(\Sigma\)-computable puede ser computada por un programa sin este tipo de instrucciones, tal como lo veremos mas adelante (Lema 4.55).

Para poder hacer concretamente las maquinas simuladoras de instrucciones deberemos diseñar antes algunas maquinas auxiliares. Todas las maquinas descriptas a continuacion tendran a \(\shortmid\) como unit y a \(B\) como blanco, tendran a \(\Sigma\) como su alfabeto terminal y su alfabeto mayor sera \(\Gamma=\Sigma\cup\{B,\shortmid\}\cup\{\tilde{a}:a\in\Sigma\cup\{\shortmid\}\}\). Ademas tendran uno o dos estados finales con la propiedad de que si \(q\) es un estado final, entonces \((q,\sigma)\notin D_{\delta}\), para cada \(\sigma\in\Gamma\).

Notese que \[\begin{array}{lcr} \alpha B\beta_{1}B\beta_{2}B...B\beta_{j}B\gamma & \overset{\ast}{\vdash} & \alpha B\beta_{1}B\beta_{2}B...B\beta_{j}B\gamma\\ \ \uparrow & & \uparrow\ \\ \ q_{0} & & q_{f}\ \end{array}\] siempre que \(\alpha,\gamma\in\Gamma^{\ast}\), \(\beta_{1},...,\beta_{j}\in(\Gamma-\{B\})^{\ast}\). Es decir la maquina \(D_{j}\) lo unico que hace es mover el cabezal desde el blanco de la izquierda de un bloque determinado, exactamente \(j\) bloques a la derecha

Analogamente \(I_{j}\) sera una maquina que desplaza el cabezal \(j\) bloques a la izquierda del blanco que esta escaneando. Es decir \(I_{j}\) cumplira que \[\begin{array}{lcr} \alpha B\beta_{j}B...B\beta_{2}B\beta_{1}B\gamma & \overset{\ast}{\vdash} & \alpha B\beta_{j}B...B\beta_{2}B\beta_{1}B\gamma\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \uparrow & & \uparrow\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ q_{0} & & q_{f}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \end{array}\] siempre que \(\alpha,\gamma\in\Gamma^{\ast}\), \(\beta_{1},...,\beta_{j}\in(\Gamma-\{B\})^{\ast}\). Dejamos al lector la manufactura de esta maquina.

Para \(j\geq1\), sea \(TD_{j}\) una maquina con un solo estado final \(q_{f}\) y tal que \[\begin{array}{ccc} \alpha B\gamma & \overset{\ast}{\vdash} & \alpha BB\gamma\\ \uparrow & & \uparrow\ \ \\ q_{0} & & q_{f}\ \ \end{array}\] cada vez que \(\alpha,\gamma\in\Gamma^{\ast}\) y \(\gamma\) tiene exactamente \(j\) ocurrencias de \(B\). Es decir la maquina \(TD_{j}\) corre un espacio a la derecha todo el segmento \(\gamma\) y agrega un blanco en el espacio que se genera a la izquierda. Por ejemplo, para el caso de \(\Sigma=\{a\}\) podemos tomar \(TD_{3}\) igual a la siguiente maquina:

Analogamente, para \(j\geq1\), sea \(TI_{j}\) una maquina tal que \[\begin{array}{ccc} \alpha B\sigma\gamma & \overset{\ast}{\vdash} & \alpha B\gamma\\ \uparrow\ & & \uparrow\\ q_{0}\ \ & & q_{f} \end{array}\] cada vez que \(\alpha\in\Gamma^{\ast}\), \(\sigma\in\Gamma\) y \(\gamma\) tiene exactamente \(j\) ocurrencias de \(B\). Es decir la maquina \(TI_{j}\) corre un espacio a la izquierda todo el segmaneto \(\gamma\) (por lo cual en el lugar de \(\sigma\) queda el primer simbolo de \(\gamma\)). Dejamos al lector la construccion de por ejemplo \(TI_{3}\) para \(\Sigma=\{a\}\).

A continuacion describiremos las distintas maquinas simuladoras de instrucciones (y para algunos casos mostraremos concretamente como pueden ser hechas usando las maquinas anteriores).

Para \(1\leq i\leq k\), sea \(M_{i,k}^{+}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{i-1}}B\shortmid^{x_{i}+1}B\shortmid^{x_{i+1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i,k}^{+}\). Es claro que la maquina \(M_{i,k}^{+}\) simula la instruccion \(\mathrm{N}\bar{\imath}\leftarrow\mathrm{N}\bar{\imath}+1\), via la representacion de estados en la cinta con respecto a \(k\).

Para \(1\leq i\leq k\), sea \(M_{i,k}^{\dot{-}}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{i-1}}B\shortmid^{x_{i}\dot{-}1}B\shortmid^{x_{i+1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i,k}^{\dot{-}}\). Es claro que la maquina \(M_{i,k}^{\dot{-}}\) simula la instruccion \(\mathrm{P}\bar{\imath}\leftarrow\mathrm{P}\bar{\imath}\dot{-}1\), via la representacion de estados en la cinta con respecto a \(k\).

Para \(1\leq i\leq k\) y \(a\in\Sigma\), sea \(M_{i,k}^{a}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{i-1}B\alpha_{i}aB\alpha_{i+1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i,k}^{a}\). Es claro que la maquina \(M_{i,k}^{a}\) simula la instruccion \(\mathrm{P}\bar{\imath}\leftarrow\mathrm{P}\bar{\imath}.a\), via la representacion de estados en la cinta con respecto a \(k\). La maquina \(M_{i,k}^{a}\).puede hacerse de la siguiente manera:

Para \(1\leq i\leq k\), sea \(M_{i,k}^{\curvearrowright}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{i-1}B^{\curvearrowright}\alpha_{i}B\alpha_{i+1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i,k}^{\curvearrowright}\). Es claro que la maquina \(M_{i,k}^{\curvearrowright}\) simula la instruccion \(\mathrm{P}\bar{\imath}\leftarrow\ ^{\curvearrowright}\mathrm{P}\bar{\imath}\), via la representacion de estados en la cinta con respecto a \(k\).

Para \(1\leq i,j\leq k\), sea \(M_{i\leftarrow j}^{\#,k}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{i-1}}B\shortmid^{x_{j}}B\shortmid^{x_{i+1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i\leftarrow j}^{\#,k}\). Es claro que la maquina \(M_{i\leftarrow j}^{\#,k}\) simula la instruccion \(\mathrm{N}\bar{\imath}\leftarrow\mathrm{N}\bar{j}\), via la representacion de estados en la cinta con respecto a \(k\).

Para \(1\leq i,j\leq k\), sea \(M_{i\leftarrow j}^{\ast,k}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{i-1}B\alpha_{j}B\alpha_{i+1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i\leftarrow j}^{\ast,k}\). Es claro que la maquina \(M_{i\leftarrow j}^{\ast,k}\) simula la instruccion \(\mathrm{P}\bar{\imath}\leftarrow\mathrm{P}\bar{j}\), via la representacion de estados en la cinta con respecto a \(k\). La maquina \(M_{i\leftarrow j}^{\ast,k}\), para el caso \(\Sigma=\{a,b\}\) y \(i<j\) puede hacerse de la siguiente manera:

Para \(1\leq i\leq k\), sea \(M_{i\leftarrow0}^{k}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{i-1}}BB\shortmid^{x_{i+1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i\leftarrow0}^{k}\). Es claro que la maquina \(M_{i\leftarrow0}^{k}\) simula la instruccion \(\mathrm{N}\bar{\imath}\leftarrow0\), via la representacion de estados en la cinta con respecto a \(k\).

Para \(1\leq i\leq k\), sea \(M_{i\leftarrow\varepsilon}^{k}\) una maquina tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\): \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{i-1}BB\alpha_{i+1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{f} \end{array}\] donde \(q_{0}\) es el estado inicial y \(q_{f}\) es el unico estado final de \(M_{i\leftarrow\varepsilon}^{k}\). Es claro que la maquina \(M_{i\leftarrow\varepsilon}^{k}\) simula la instruccion \(\mathrm{P}\bar{\imath}\leftarrow\varepsilon\), via la representacion de estados en la cinta con respecto a \(k\).

Sea \[M_{\mathrm{SKIP}}=\left(\{q_{0},q_{f}\},\Gamma,\Sigma,\delta,q_{0},B,\shortmid,\{q_{f}\}\right),\] con \(D_{\delta}=\{(q_{0},B)\}\) y \(\delta(q_{0},B)=(q_{f},B,K)\). Es claro que la maquina \(M_{\mathrm{SKIP}}\) simula la instruccion \(\mathrm{SKIP}\), via la representacion de estados en la cinta con respecto a \(k\) (cualquiera sea el \(k\)).

Para \(1\leq j\leq k\), sea \(IF_{j,k}\) una maquina con estado inicial \(q_{0}\) y dos estados finales \(q_{si}\) y \(q_{no}\) tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\), si \(x_{j}\neq0\), entonces \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{si} \end{array}\] y si \(x_{j}=0\), entonces \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{no} \end{array}\]

Para \(1\leq i\leq k\) y \(a\in\Sigma\), sea \(IF_{j,k}^{a}\) una maquina con estado inicial \(q_{0}\) y dos estados finales \(q_{si}\) y \(q_{no}\) tal que cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\), si \(\alpha_{j}\) comienza con \(a\), entonces \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{si} \end{array}\] y en caso contrario \[\begin{array}{lcl} B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k} & \overset{\ast}{\vdash} & B\shortmid^{x_{1}}...B\shortmid^{x_{k}}B\alpha_{1}...B\alpha_{k}\\ \uparrow & & \uparrow\\ q_{0} & & q_{no} \end{array}\] La maquina \(IF_{j,k}^{a}\) puede hacerse de la siguinete manera:

A continuacion veremos un ejemplo de como se arma la maquina simuladora de un programa dado. Sea \(\Sigma=\{\blacktriangle,\#\}\) y sea \(\mathcal{P}\) el siguiente programa \[\begin{array}{ll} \mathrm{L}3 & \mathrm{N}4\leftarrow\mathrm{N}4+1\\ & \mathrm{P}1\leftarrow\ ^{\curvearrowright}\mathrm{P}1\\ & \mathrm{IF\ P}1\ \mathrm{BEGINS\ }\blacktriangle\ \mathrm{GOTO}\;\mathrm{L}3\\ & \mathrm{P}3\leftarrow\mathrm{P}3.\# \end{array}\] Tomemos \(k=5\). Es claro que \(k\geq N(\mathcal{P})=4\). A la maquina que simulara a \(\mathcal{P}\) respecto de \(k\), la llamaremos \(M_{sim}\) y sera la siguiente maquina:

Veamos con un ejemplo como \(M_{sim}\) simula a \(\mathcal{P}\). Supongamos que corremos \(\mathcal{P}\) desde el estado \[\left\Vert 2,1,0,5,3,\#\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert\] Tendremos entonces la siguiente sucesion de descripciones instantaneas: \[\begin{aligned} & (1,\left\Vert 2,1,0,5,3,\#\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert )\\ \\ & (2,\left\Vert 2,1,0,6,3,\#\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert )\\ \\ & (3,\left\Vert 2,1,0,6,3,\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert )\\ \\ & (1,\left\Vert 2,1,0,6,3,\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert )\\ \\ & (2,\left\Vert 2,1,0,7,3,\blacktriangle\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert )\\ \\ & (3,\left\Vert 2,1,0,7,3,\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert )\\ \\ & (4,\left\Vert 2,1,0,7,3,\#\#,\varepsilon,\blacktriangle\blacktriangle,\#\blacktriangle,\#\right\Vert )\\ \\ & (5,\left\Vert 2,1,0,7,3,\#\#,\varepsilon,\blacktriangle\blacktriangle\#,\#\blacktriangle,\#\right\Vert ) \end{aligned}\] Si hacemos funcionar a \(M_{sim}\) desde \(q_{0}B\shortmid^{2}B\shortmid BB\shortmid^{5}B\shortmid^{3}B\#\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\) obtendremos una sucesion de descripciones instantaneas dentro de la cual estara la siguiente subsucesion que se corresponde con las descripciones instantaneas de la computacion anterior. \[\begin{aligned} q_{0}B & \shortmid^{2}B\shortmid BB\shortmid^{5}B\shortmid^{3}B\#\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ \\q_{1}B & \shortmid^{2}B\shortmid BB\shortmid^{6}B\shortmid^{3}B\#\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ q_{2}B & \shortmid^{2}B\shortmid BB\shortmid^{6}B\shortmid^{3}B\#\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ \\q_{3}B & \shortmid^{2}B\shortmid BB\shortmid^{6}B\shortmid^{3}B\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ q_{4}B & \shortmid^{2}B\shortmid BB\shortmid^{6}B\shortmid^{3}B\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ \\q_{si}B & \shortmid^{2}B\shortmid BB\shortmid^{6}B\shortmid^{3}B\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ q_{0}B & \shortmid^{2}B\shortmid BB\shortmid^{6}B\shortmid^{3}B\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ \\q_{1}B & \shortmid^{2}B\shortmid BB\shortmid^{7}B\shortmid^{3}B\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ q_{2}B & \shortmid^{2}B\shortmid BB\shortmid^{7}B\shortmid^{3}B\blacktriangle\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ \\q_{3}B & \shortmid^{2}B\shortmid BB\shortmid^{7}B\shortmid^{3}B\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ q_{4}B & \shortmid^{2}B\shortmid BB\shortmid^{7}B\shortmid^{3}B\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ \\q_{no}B & \shortmid^{2}B\shortmid BB\shortmid^{7}B\shortmid^{3}B\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ q_{5}B & \shortmid^{2}B\shortmid BB\shortmid^{7}B\shortmid^{3}B\#\#BB\blacktriangle\blacktriangle B\#\blacktriangle B\#B\\ \\q_{6}B & \shortmid^{2}B\shortmid BB\shortmid^{7}B\shortmid^{3}B\#\#BB\blacktriangle\blacktriangle\#B\#\blacktriangle B\#B \end{aligned}\] Dejamos al lector ver en detalle el paralelismo que hay entre las dos sucesiones de descripciones instantaneas arriba expuestas.

A continuacion describiremos en general como hacer la maquina simuladora de \(\mathcal{P}\), respecto de \(k\). Supongamos que \(\mathcal{P}=I_{1}...I_{n}\). Para cada \(i=1,...,n\), llamaremos \(M_{i}\) a la maquina que simulara el efecto que produce la instruccion \(I_{i}\), es decir tomemos

Ya que la maquina \(M_{i}\) puede tener uno o dos estados finales, la representaremos como se muestra a continuacion:

entendiendo que en el caso en que \(M_{i}\) tiene un solo estado final, este esta representado por el circulo de abajo a la izquierda y en el caso en que \(M_{i}\) tiene dos estados finales, el circulo de abajo a la izquierda corresponde al estado final \(q_{no}\) y el circulo de abajo a la derecha corresponde al estado \(q_{si}\). Para armar la maquina que simulara a \(\mathcal{P}\) hacemos lo siguiente. Primero unimos las maquinas \(M_{1},...,M_{n}\) de la siguiente manera:

Luego para cada \(i\) tal que \(Bas(I_{i})\) es de la forma \(\alpha\mathrm{GOTO}\;\mathrm{L}\bar{m}\), ligamos con una flecha de la forma \[\underrightarrow{\;\;\;\;\;\;B,B,K\;\;\;\;\;\;}\] el estado final \(q_{si}\) de la \(M_{i}\) con el estado inicial de la \(M_{h}\), donde \(h\) es tal que \(I_{h}\) es la primer instruccion que tiene label \(\mathrm{L}\bar{m}\).

4.4.4.2 El lema de la simulacion

A continuacion enunciaremos en forma de lema la existencia de la maquina simuladora y de las propiedades esenciales que usaremos luego para probar que toda funcion \(\Sigma\)-computable es \(\Sigma\)-Turing computable.

4.55. Sea \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) y sea \(k\geq N(\mathcal{P})\). Supongamos que en \(\mathcal{P}\) no hay instrucciones de la forma \(\mathrm{GOTO}\;\mathrm{L}\bar{m}\) ni de la forma \(\mathrm{L}\bar{n}\ \mathrm{GOTO}\;\mathrm{L}\bar{m}\). Para cada \(a\in\Sigma\cup\{\shortmid\}\), sea \(\tilde{a}\) un nuevo simbolo. Sea \(\Gamma=\Sigma\cup\{B,\shortmid\}\cup\{\tilde{a}:a\in\Sigma\cup\{\shortmid\}\}\). Entonces hay una maquina de Turing con unit \(M=\left(Q,\Gamma,\Sigma,\delta,q_{0},B,\shortmid,\{q_{f}\}\right)\) la cual satisface

adhocprefix(1)adhocsufix \((q_{f},\sigma)\notin D_{\delta}\), para cada \(\sigma\in\Gamma\).
adhocprefix(2)adhocsufix Cualesquiera sean \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\), el programa \(\mathcal{P}\) se detiene partiendo del estado \[\left\Vert x_{1},...,x_{k},\alpha_{1},...,\alpha_{k}\right\Vert\] sii \(M\) se detiene partiendo de la descripcion instantanea \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{k}}B\alpha_{1}B...B\alpha_{k}B\right\rfloor\]
adhocprefix(3)adhocsufix Si \(x_{1},...,x_{k}\in\omega\) y \(\alpha_{1},...,\alpha_{k}\in\Sigma^{\ast}\) son tales que \(\mathcal{P}\) se detiene partiendo del estado \[\left\Vert x_{1},...,x_{k},\alpha_{1},...,\alpha_{k}\right\Vert\] y llega al estado \[\left\Vert y_{1},...,y_{k},\beta_{1},...,\beta_{k}\right\Vert\] entonces \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{k}}B\alpha_{1}B...B\alpha_{k}B\right\rfloor \overset{\ast}{\underset{M}{\vdash}}\left\lfloor q_{f}B\shortmid^{y_{1}}B...B\shortmid^{y_{k}}B\beta_{1}B...B\beta_{k}B\right\rfloor\]

Cabe destacar que si bien la veracidad de este lema es sustentada en las explicaciones anteriores, una prueba formal rigurosa del mismo resultaria extremadamente larga y tediosa. La ventaja de que sea un resultado intuitivamente claro nos permite aceptarlo y seguir adelante en nuestro analisis.

4.4.4.3 Turing vence a Neumann

En lo que sigue usaremos la existencia de la maquina simuladora de un programa para probar que toda funcion \(\Sigma\)-computable es \(\Sigma\)-Turing computable. Antes un lema.

4.56. Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) es \(\Sigma\)-computable, entonces hay un programa \(\mathcal{Q}\) el cual computa a \(f\) y el cual cumple con las siguientes propiedades

adhocprefix(1)adhocsufix En \(\mathcal{Q}\) no hay instrucciones de la forma \(\mathrm{GOTO}\;\mathrm{L}\bar{\imath}\) ni de la forma \(\mathrm{L}\bar{j}\ \mathrm{GOTO}\;\mathrm{L}\bar{\imath}\)
adhocprefix(2)adhocsufix Cuando \(\mathcal{Q}\) termina partiendo de un estado cualquiera dado, el estado alcansado es tal que las variables numericas tienen todas el valor \(0\) y las alfabeticas tienen todas exepto \(\mathrm{P}1\) el valor \(\varepsilon\).

Proof. Sea \(\mathcal{P}\) un programa que compute a \(f\). Sea \(r\in\mathbf{N}\) tal que \(r>N(\mathcal{P}),n,m\). Sea \(\mathcal{\tilde{P}}\) el resultado de reemplazar en \(\mathcal{P}\) cada instruccion de la forma \[\alpha\mathrm{GOTO}\;\mathrm{L}\bar{\imath}\] con \(\alpha\in\{\varepsilon\}\cup\{\mathrm{L}\bar{j}:j\in\mathbf{N}\}\) por \(\alpha\mathrm{IF\ N}\bar{r}\neq0\ \mathrm{GOTO}\;\mathrm{L}\bar{\imath}\). Ahora sea \(\mathcal{Q}\) el siguiente programa \[\begin{array}{l} \mathrm{N}\bar{r}\leftarrow\mathrm{N}\bar{r}+1\\ \mathcal{\tilde{P}}\\ \mathrm{N}1\leftarrow0\\ \vdots\\ \mathrm{N}\bar{r}\leftarrow0\\ \mathrm{P}2\leftarrow\varepsilon\\ \vdots\\ \mathrm{P}\bar{r}\leftarrow\varepsilon \end{array}\] Es facil ver que \(\mathcal{Q}\) tiene las propiedades (1) y (2).

Por supuesto, hay un lema analogo para el caso en que \(f\) llega a \(\omega\) en lugar de llegar a \(\Sigma^{\ast}\). Ahora si, el anunciado teorema:

Proof. Supongamos \(O=\Sigma^{\ast}\). Por el Lema 4.56 existe \(\mathcal{P}\in\mathrm{Pro}^{\Sigma}\) el cual computa \(f\) y tiene las propiedades (1) y (2). Sea \(k=\max\{n,m,N(\mathcal{P})\}\) y sea \(M_{sim}\) la maquina de Turing con unit que simula a \(\mathcal{P}\) respecto de \(k\). Como puede observarse, la maquina \(M_{sim}\), no necesariamente computara a \(f\). Sea \(M_{1}\) la siguiente maquina:

(Cuando \(n=0\) debemos interpretar que \(D_{0}=\left(\{q_{0},q_{f}\},\Gamma,\Sigma,\delta,q_{0},B,\shortmid,\{q_{f}\}\right)\), con \(D_{\delta}=\{(q_{0},B)\}\) y \(\delta(q_{0},B)=(q_{f},B,K)\). Notese que \(M_{1}\) cumple que para cada \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\), \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}B\right\rfloor \overset{\ast}{\vdash}\left\lfloor q_{f}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B^{k-n}B\alpha_{1}B...B\alpha_{m}B\right\rfloor\] Sea \(M_{2}\) la siguiente maquina

Notese que \(M_{2}\) cumple que para cada \(\alpha\in\Sigma^{\ast}\), \[\left\lfloor q_{0}B^{k+1}\alpha\right\rfloor \overset{\ast}{\vdash}\left\lfloor q_{f}B\alpha\right\rfloor\] Sea \(M\) la siguiente maquina:

A continuacion veremos que \(M\) computa a \(f\). Supongamos que \((\vec{x},\vec{\alpha})\in(\omega^{n}\times\Sigma^{\ast m})-D_{f}\). Deberemos ver que \(M\) no termina partiendo de

Primero notemos que, ya que \(\mathcal{P}\) computa a \(f\), tenemos que \(\mathcal{P}\) no termina partiendo de \(\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert\) por lo cual \(\mathcal{P}\) no termina partiendo de \[\left\Vert x_{1},...,x_{n},\overset{k-n}{\overbrace{0,...,0}},\alpha_{1},...,\alpha_{m},\overset{k-m}{\overbrace{\varepsilon,...,\varepsilon}}\right\Vert\] lo cual implica (Lema 4.55) que

Ahora notese que si hacemos funcionar a \(M\) desde la descripcion instantanea dada en (*), llegaremos (via la copia de \(M_{1}\) dentro de \(M\)) indefectiblemente (ya que \(M\) es deterministica) a la siguiente descripcion instantanea \[\left\lfloor q_{2}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B^{k-n}B\alpha_{1}B...B\alpha_{m}B\right\rfloor\] Luego entonces (**) nos dice que al seguir trabajando \(M\) (ahora via la copia de \(M_{sim}\) dentro de \(M\)), la maquina \(M\) nunca terminara.

Para terminar de ver que \(M\) computa a \(f\), tomemos \((\vec{x},\vec{\alpha})\in D_{f}\) y veamos que \[\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}B\right\rfloor \overset{\ast}{\underset{M}{\vdash}}\left\lfloor q_{5}Bf(\vec{x},\vec{\alpha})\right\rfloor\] y que la maquina \(M\) se detiene en \(\left\lfloor q_{5}Bf(\vec{x},\vec{\alpha})\right\rfloor\). La maquina \(M\) se detiene en \(\left\lfloor q_{5}Bf(\vec{x},\vec{\alpha})\right\rfloor\) ya que \(q_{5}\) es el estado final de una copia de \(M_{2}\) y por lo tanto no sale ninguna flecha desde el. Ya que \(\mathcal{P}\) computa a \(f\) y tiene la propiedad (2) del Lema 4.56, tenemos que \(\mathcal{P}\) termina partiendo de \(\left\Vert x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\right\Vert\) y llega al estado \(\left\Vert f(\vec{x},\vec{\alpha})\right\Vert\), o lo que es lo mismo, \(\mathcal{P}\) termina partiendo de \[\left\Vert x_{1},...,x_{n},\overset{k-n}{\overbrace{0,...,0}},\alpha_{1},...,\alpha_{m},\overset{k-m}{\overbrace{\varepsilon,...,\varepsilon}}\right\Vert\] y llega al estado \[\left\Vert \overset{k}{\overbrace{0,...,0}},f(\vec{x},\vec{\alpha}),\overset{k-1}{\overbrace{\varepsilon,...,\varepsilon}}\right\Vert\] Pero entonces el Lema 4.55 nos dice que

Como ya lo vimos, si hacemos funcionar a \(M\) desde \(\left\lfloor q_{0}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B\alpha_{1}B...B\alpha_{m}B\right\rfloor\), llegaremos (via la copia de \(M_{1}\) dentro de \(M\)) indefectiblemente a la siguiente descripcion instantanea \[\left\lfloor q_{2}B\shortmid^{x_{1}}B...B\shortmid^{x_{n}}B^{k-n}B\alpha_{1}B...B\alpha_{m}B\right\rfloor\] Luego (***) nos dice que, via la copia de \(M_{sim}\) dentro de \(M\), llegaremos a \(\left\lfloor q_{3}B^{k+1}f(\vec{x},\vec{\alpha})\right\rfloor\) e inmediatamente a \(\left\lfloor q_{4}B^{k+1}f(\vec{x},\vec{\alpha})\right\rfloor\). Finalmente, via la copia de \(M_{2}\) dentro de \(M\), llegaremos a \(\left\lfloor q_{5}Bf(\vec{x},\vec{\alpha})\right\rfloor\), lo cual termina de demostrar que \(M\) computa a \(f\)

4.4 Batallas entre paradigmas