El paradigma de Godel: Funciones \Sigma-recursivas

En esta seccion desarrollaremos el modelo matematico del concepto de funcion \(\Sigma\)-efectivamente computable, dado por Godel. Dichas funciones seran llamadas \(\Sigma\)-recursivas. La idea es partir de un conjunto inicial de funciones muy simples y obviamente \(\Sigma\)-efectivamente computables y luego obtener nuevas funciones \(\Sigma\)-efectivamente computables usando constructores que preservan la computabilidad efectiva. Las funciones \(\Sigma\)-recursivas seran las que se obtienen iterando el uso de estos constructores, partiendo del conjunto inicial de funciones antes mencionado. Nos referiremos a este paradigma como el paradigma Godeliano o recursivo. A veces tambien lo llamaremos el paradigma funcional.

La familia de funciones simples y obviamente \(\Sigma\)-efectivamente computables de la que partiremos es la siguiente \[\left\{ Suc,Pred,C_{0}^{0,0},C_{\varepsilon}^{0,0}\right\} \cup\left\{ d_{a}:a\in\Sigma\right\} \cup\left\{ p_{j}^{n,m}:1\leq j\leq n+m\right\}\] Los constructores que usaremos son:

Estos constructores nos permiten dadas ciertas funciones construir o definir una nueva funcion y tienen la propiedad de preservar la computabilidad efectiva en el sentido que si las funciones iniciales son \(\Sigma\)-efectivamente computables, entonces la funcion obtenida tambien lo es. Un concepto fundamental es el de funcion \(\Sigma\)-recursiva primitiva. Estas funciones seran aquellas que se obtienen a partir de las del conjunto inicial usando solo los dos primeros constructores: composicion y recursion primitiva. Nuestro primer objetivo es definir el concepto de funcion \(\Sigma\)-recursiva primitiva para lo cual en las proximas dos secciones definiremos y estudiaremos los constructores de composicion y recursion primitiva. Luego definiremos el concepto de funcion \(\Sigma\)-recursiva primitiva y nos abocaremos a desarrollar este concepto fundamental. Recien despues estudiaremos el constructor de minimizacion y definiremos el concepto de funcion \(\Sigma\)-recursiva. La ultima parte de la seccion esta destinada a probar un teorema que nos dice que los conceptos de funcion \(\Sigma\)-recursiva y \(\Sigma\)-recursiva primitiva son independientes del alfabeto \(\Sigma\).

4.2.1 Composicion

Dadas funciones \(\Sigma\)-mixtas \(f,f_{1},...,f_{r}\), con \(r\geq1\), diremos que la funcion \(f\circ[f_{1},...,f_{r}]\) es obtenida por composicion a partir de las funciones \(f,f_{1},...,f_{r}\). Para probar que la composicion preserva la computabilidad efectiva necesitaremos el siguiente lema.

4.1. Supongamos que \(f,f_{1},...,f_{r}\) son funciones \(\Sigma\)-mixtas, con \(r\geq1\). Supongamos ademas que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\). Entonces hay \(n,m,k,l\in\omega\) y \(s\in\{\#,\ast\}\) tales que

adhocprefix-adhocsufix \(r=n+m\)
adhocprefix-adhocsufix \(f\) es de tipo \((n,m,s)\)
adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\)
adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\)

Mas aun, en tal caso la funcion \(f\circ[f_{1},...,f_{n+m}]\) es de tipo \((k,l,s)\) y: \[\begin{aligned} D_{f\circ[f_{1},...,f_{n+m}]} & =\left\{ (\vec{x},\vec{\alpha})\in\bigcap_{i=1}^{n+m}D_{f_{i}}:(f_{1}(\vec{x},\vec{\alpha}),...,f_{n+m}(\vec{x},\vec{\alpha}))\in D_{f}\right\} \\ f\circ[f_{1},...,f_{n+m}](\vec{x},\vec{\alpha}) & =f(f_{1}(\vec{x},\vec{\alpha}),...,f_{n+m}(\vec{x},\vec{\alpha})). \end{aligned}\]

Proof. Notese que \(f\neq\emptyset\) y \([f_{1},...,f_{r}]\neq\emptyset\) (por que?). Ya que \(f\neq\emptyset\) tenemos que hay unicos \(n,m\in\omega\) y \(s\in\{\#,\ast\}\) tales que \(f\) es de tipo \((n,m,s)\). Ya que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\) y \(I_{[f_{1},...,f_{r}]}\subseteq I_{f_{1}}\times...\times I_{f_{r}}\), tenemos que

Ya que \([f_{1},...,f_{r}]\neq\emptyset\) tenemos que \(D_{[f_{1},...,f_{r}]}=\bigcap_{i=1}^{r}D_{f_{i}}\neq\emptyset\), por lo cual los conjuntos \(D_{f_{1}},...,D_{f_{n+m}}\) deberan ser todos de un mismo tipo, digamos de tipo \((k,l)\). Es decir que \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\) y \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\).

Las ultimas observaciones del lema son directas de las definiciones de \([f_{1},...,f_{n+m}]\) y de composicion de funciones

Ahora si podemos probar facilmente que el contructor composicion preserva la computabilidad efectiva

4.2. Si \(f,f_{1},...,f_{r}\), con \(r\geq1\), son \(\Sigma\)-efectivamente computables, entonces \(f\circ[f_{1},...,f_{r}]\) lo es.

Proof. Si \(f\circ[f_{1},...,f_{r}]=\emptyset\), entonces claramente es \(\Sigma\)-efectivamente computable. Supongamos entonces que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\). Por el lema anterior hay \(n,m,k,l\in\omega\) y \(s\in\{\#,\ast\}\) tales que

Sean \(\mathbb{P},\mathbb{P}_{1},...,\mathbb{P}_{n+m}\) procedimientos efectivos los cuales computen computen las funciones \(f,f_{1},...,f_{n+m}\), respectivamente. Usando estos procedimientos es facil definir un procedimiento efectivo el cual compute a \(f\circ[f_{1},...,f_{n+m}]\).

4.2.2 Recursion primitiva

La recursion primitiva es un tipo muy particular de recursion. Consideremos por ejemplo las siguientes ecuaciones:

Notese que hay una unica funcion \(R:\omega\rightarrow\omega\) la cual cumple (1) y (2). Esto es ya que el valor de \(R\) en \(t\) esta determinado por sucesivas aplicaciones de las ecuaciones (1) y (2). Por ejemplo la ecuacion (1) nos dice que \(R(0)=1\) pero entonces la ecuacion (2) nos dice que \(R(1)=1+1+1^{2}=3\) por lo cual nuevamente la ecuacion (2) nos dice que \(R(2)=1+3+3^{2}=13\) y asi podemos notar facilmente que \(R\) esta determinada por dichas ecuaciones.

Se suele decir que las ecuaciones (1) y (2) definen recursivamente a la funcion \(R\) pero hay que tener cuidado porque esto es una manera de hablar ya que la funcion \(R\) podria en nuestro discurso ya haber sido definida de otra manera. Mas propio es pensar que dichas ecuaciones determinan a \(R\) en el sentido que \(R\) es la unica que las cumple. Por ejemplo las ecuaciones:

definen recursivamente a la funcion \(C_{50}^{1,0}\) pero esta claro que la definicion de \(C_{50}^{1,0}\) en esta materia no fue dada de esta forma.

Hay casos de recursiones en las cuales el valor de \(R(t+1)\) no solo depende de \(R(t)\) sino que tambien depende de \(t\). Por ejemplo

De todas maneras deberia quedar claro que las ecuaciones (i) y (ii) determinan una unica funcion \(R:\omega\rightarrow\omega\) que las satisface.

Tambien podemos generalizar pensando que la funcion \(R\) depende no solo de un parametro \(t\) sino que su dominio es \(\omega^{4}\), es decir depende de \(t\) y \(x_{1},x_{2},x_{3}\). Por ejemplo

Dejamos al lector convencerse de que (p) y (q) son cumplidas por una unica funcion \(R:\omega^{4}\rightarrow\omega\). Tambien podriamos tener variables alfabeticas. Por ejemplo consideremos

Es claro aqui que las ecuaciones (r) y (s) determinan una unica funcion \(R:\omega^{3}\times\Sigma^{\ast2}\rightarrow\omega\) que las cumple. Esto se puede explicar de la siguiente manera:

El caso anterior podria generalizarse de la siguiente manera: Si tenemos dadas dos funciones \[\begin{aligned} f & :\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\\ g & :\omega^{n+2}\times\Sigma^{\ast m}\rightarrow\omega \end{aligned}\] entonces las ecuaciones:

determinan una unica funcion \(R:\omega^{n+1}\times\Sigma^{\ast m}\rightarrow\omega\) que las cumple. Notese que para el caso \[\begin{aligned} n & =m=2\\ f & =\lambda x_{1}x_{2}\alpha_{1}\alpha_{2}[x_{1}+\left\vert \alpha_{1}\right\vert ^{x_{2}}]\\ g & =\lambda xtx_{1}x_{2}\alpha_{1}\alpha_{2}[t+x_{1}+x_{2}+\left\vert \alpha_{1}\right\vert +\left\vert \alpha_{2}\right\vert +x] \end{aligned}\] las ecuaciones (a) y (b) se transforman en las ecuaciones (r) y (s).

El primer caso de recursion primitiva que definiremos a continuacion engloba los ejemplos vistos recien dentro de un marco general.

4.2.2.1 Recursion primitiva sobre variable numerica con valores numericos

Supongamos tenemos dadas funciones \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\\ g & :\omega\times\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega \end{aligned}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacios. Usando el razonamiento inductivo usado en los ejemplos anteriores, se puede probar que hay una unica funcion \[R:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\] la cual cumple las ecuaciones

LLamaremos \(R(f,g)\) a esta unica funcion que cumple las ecuaciones anteriores. Resumiendo, diremos que las ecuaciones

definen recursivamente a la funcion \(R(f,g)\). Tambien diremos que \(R(f,g)\) es obtenida por recursion primitiva a partir de \(f\) y \(g\).

NOTA IMPOTANTE: No confundirse y pensar que \(R(f,g)\) es el resultado de aplicar una funcion \(R\) al par \((f,g)\), de hecho hasta el momento no hemos definido ninguna funcion \(R\) cuyo dominio sea cierto conjunto de pares ordenados de funciones!

Notese que cuando \(m=n=0\), se tiene que \(D_{f}=\{\Diamond\}\) y (1) y (2) se transforman en

Como era de esperar, este caso del constructor de recursion primitiva preserva la computabilidad efectiva

4.3. Si \(f\) y \(g\) son \(\Sigma\)-efectivamente computables, entonces \(R(f,g)\) lo es.

Nota importante: En los ejemplos anteriores y en todos los casos que manejaremos en esta primera etapa, en las aplicaciones del constructor de recursion primitiva (en sus cuatro formas) las funciones iniciales seran \(\Sigma\)-totales (es decir \(S_{1}=...=S_{n}=\omega\) y \(L_{1}=...=L_{m}=\Sigma^{\ast}\)). Mas adelante veremos aplicaciones con funciones no \(\Sigma\)-totales.

4.2.2.2 Recursion primitiva sobre variable numerica con valores alfabeticos

Ahora haremos el caso en el que la funcion definida recursivamente tiene imagen contenida en \(\Sigma^{\ast}\). Es claro que entonces \(f\) y \(g\) tambien deberan tener imagen contenida en \(\Sigma^{\ast}\). El unico detalle a tener en cuenta en la definicion de este caso es que si solo hicieramos estos cambios y pusieramos las mismas ecuaciones la funcion \(g\) no resultaria \(\Sigma\)-mixta en general. Para que la \(g\) de la recursion siga siendo \(\Sigma\)-mixta deberemos modificar levemente su dominio en relacion al caso ya hecho

Supongamos \(\Sigma\) es un alfabeto finito. Sean \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\\ g & :\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast} \end{aligned}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacios. Definamos \[R(f,g):\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\] de la siguiente manera

Diremos que \(R(f,g)\) es obtenida por recursion primitiva a partir de \(f\) y \(g\). Notese que cuando \(m=n=0\), se tiene que \(D_{f}=\{\Diamond\}\) y (1) y (2) se transforman en

La prueba del siguiente lema es completamente analoga a la del lema anterior que fue dejada como ejercicio.

4.4. Si \(f\) y \(g\) son \(\Sigma\)-efectivamente computables, entonces \(R(f,g)\) lo es.

4.2.2.3 Recursion primitiva sobre variable alfabetica con valores numericos

Ya vimos dos casos de recursion donde el parametro que comanda la recursion es numerico. Daremos a continuacion un ejemplo de recursion en el cual el parametro principal es alfabetico. Sea \(\Sigma=\{\%,@,?\}\) y consideremos las siguientes ecuaciones:

Notese que las ecuaciones anteriores determinan una funcion \(R:\Sigma^{\ast}\rightarrow\omega\). Esto es ya que \(R\) en \(\varepsilon\) debe valer \(15\) y sabiendo esto las ecuaciones (2), (3) y (4) (con \(\alpha=\varepsilon\)) nos dicen que \[\begin{aligned} R(\%) & =16\\ R(@) & =75\\ R(?) & =15^{20} \end{aligned}\] por lo cual podemos aplicarlas nuevamente a dichas ecuaciones (con \(\alpha\in\{\%,@,?\}\)) para calcular \(R\) en todas las palabras de longitud \(2\); y asi sucesivamente.

Daremos otro ejemplo un poco mas complicado para seguir aproximandonos al caso general. Nuevamente supongamos que \(\Sigma=\{\%,@,?\}\) y supongamos tenemos una funcion \[f:\omega\times\Sigma^{\ast}\rightarrow\omega\] y tres funciones \[\begin{aligned} \mathcal{G}_{\%} & :\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega\\ \mathcal{G}_{@} & :\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega\\ \mathcal{G}_{?} & :\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega \end{aligned}\] Entonces hay una unica funcion \(R::\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\omega\) la cual cumple las siguientes ecuaciones

El ejemplo anterior nos muestra que para hacer recursion sobre parametro alfabetico nos hace falta "una funcion \(g\) por cada simbolo de \(\Sigma\)". Esto motiva la siguiente definicion. Dado un alfabeto \(\Sigma\), una familia \(\Sigma\)-indexada de funciones sera una funcion \(\mathcal{G}\) tal que \(D_{\mathcal{G}}=\Sigma\) y para cada \(a\in D_{\mathcal{G}}\) se tiene que \(\mathcal{G}(a)\) es una funcion. Algunos ejemplos:

Si \(\mathcal{G}\) es una familia \(\Sigma\)-indexada de funciones, entonces para \(a\in\Sigma\), escribiremos \(\mathcal{G}_{a}\) en lugar de \(\mathcal{G}(a)\). Ahora sí, nuestro caso de recursion primitiva. Sea \[f:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacios y sea \(\mathcal{G}\) una familia \(\Sigma\)-indexada de funciones tal que \[\mathcal{G}_{a}:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\omega\] para cada \(a\in\Sigma.\) Definamos \[R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\omega\] de la siguiente manera

Diremos que \(R(f,\mathcal{G})\) es obtenida por recursion primitiva a partir de \(f\) y \(\mathcal{G}\). Notese que cuando \(m=n=0\), se tiene que \(D_{f}=\{\Diamond\}\) y (1) y (2) se transforman en

4.5. Si \(f\) y cada \(\mathcal{G}_{a}\) son \(\Sigma\)-efectivamente computables, entonces \(R(f,\mathcal{G})\) lo es.

4.2.2.4 Recursion primitiva sobre variable alfabetica con valores alfabeticos

Supongamos \(\Sigma\) es un alfabeto finito. Sea \[f:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacios y sea \(\mathcal{G}\) una familia \(\Sigma\)-indexada de funciones tal que \[\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}\] para cada \(a\in\Sigma\). Definamos \[R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}\] de la siguiente manera

La prueba del siguiente lema es completamente analoga a la del lema anterior que fue dejada como ejercicio.

4.6. Si \(f\) y cada \(\mathcal{G}_{a}\) son \(\Sigma\)-efectivamente computables, entonces \(R(f,\mathcal{G})\) lo es.

4.2.3 Funciones \(\Sigma\)-recursivas primitivas

Intuitivamente hablando una funcion es \(\Sigma\)-recursiva primitiva si se puede obtener de las iniciales usando los constructores de composicion y recursion primitiva. Daremos ahora una definicion matematica de este concepto. Definamos los conjuntos \(\mathrm{PR}_{0}^{\Sigma}\subseteq\mathrm{PR}_{1}^{\Sigma}\subseteq\mathrm{PR}_{2}^{\Sigma}\subseteq...\subseteq\mathrm{PR}^{\Sigma}\) de la siguiente manera \[\begin{array}{lll} \mathrm{PR}_{0}^{\Sigma} & = & \left\{ Suc,Pred,C_{0}^{0,0},C_{\varepsilon}^{0,0}\right\} \cup\left\{ d_{a}:a\in\Sigma\right\} \cup\left\{ p_{j}^{n,m}:1\leq j\leq n+m\right\} \\ \mathrm{PR}_{k+1}^{\Sigma} & = & \mathrm{PR}_{k}^{\Sigma}\cup\left\{ f\circ[f_{1},...,f_{r}]:f,f_{1},...,f_{r}\in\mathrm{PR}_{k}^{\Sigma}\text{, }r\geq1\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ R(f,\mathcal{G}):R(f,\mathcal{G})\text{ esta definida y }\{f\}\cup\{\mathcal{G}_{a}:a\in\Sigma\}\subseteq\mathrm{PR}_{k}^{\Sigma}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ R(f,g):R(f,g)\text{ esta definida y }f,g\in\mathrm{PR}_{k}^{\Sigma}\right\} \\ \mathrm{PR}^{\Sigma} & = & \bigcup_{k\geq0}\mathrm{PR}_{k}^{\Sigma} \end{array}\] Una funcion es llamada \(\Sigma\)-recursiva primitiva (\(\Sigma\)-p.r.) si pertenece a \(\mathrm{PR}^{\Sigma}\).

Proof. Dejamos al lector la prueba por induccion en \(k\) de que si \(f\in\mathrm{PR}_{k}^{\Sigma}\), entonces \(f\) es \(\Sigma\)-efectivamente computable, la cual sale en forma directa usando los lemas anteriores que garantizan que los constructores de composicion y recursion primitiva preservan la computabilidad efectiva

4.2.3.1 Algunas funciones \(\Sigma\)-recursivas primitivas

En los siguientes cuatro lemas se prueba bien formalmente que varias funciones bien conocidas son \(\Sigma\)-primitivas recursivas.

4.7. Sea \(\Sigma\) un alfabeto finito.

adhocprefix(1)adhocsufix \(\emptyset\in\mathrm{PR}^{\Sigma}\).
adhocprefix(2)adhocsufix \(\lambda xy\left[x+y\right]\in\mathrm{PR}^{\Sigma}\).
adhocprefix(3)adhocsufix \(\lambda xy\left[x.y\right]\in\mathrm{PR}^{\Sigma}\).
adhocprefix(4)adhocsufix \(\lambda x\left[x!\right]\in\mathrm{PR}^{\Sigma}\).

Proof. (1) Notese que \(\emptyset=Pred\circ C_{0}^{0,0}\in\mathrm{PR}_{1}^{\Sigma}\)

(2) Notar que \[\begin{aligned} \lambda xy\left[x+y\right](0,x_{1}) & =x_{1}=p_{1}^{1,0}(x_{1})\\ \lambda xy\left[x+y\right](t+1,x_{1}) & =\lambda xy\left[x+y\right](t,x_{1})+1\\ & =\left(Suc\circ p_{1}^{3,0}\right)\left(\lambda xy\left[x+y\right](t,x_{1}),t,x_{1}\right) \end{aligned}\] lo cual implica que \(\lambda xy\left[x+y\right]=R\left(p_{1}^{1,0},Suc\circ p_{1}^{3,0}\right)\in\mathrm{PR}_{2}^{\Sigma}.\)

(3) Primero note que \[\begin{aligned} C_{0}^{1,0}(0) & =C_{0}^{0,0}(\Diamond)\\ C_{0}^{1,0}(t+1) & =C_{0}^{1,0}(t) \end{aligned}\] lo cual implica que \(C_{0}^{1,0}=R\left(C_{0}^{0,0},p_{1}^{2,0}\right)\in\mathrm{PR}_{1}^{\Sigma}.\) Tambien note que \[\lambda tx\left[t.x\right]=R\left(C_{0}^{1,0},\lambda xy\left[x+y\right]\circ\left[p_{1}^{3,0},p_{3}^{3,0}\right]\right),\] lo cual por (2) implica que \(\lambda tx\left[t.x\right]\in\mathrm{PR}_{4}^{\Sigma}\).

(4) Note que \[\begin{aligned} \lambda x\left[x!\right](0) & =1=C_{1}^{0,0}(\Diamond)\\ \lambda x\left[x!\right](t+1) & =\lambda x\left[x!\right](t).(t+1), \end{aligned}\] lo cual implica que \[\lambda x\left[x!\right]=R\left(C_{1}^{0,0},\lambda xy\left[x.y\right]\circ\left[p_{1}^{2,0},Suc\circ p_{2}^{2,0}\right]\right).\] Ya que \(C_{1}^{0,0}=\) \(Suc\circ C_{0}^{0,0}\), tenemos que \(C_{1}^{0,0}\in\mathrm{PR}_{1}^{\Sigma}\). Por (3), tenemos que \[\lambda xy\left[x.y\right]\circ\left[p_{1}^{2,0},Suc\circ p_{2}^{2,0}\right]\in\mathrm{PR}_{5}^{\Sigma},\] obteniendo que \(\lambda x\left[x!\right]\in\mathrm{PR}_{6}^{\Sigma}\).

Ahora consideraremos dos funciones las cuales son obtenidas naturalmente por recursion primitiva sobre variable alfabetica.

4.8. Supongamos \(\Sigma\) es un alfabeto finito.

adhocprefix(a)adhocsufix \(\lambda\alpha\beta\left[\alpha\beta\right]\in\mathrm{PR}^{\Sigma}\)
adhocprefix(b)adhocsufix \(\lambda\alpha\left[\left\vert \alpha\right\vert \right]\in\mathrm{PR}^{\Sigma}\)

Proof. (a) Ya que \[\begin{aligned} \lambda\alpha\beta\left[\alpha\beta\right](\alpha_{1},\varepsilon) & =\alpha_{1}=p_{1}^{0,1}(\alpha_{1})\\ \lambda\alpha\beta\left[\alpha\beta\right](\alpha_{1},\alpha a) & =d_{a}(\lambda\alpha\beta\left[\alpha\beta\right](\alpha_{1},\alpha)),\ a\in\Sigma \end{aligned}\] tenemos que \(\lambda\alpha\beta\left[\alpha\beta\right]=R\left(p_{1}^{0,1},\mathcal{G}\right)\), donde \(\mathcal{G}_{a}=d_{a}\circ p_{3}^{0,3}\), para cada \(a\in\Sigma\).

(b) Ya que \[\begin{aligned} \lambda\alpha\left[\left\vert \alpha\right\vert \right](\varepsilon) & =0=C_{0}^{0,0}(\Diamond)\\ \lambda\alpha\left[\left\vert \alpha\right\vert \right](\alpha a) & =\lambda\alpha\left[\left\vert \alpha\right\vert \right](\alpha)+1 \end{aligned}\] tenemos que \(\lambda\alpha\left[\left\vert \alpha\right\vert \right]=R\left(C_{0}^{0,0},\mathcal{G}\right)\), donde \(\mathcal{G}_{a}=\) \(Suc\circ p_{1}^{1,1}\), para cada \(a\in\Sigma.\).

4.9. Sea \(\Sigma\) un alfabeto finito. Entonces \(C_{k}^{n,m},C_{\alpha}^{n,m}\in\mathrm{PR}^{\Sigma}\), para cada \(n,m,k\geq0\) y \(\alpha\in\Sigma^{\ast}\).

Proof. (a) Note que \(C_{k+1}^{0,0}=\) \(Suc\circ C_{k}^{0,0}\), lo cual implica \(C_{k}^{0,0}\in\mathrm{PR}_{k}^{\Sigma}\), para \(k\geq0\). Tambien note que \(C_{\alpha a}^{0,0}=d_{a}\circ C_{\alpha}^{0,0}\), lo cual dice que \(C_{\alpha}^{0,0}\in\mathrm{PR}^{\Sigma}\), para \(\alpha\in\Sigma^{\ast}\). Para ver que \(C_{k}^{0,1}\in\mathrm{PR}^{\Sigma}\) notar que \[\begin{aligned} C_{k}^{0,1}(\varepsilon) & =k=C_{k}^{0,0}(\Diamond)\\ C_{k}^{0,1}(\alpha a) & =C_{k}^{0,1}(\alpha)=p_{1}^{1,1}\left(C_{k}^{0,1}(\alpha),\alpha\right) \end{aligned}\] lo cual implica que \(C_{k}^{0,1}=R\left(C_{k}^{0,0},\mathcal{G}\right)\), con \(\mathcal{G}_{a}=p_{1}^{1,1}\), \(a\in\Sigma\). En forma similar podemos ver que \(C_{k}^{1,0},C_{\alpha}^{1,0},C_{\alpha}^{0,1}\in\mathrm{PR}^{\Sigma}\). Supongamos ahora que \(m>0\). Entonces \[\begin{aligned} C_{k}^{n,m} & =C_{k}^{0,1}\circ p_{n+1}^{n,m}\\ C_{\alpha}^{n,m} & =C_{\alpha}^{0,1}\circ p_{n+1}^{n,m} \end{aligned}\] de lo cual obtenemos que \(C_{k}^{n,m},C_{\alpha}^{n,m}\in\mathrm{PR}^{\Sigma}\). El caso \(n>0\) es similar.

4.10. Sea \(\Sigma\) un alfabeto finito.

adhocprefix(a)adhocsufix \(\lambda xy\left[x^{y}\right]\in\mathrm{PR}^{\Sigma}\).
adhocprefix(b)adhocsufix \(\lambda t\alpha\left[\alpha^{t}\right]\in\mathrm{PR}^{\Sigma}\).

Proof. (a) Note que \[\lambda tx\left[x^{t}\right]=R\left(C_{1}^{1,0},\lambda xy\left[x.y\right]\circ\left[p_{1}^{3,0},p_{3}^{3,0}\right]\right)\in\mathrm{PR}^{\Sigma}.\] O sea que \(\lambda xy\left[x^{y}\right]=\lambda tx\left[x^{t}\right]\circ\left[p_{2}^{2,0},p_{1}^{2,0}\right]\in\mathrm{PR}^{\Sigma}\).

(b) Note que \[\lambda t\alpha\left[\alpha^{t}\right]=R\left(C_{\varepsilon}^{0,1},\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[p_{3}^{1,2},p_{2}^{1,2}\right]\right)\in\mathrm{PR}^{\Sigma}.\]

Ahora probaremos que si \(\Sigma\) es no vacio, entonces las biyeciones naturales entre \(\Sigma^{\ast}\) y \(\omega\), dadas en el Lema 2.3, son \(\Sigma\)-p.r..

4.11. Si \(\leq\) es un orden total sobre un alfabeto no vacio \(\Sigma\), entonces \(s^{\leq}\), \(\#^{\leq}\) y \(\ast^{\leq}\) pertenecen a \(\mathrm{PR}^{\Sigma}\)

Proof. Supongamos \(\Sigma=\{a_{1},...,a_{k}\}\) y \(\leq\) es dado por \(a_{1}<...<a_{k}\). Ya que \[\begin{aligned} s^{\leq}(\varepsilon) & =a_{1}\\ s^{\leq}(\alpha a_{i}) & =\alpha a_{i+1}\text{, para }i<k\\ s^{\leq}(\alpha a_{k}) & =s^{\leq}(\alpha)a_{1} \end{aligned}\] tenemos que \(s^{\leq}=R\left(C_{a_{1}}^{0,0},\mathcal{G}\right)\), donde \(\mathcal{G}_{a_{i}}=d_{a_{i+1}}\circ p_{1}^{0,2}\), para \(i=1,...,k-1\) y \(\mathcal{G}_{a_{k}}=d_{a_{1}}\circ p_{2}^{0,2}.\) O sea que \(s^{\leq}\in\mathrm{PR}^{\Sigma}.\) Ya que \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(t+1) & =s^{\leq}(\ast^{\leq}(t)) \end{aligned}\] podemos ver que \(\ast^{\leq}\in\mathrm{PR}^{\Sigma}\). Ya que \[\begin{aligned} \#^{\leq}(\varepsilon) & =0\\ \#^{\leq}(\alpha a_{i}) & =\#^{\leq}(\alpha).k+i\text{, para }i=1,...,k, \end{aligned}\] tenemos que \(\#^{\leq}=R\left(C_{0}^{0,0},\mathcal{G}\right)\), donde \[\mathcal{G}_{a_{i}}=\lambda xy\left[x+y\right]\circ\left[\lambda xy\left[x.y\right]\circ\left[p_{1}^{1,1},C_{k}^{1,1}\right],C_{i}^{1,1}\right]\text{, para }i=1,...,k\text{.}\] O sea que \(\#^{\leq}\in\mathrm{PR}^{\Sigma}\).

4.12.

adhocprefix(a)adhocsufix \(\lambda xy\left[x\dot{-}y\right]\in\mathrm{PR}^{\Sigma}.\)
adhocprefix(b)adhocsufix \(\lambda xy\left[\max(x,y)\right]\in\mathrm{PR}^{\Sigma}.\)
adhocprefix(c)adhocsufix \(\lambda xy\left[x=y\right]\in\mathrm{PR}^{\Sigma}.\)
adhocprefix(d)adhocsufix \(\lambda xy\left[x\leq y\right]\in\mathrm{PR}^{\Sigma}.\)
adhocprefix(e)adhocsufix \(\lambda\alpha\beta\left[\alpha=\beta\right]\in\mathrm{PR}^{\Sigma}\)

Proof. (a) Primero notar que \(\lambda x\left[x\dot{-}1\right]=R\left(C_{0}^{0,0},p_{2}^{2,0}\right)\in\mathrm{PR}^{\Sigma}.\) Tambien note que \[\lambda tx\left[x\dot{-}t\right]=R\left(p_{1}^{1,0},\lambda x\left[x\dot{-}1\right]\circ p_{1}^{3,0}\right)\in\mathrm{PR}^{\Sigma}.\] O sea que \(\lambda xy\left[x\dot{-}y\right]=\lambda tx\left[x\dot{-}t\right]\circ\left[p_{2}^{2,0},p_{1}^{2,0}\right]\in\mathrm{PR}^{\Sigma}\).

(b) Note que \(\lambda xy\left[\max(x,y)\right]=\lambda xy\left[x+(y\dot{-}x)\right]\).

(d) Note que \(\lambda xy\left[x\leq y\right]=\lambda xy\left[1\dot{-}(x\dot{-}y)\right]\).

(e) Sea \(\leq\) un orden total sobre \(\Sigma.\) Ya que \[\alpha=\beta\text{ sii }\#^{\leq}(\alpha)=\#^{\leq}(\beta)\] tenemos que \[\lambda\alpha\beta\left[\alpha=\beta\right]=\lambda xy\left[x=y\right]\circ\left[\#^{\leq}\circ p_{1}^{0,2},\#^{\leq}\circ p_{2}^{0,2}\right]\] lo cual nos dice que \(\lambda\alpha\beta\left[\alpha=\beta\right]\) es \(\Sigma\)-p.r.

4.2.3.2 Operaciones logicas entre predicados

Dados predicados \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), con el mismo dominio, definamos nuevos predicados \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) de la siguiente manera \[\begin{aligned} & \begin{array}{rll} (P\vee Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ o }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\\ & \begin{array}{rll} (P\wedge Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ y }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\\ & \begin{array}{rll} \lnot P:S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=0\\ 0 & & \text{si }P(\vec{x},\vec{\alpha})=1 \end{array}\right. \end{array} \end{aligned}\]

4.13. Si \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) son predicados \(\Sigma\)-p.r., entonces \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) lo son tambien.

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

4.2.3.3 Conjuntos \(\Sigma\)-recursivos primitivos

Un conjunto \(\Sigma\)-mixto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es llamado \(\Sigma\)-recursivo primitivo si su funcion caracteristica \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. (Notese que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es el predicado \(\lambda\vec{x}\vec{\alpha}\left[(\vec{x},\vec{\alpha})\in S\right]\).)

4.14. Si \(S_{1},S_{2}\subseteq\omega^{n}\times\Sigma^{\ast m}\) son \(\Sigma\)-p.r., entonces \(S_{1}\cup S_{2}\), \(S_{1}\cap S_{2}\) y \(S_{1}-S_{2}\) lo son.

Proof. Note que \[\begin{aligned} \chi_{S_{1}\cup S_{2}}^{\omega^{n}\times\Sigma^{\ast m}} & =(\chi_{S_{1}}^{\omega^{n}\times\Sigma^{\ast m}}\vee\chi_{S_{2}}^{\omega^{n}\times\Sigma^{\ast m}})\\ \chi_{S_{1}\cap S_{2}}^{\omega^{n}\times\Sigma^{\ast m}} & =(\chi_{S_{1}}^{\omega^{n}\times\Sigma^{\ast m}}\wedge\chi_{S_{2}}^{\omega^{n}\times\Sigma^{\ast m}})\\ \chi_{S_{1}-S_{2}}^{\omega^{n}\times\Sigma^{\ast m}} & =\lambda xy\left[x\dot{-}y\right]\circ\left[\chi_{S_{1}}^{\omega^{n}\times\Sigma^{\ast m}},\chi_{S_{2}}^{\omega^{n}\times\Sigma^{\ast m}}\right] \end{aligned}\]

Proof. Si \(S=\emptyset\), entonces es claro que \(S\) es \(\Sigma\)-p.r.. Probaremos ahora el lema para el caso en que \(S\) tiene un solo elemento. Supongamos entonces \[S=\{(z_{1},...,z_{n},\gamma_{1},...,\gamma_{m})\}.\] Note que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es el siguiente predicado \[\left(\chi_{\{z_{1}\}}^{\omega}\circ p_{1}^{n,m}\wedge...\wedge\chi_{\{z_{n}\}}^{\omega}\circ p_{n}^{n,m}\wedge\chi_{\{\gamma_{1}\}}^{\Sigma^{\ast}}\circ p_{n+1}^{n,m}\wedge...\wedge\chi_{\{\gamma_{m}\}}^{\Sigma^{\ast}}\circ p_{n+m}^{n,m}\right).\] Ya que los predicados \[\begin{aligned} \chi_{\{z_{i}\}}^{\omega} & =\lambda xy\left[x=y\right]\circ\left[p_{1}^{1,0},C_{z_{i}}^{1,0}\right]\\ \chi_{\{\gamma_{i}\}}^{\Sigma^{\ast}} & =\lambda\alpha\beta\left[\alpha=\beta\right]\circ\left[p_{1}^{0,1},C_{\gamma_{i}}^{0,1}\right] \end{aligned}\] son \(\Sigma\)-p.r., el Lema 4.13 (aplicado \((n+m)-1\) veces), implica que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. Cuando \(S\) tiene mas de un elemento, ya que entonces es la union de una cantidad finita de conjuntos de un solo elemento, se puede aplicar el Lema 4.14 (\(\left\vert S\right\vert -1\) veces) para obtener que \(S\) es \(\Sigma\)-p.r..

El siguiente lema caracteriza cuando un conjunto rectangular es \(\Sigma\)-p.r..

4.15. Supongamos \(S_{1},...,S_{n}\subseteq\omega\), \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) son conjuntos no vacios. Entonces \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-p.r. sii \(S_{1},...,S_{n},L_{1},...,L_{m}\) son \(\Sigma\)-p.r.

Proof. (\(\Rightarrow\)) Veremos por ejemplo que \(L_{1}\) es \(\Sigma\)-p.r.. Sea \((z_{1},...,z_{n},\zeta_{1},...,\zeta_{m})\) un elemento fijo de \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}.\) Note que \[\alpha\in L_{1}\text{ sii }(z_{1},...,z_{n},\alpha,\zeta_{2},...,\zeta_{m})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m},\] lo cual implica que \[\chi_{L_{1}}^{\Sigma^{\ast}}=\chi_{S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}^{\omega^{n}\times\Sigma^{\ast m}}\circ\left[C_{z_{1}}^{0,1},...,C_{z_{n}}^{0,1},p_{1}^{0,1},C_{\zeta_{2}}^{0,1},...,C_{\zeta_{m}}^{0,1}\right]\] (\(\Leftarrow\)) Note que \(\chi_{S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}^{\omega^{n}\times\Sigma^{\ast m}}\) es el predicado \[\left(\chi_{S_{1}}^{\omega}\circ p_{1}^{n,m}\wedge...\wedge\chi_{S_{n}}^{\omega}\circ p_{n}^{n,m}\wedge\chi_{L_{1}}^{\Sigma^{\ast}}\circ p_{n+1}^{n,m}\wedge...\wedge\chi_{L_{m}}^{\Sigma^{\ast}}\circ p_{n+m}^{n,m}\right).\]

Dada una funcion \(f\) y un conjunto \(S\subseteq D_{f}\), usaremos \(f|_{S}\) para denotar la restriccion de \(f\) al conjunto \(S\), i.e. \(f|_{S}=f\cap(S\times I_{f})\). Notese que \(f|_{S}\) es la funcion dada por \[D_{f|_{S}}=S\text{ \ \ \ y \ \ }f|_{S}(e)=f(e)\text{, para cada }e\in S\]

4.16. Sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Supongamos \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) es \(\Sigma\)-p.r.. Si \(S\subseteq D_{f}\) es \(\Sigma\)-p.r., entonces \(f|_{S}\) es \(\Sigma\)-p.r..

Proof. Supongamos \(O=\Sigma^{\ast}\). Entonces \[f|_{S}=\lambda x\alpha\left[\alpha^{x}\right]\circ\left[Suc\circ Pred\circ\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}},f\right]\] lo cual nos dice que \(f|_{S}\) es \(\Sigma\)-p.r.. El caso \(O=\omega\) es similar usando \(\lambda xy\left[x^{y}\right]\) en lugar de \(\lambda x\alpha\left[\alpha^{x}\right]\).

Usando el lema anterior en combinacion con el Lema 4.13 podemos ver que muchos predicados usuales son \(\Sigma\)-p.r.. Por ejemplo sea \[P=\lambda x\alpha\beta\gamma\left[x=\left\vert \gamma\right\vert \wedge\alpha=\gamma^{Pred(\left\vert \beta\right\vert )}\right].\] Notese que \[D_{P}=\omega\times\Sigma^{\ast}\times(\Sigma^{\ast}-\{\varepsilon\})\times\Sigma^{\ast}\] es \(\Sigma\)-p.r. ya que \[\chi_{D_{P}}^{\omega\times\Sigma^{\ast3}}=\lnot\lambda\alpha\beta\left[\alpha=\beta\right]\circ\left[p_{3}^{1,3},C_{\varepsilon}^{1,3}\right]\] Tambien note que los predicados \[\begin{aligned} & \lambda x\alpha\beta\gamma\left[x=\left\vert \gamma\right\vert \right]\\ & \lambda x\alpha\beta\gamma\left[\alpha=\gamma^{Pred(\left\vert \beta\right\vert )}\right] \end{aligned}\] son \(\Sigma\)-p.r. ya que pueden obtenerse componiendo funciones \(\Sigma\)-p.r.. O sea que \(P\) es \(\Sigma\)-p.r. ya que \[P=\left(\lambda x\alpha\beta\gamma\left[x=\left\vert \gamma\right\vert \right]|_{D_{P}}\wedge\lambda x\alpha\beta\gamma\left[\alpha=\gamma^{Pred(\left\vert \beta\right\vert )}\right]\right).\]

4.17. Sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) es \(\Sigma\)-p.r., entonces existe una funcion \(\Sigma\)-p.r. \(\bar{f}:\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), tal que \(f=\bar{f}|_{D_{f}}\).

Proof. Es facil ver por induccion en \(k\) que el enunciado se cumple para cada \(f\in\mathrm{PR}_{k}^{\Sigma}\)

(\(\Rightarrow\)) Note que \(S=D_{Pred\circ\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}}\).

(\(\Leftarrow\)) Probaremos por induccion en \(k\) que \(D_{F}\) es \(\Sigma\)-p.r., para cada \(F\in\mathrm{PR}_{k}^{\Sigma}.\) El caso \(k=0\) es facil\(.\) Supongamos el resultado vale para un \(k\) fijo y supongamos \(F\in\mathrm{PR}_{k+1}^{\Sigma}.\) Veremos entonces que \(D_{F}\) es \(\Sigma\)-p.r.. Hay varios casos. Consideremos primero el caso en que \(F=R(f,g)\), donde \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\\ g & :\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}, \end{aligned}\] con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) conjuntos no vacios y \(f,g\in\mathrm{PR}_{k}^{\Sigma}\). Notese que por definicion de \(R(f,g)\), tenemos que \[D_{F}=\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}.\] Por hipotesis inductiva tenemos que \(D_{f}=S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-p.r., lo cual por el Lema 4.15 nos dice que los conjuntos \(S_{1},...,S_{n}\), \(L_{1},...,L_{m}\) son \(\Sigma\)-p.r.. Ya que \(\omega\) es \(\Sigma\)-p.r., el Lema 4.15 nos dice que \(D_{F}\) es \(\Sigma\)-p.r..

Supongamos ahora que \(F=g\circ[g_{1},...,g_{r}]\) con \(g,g_{1},...,g_{r}\in\mathrm{PR}_{k}^{\Sigma}\). Si \(F=\emptyset\), entonces es claro que \(D_{F}=\emptyset\) es \(\Sigma\)-p.r.. Supongamos entonces que \(F\) no es la funcion \(\emptyset\). Tenemos entonces que \(r\) es de la forma \(n+m\) y \[\begin{aligned} g & :D_{g}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\\ g_{i} & :D_{g_{i}}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega\text{, }i=1,...,n\\ g_{i} & :D_{g_{i}}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\Sigma^{\ast},i=n+1,...,n+m \end{aligned}\] con \(O\in\{\omega,\Sigma^{\ast}\}\) y \(k,l\in\omega\). Por Lema 4.17, hay funciones \(\Sigma\)-p.r. \(\bar{g}_{1},...,\bar{g}_{n+m}\) las cuales son \(\Sigma\)-totales y cumplen \[g_{i}=\bar{g}_{i}|_{D_{g_{i}}}\text{, para }i=1,...,n+m.\] Por hipotesis inductiva los conjuntos \(D_{g}\), \(D_{g_{i}}\), \(i=1,...,n+m\), son \(\Sigma\)-p.r. y por lo tanto \[S=\bigcap_{i=1}^{n+m}D_{g_{i}}\] lo es. Notese que \[\chi_{D_{F}}^{\omega^{k}\times\Sigma^{\ast l}}=(\chi_{D_{g}}^{\omega^{n}\times\Sigma^{\ast m}}\circ\left[\bar{g}_{1},...,\bar{g}_{n+m}\right]\wedge\chi_{S}^{\omega^{k}\times\Sigma^{\ast l}})\] lo cual nos dice que \(D_{F}\) es \(\Sigma\)-p.r..

4.2.3.4 Lema de division por casos para funciones \(\Sigma\)-p.r.

Una observacion interesante es que si \(f_{i}:D_{f_{i}}\rightarrow O\), \(i=1,...,k\), son funciones tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\), entonces \(f_{1}\cup...\cup f_{k}\) es la funcion \[\begin{array}{rll} D_{f_{1}}\cup...\cup D_{f_{k}} & \rightarrow & O\\ e & \rightarrow & \left\{ \begin{array}{clc} f_{1}(e) & & \text{si }e\in D_{f_{1}}\\ \vdots & & \vdots\\ f_{k}(e) & & \text{si }e\in D_{f_{k}} \end{array}\right. \end{array}\]

4.18. Sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Supongamos \(f_{i}:D_{f_{i}}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), \(i=1,...,k\), son funciones \(\Sigma\)-p.r. tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j.\) Entonces \(f_{1}\cup...\cup f_{k}\) es \(\Sigma\)-p.r..

Proof. Supongamos \(O=\Sigma^{\ast}\) y \(k=2.\) Sean \[\bar{f}_{i}:\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast},i=1,2,\] funciones \(\Sigma\)-p.r. tales que \(\bar{f}_{i}|_{D_{f_{i}}}=f_{i}\), \(i=1,2\) (Lema 4.17)\(.\) Por Lema 4.4 los conjuntos \(D_{f_{1}}\) y \(D_{f_{2}}\) son \(\Sigma\)-p.r. y por lo tanto lo es \(D_{f_{1}}\cup D_{f_{2}}\). Ya que \[f_{1}\cup f_{2}=\left(\lambda\alpha\beta\left[\alpha\beta\right]\circ\left[\lambda x\alpha\left[\alpha^{x}\right]\circ\left[\chi_{D_{f_{1}}}^{\omega^{n}\times\Sigma^{\ast m}},\bar{f}_{1}\right],\lambda x\alpha\left[\alpha^{x}\right]\circ\left[\chi_{D_{f_{2}}}^{\omega^{n}\times\Sigma^{\ast m}},\bar{f}_{2}\right]\right]\right)|_{D_{f_{1}}\cup D_{f_{2}}}\] tenemos que \(f_{1}\cup f_{2}\) es \(\Sigma\)-p.r..

El caso \(k>2\) puede probarse por induccion ya que \[f_{1}\cup...\cup f_{k}=(f_{1}\cup...\cup f_{k-1})\cup f_{k}.\]

Proof. Supongamos \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), con \(D_{f}=\{e_{1},...,e_{k}\}\). Por el Corolario 4.1, cada \(\{e_{i}\}\) es \(\Sigma\)-p.r. por lo cual el Lema 4.16 nos dice que \(C_{f(e_{i})}^{n,m}|_{\{e_{i}\}}\) es \(\Sigma\)-p.r.. O sea que \[f=C_{f(e_{1})}^{n,m}|_{\{e_{1}\}}\cup...\cup C_{f(e_{k})}^{n,m}|_{\{e_{k}\}}\] es \(\Sigma\)-p.r..

Recordemos que dados \(i\in\omega\) y \(\alpha\in\Sigma^{\ast}\), definimos \[\left[\alpha\right]_{i}=\left\{ \begin{array}{lll} i\text{-esimo elemento de }\alpha & & \text{si }1\leq i\leq\left\vert \alpha\right\vert \\ \varepsilon & & \text{caso contrario} \end{array}\right.\]

4.19. \(\lambda i\alpha\left[[\alpha]_{i}\right]\) es \(\Sigma\)-p.r..

Proof. Note que \[\begin{aligned} _{i} & =\varepsilon\\{} [\alpha a]_{i} & =\left\{ \begin{array}{lll} [\alpha]_{i} & & \text{si }i\neq\left\vert \alpha\right\vert +1\\ a & & \text{si }i=\left\vert \alpha\right\vert +1 \end{array}\right. \end{aligned}\] lo cual dice que \(\lambda i\alpha\left[[\alpha]_{i}\right]=R\left(C_{\varepsilon}^{1,0},\mathcal{G}\right)\), donde \(\mathcal{G}_{a}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\rightarrow\Sigma^{\ast}\) es dada por \[\mathcal{G}_{a}(i,\alpha,\zeta)=\left\{ \begin{array}{lll} \zeta & & \text{si }i\neq\left\vert \alpha\right\vert +1\\ a & & \text{si }i=\left\vert \alpha\right\vert +1 \end{array}\right.\] O sea que solo resta probar que cada \(\mathcal{G}_{a}\) es \(\Sigma\)-p.r.. Primero note que los conjuntos \[\begin{aligned} S_{1} & =\left\{ (i,\alpha,\zeta)\in\omega\times\Sigma^{\ast}\times\Sigma^{\ast}:i\neq\left\vert \alpha\right\vert +1\right\} \\ S_{2} & =\left\{ (i,\alpha,\zeta)\in\omega\times\Sigma^{\ast}\times\Sigma^{\ast}:i=\left\vert \alpha\right\vert +1\right\} \end{aligned}\] son \(\Sigma\)-p.r. ya que \[\begin{aligned} \chi_{S_{1}}^{\omega\times\Sigma^{\ast}\times\Sigma^{\ast}} & =\lambda xy\left[x\neq y\right]\circ\left[p_{1}^{1,2},Suc\circ\lambda\alpha\left[\left\vert \alpha\right\vert \right]\circ p_{2}^{1,2}\right]\\ \chi_{S_{2}}^{\omega\times\Sigma^{\ast}\times\Sigma^{\ast}} & =\lambda xy\left[x=y\right]\circ\left[p_{1}^{1,2},Suc\circ\lambda\alpha\left[\left\vert \alpha\right\vert \right]\circ p_{2}^{1,2}\right] \end{aligned}\] Ya que \[\mathcal{G}_{a}=p_{3}^{1,2}|_{S_{1}}\cup C_{a}^{1,2}|_{S_{2}}\] el Lema 4.18 nos dice que \(\mathcal{G}_{a}\) es \(\Sigma\)-p.r., para cada \(a\in\Sigma\).

4.2.3.5 Sumatoria, productoria y concatenatoria de funciones \(\Sigma\)-p.r.

Sea \(\Sigma\) un alfabeto finito. Sea \(f:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\), con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacios. Para \(x,y\in\omega\) y \((\vec{x},\vec{\alpha})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\), definamos \[\begin{aligned} \sum\limits_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 0 & & \text{si }x>y\\ f(x,\vec{x},\vec{\alpha})+f(x+1,\vec{x},\vec{\alpha})+...+f(y,\vec{x},\vec{\alpha}) & & \text{si }x\leq y \end{array}\right.\\ \prod\limits_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 1 & & \text{si }x>y\\ f(x,\vec{x},\vec{\alpha}).f(x+1,\vec{x},\vec{\alpha})....f(y,\vec{x},\vec{\alpha}) & & \text{si }x\leq y \end{array}\right. \end{aligned}\] En forma similar, cuando \(I_{f}\subseteq\Sigma^{\ast}\), definamos \[\overset{t=y}{\underset{t=x}{\subset}}f(t,\vec{x},\vec{\alpha})=\left\{ \begin{array}{lll} \varepsilon & & \text{si }x>y\\ f(x,\vec{x},\vec{\alpha})f(x+1,\vec{x},\vec{\alpha})....f(y,\vec{x},\vec{\alpha}) & & \text{si }x\leq y \end{array}\right.\] Note que, en virtud de la definicion anterior, el dominio de las funciones \[\lambda xy\vec{x}\vec{\alpha}\left[\sum_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\ \ \ \ \ \ \ \ \ \ \ \ \lambda xy\vec{x}\vec{\alpha}\left[\prod_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\ \ \ \ \ \ \ \ \ \ \ \ \lambda xy\vec{x}\vec{\alpha}\left[\subset_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\] es \(\omega\times\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\).

4.20. Sea \(\Sigma\) un alfabeto finito.

adhocprefix(a)adhocsufix Si \(f:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\) es \(\Sigma\)-p.r., con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacios, entonces las funciones \(\lambda xy\vec{x}\vec{\alpha}\left[\sum_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\) y \(\lambda xy\vec{x}\vec{\alpha}\left[\prod_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\) son \(\Sigma\)-p.r.
adhocprefix(b)adhocsufix Si \(f:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Sigma^{\ast}\) es \(\Sigma\)-p.r., con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacios, entonces la funcion \(\lambda xy\vec{x}\vec{\alpha}\left[\subset_{t=x}^{t=y}f(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r.

Proof. (a) Sea \(G=\lambda tx\vec{x}\vec{\alpha}\left[\sum_{i=x}^{i=t}f(i,\vec{x},\vec{\alpha})\right]\). Ya que \[\lambda xy\vec{x}\vec{\alpha}\left[\sum_{i=x}^{i=y}f(i,\vec{x},\vec{\alpha})\right]=G\circ\left[p_{2}^{n+2,m},p_{1}^{n+2,m},p_{3}^{n+2,m},...,p_{n+m+2}^{n+2,m}\right]\] solo tenemos que probar que \(G\) es \(\Sigma\)-p.r.. Primero note que \[\begin{aligned} G(0,x,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 0 & & \text{si }x>0\\ f(0,\vec{x},\vec{\alpha}) & & \text{si }x=0 \end{array}\right.\\ G(t+1,x,\vec{x},\vec{\alpha}) & =\left\{ \begin{array}{lll} 0 & & \text{si }x>t+1\\ G(t,x,\vec{x},\vec{\alpha})+f(t+1,\vec{x},\vec{\alpha}) & & \text{si }x\leq t+1 \end{array}\right. \end{aligned}\] O sea que si definimos \[\begin{array}{rll} h:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m} & \rightarrow & \omega\\ (x,\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 0 & & \text{si }x>0\\ f(0,\vec{x},\vec{\alpha}) & & \text{si }x=0 \end{array}\right. \end{array}\] \[\begin{array}{rll} g:\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m} & \rightarrow & \omega\\ (A,t,x,\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 0 & & \text{si }x>t+1\\ A+f(t+1,\vec{x},\vec{\alpha}) & & \text{si }x\leq t+1 \end{array}\right. \end{array}\] tenemos que \(G=R(h,g)\). Es decir que solo nos falta probar que \(h\) y \(g\) son \(\Sigma\)-p.r.. Sean \[\begin{aligned} D_{1} & =\left\{ (x,\vec{x},\vec{\alpha})\in\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x>0\right\} \\ D_{2} & =\left\{ (x,\vec{x},\vec{\alpha})\in\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x=0\right\} \\ H_{1} & =\left\{ (z,t,x,\vec{x},\vec{\alpha})\in\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x>t+1\right\} \\ H_{2} & =\left\{ (z,t,x,\vec{x},\vec{\alpha})\in\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}:x\leq t+1\right\} . \end{aligned}\] Notese que \[\begin{aligned} h & =C_{0}^{n+1,m}|_{D_{1}}\cup\lambda x\vec{x}\vec{\alpha}\left[f(0,\vec{x},\vec{\alpha})\right]|_{D_{2}}\\ g & =C_{0}^{n+3,m}|_{H_{1}}\cup\lambda Atx\vec{x}\vec{\alpha}\left[A+f(t+1,\vec{x},\vec{\alpha})\right])|_{H_{2}} \end{aligned}\] Ya que \(f\) es \(\Sigma\)-p.r. y \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[f(0,\vec{x},\vec{\alpha})\right] & =f\circ\left[C_{0}^{n+1,m},p_{2}^{n+1,m},p_{3}^{n+1,m},...,p_{n+1+m}^{n+1,m}\right]\\ \lambda Atx\vec{x}\vec{\alpha}\left[A+f(t+1,\vec{x},\vec{\alpha})\right]) & =\lambda xy[x+y]\circ\left[p_{1}^{n+3,m},f\circ\left[Suc\circ p_{2}^{n+3,m},p_{4}^{n+3,m},...,p_{n+3+m}^{n+3,m}\right]\right] \end{aligned}\] tenemos que \(\lambda x\vec{x}\vec{\alpha}\left[f(0,\vec{x},\vec{\alpha})\right]\) y \(\lambda Atx\vec{x}\vec{\alpha}\left[A+f(t+1,\vec{x},\vec{\alpha})\right])\) son \(\Sigma\)-p.r..O sea que para probar que \(h\) y \(g\) son \(\Sigma\)-p.r.solo nos falta ver que los conjuntos \(D_{1},D_{2},H_{1},H_{2}\) son \(\Sigma\)-p.r.. y aplicar luego el Lema 4.16. Veamos que por ejemplo \(H_{1}\) lo es. Es decir debemos ver que \(\chi_{H_{1}}^{\omega^{3+n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r.. Ya que \(f\) es \(\Sigma\)-p.r. tenemos que \(D_{f}=\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-p.r., lo cual por el Lema 4.15 nos dice que los conjuntos \(S_{1},...,S_{n}\), \(L_{1},...,L_{m}\) son \(\Sigma\)-p.r.. Ya que \(\omega\) es \(\Sigma\)-p.r., el Lema 4.15 nos dice que \(R=\omega^{3}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-p.r.. Notese que \(\chi_{H_{1}}^{\omega^{3+n}\times\Sigma^{\ast m}}=(\chi_{R}^{\omega^{3+n}\times\Sigma^{\ast m}}\wedge\lambda ztx\vec{x}\vec{\alpha}\left[x>t+1\right])\) por lo cual \(\chi_{H_{1}}^{\omega^{3+n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-p.r. ya que es la conjuncion de dos predicados \(\Sigma\)-p.r.

Veamos un ejemplo de como se puede aplicar el lema anterior. Sea \(F=\lambda yx_{1}\left[\sum_{t=0}^{t=y}(x_{1})^{t}\right]\). Es claro que \(D_{F}=\omega^{2}\). Para ver que \(F\) es \(\Sigma\)-p.r. aplicaremos el lema anterior por lo cual es importante encontrar la \(f\) adecuada a la cual se le aplicara el lema. Tomemos \(f=\lambda tx_{1}[(x_{1})^{t}]\). Claramente \(f\) es \(\Sigma\)-p.r. por lo cual el lema anterior nos dice que \[G=\lambda xyx_{1}\left[\sum_{t=x}^{t=y}f(t,x_{1})\right]=\lambda xyx_{1}\left[\sum_{t=x}^{t=y}(x_{1})^{t}\right]\] es \(\Sigma\)-p.r.. Claramente \(G\) no es la funcion \(F\) pero es en algun sentido "mas amplia" que \(F\) ya que tiene una variable mas y se tiene que \(F(y,x_{1})=G(0,y,x_{1})\), para cada \(y,x_{1}\in\omega\). Es facil ver que \[F=G\circ\left[C_{0}^{2,0},p_{1}^{2,0},p_{2}^{2,0}\right]\] por lo cual \(F\) es \(\Sigma\)-p.r..

4.2.3.6 Cuantificacion acotada de predicados \(\Sigma\)-p.r. con dominio rectangular

Ses \(P:S\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\) un predicado, con \(S,S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacios. Supongamos \(\bar{S}\subseteq S\). Entonces la expresion Booleana \[(\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\] depende de las variables \(x,\vec{x},\vec{\alpha}\) y valdra \(1\) en una \((1+n+m)\)-upla \((x,\vec{x},\vec{\alpha})\) cuando \(P(t,\vec{x},\vec{\alpha})\) sea igual a \(1\) para cada \(t\in\{u\in\bar{S}:u\leq x\}\); y \(0\) en caso contrario. Tenemos entonces que el dominio del predicado \[\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\] es \(\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). En forma analoga se define la forma de interpretar la expresion Booleana \[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\] Cabe destacar que \[\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]=\lnot\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;\lnot P(t,\vec{x},\vec{\alpha})\right]\]

Tambien podemos cuantificar sobre variable alfabetica. Sea \(P:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times L\rightarrow\omega\) un predicado, con \(S_{1},...,S_{n}\subseteq\omega\) y \(L,L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacios. Supongamos \(\bar{L}\subseteq L\). Entonces la expresion Booleana \[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\] depende de las variables \(x,\vec{x},\vec{\alpha}\) y valdra \(1\) en una \((1+n+m)\)-upla \((x,\vec{x},\vec{\alpha})\) cuando \(P(\vec{x},\vec{\alpha},\alpha)\) sea igual a \(1\) para cada \(\alpha\in\{\beta\in\bar{L}:\left\vert \beta\right\vert \leq x\}\); y \(0\) en caso contrario. Tenemos entonces que el dominio del predicado \[\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right]\] es \(\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). En forma analoga se define la forma de interpretar la expresion Booleana \[(\exists\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\] Cabe destacar que \[\lambda x\vec{x}\vec{\alpha}\left[(\exists\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}P(\vec{x},\vec{\alpha},\alpha)\right]=\lnot\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\lnot P(\vec{x},\vec{\alpha},\alpha)\right]\]

4.21. Sea \(\Sigma\) un alfabeto finito.

adhocprefix(a)adhocsufix Sea \(P:S\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\) un predicado \(\Sigma\)-p.r., con \(S,S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacios. Supongamos \(\bar{S}\subseteq S\) es \(\Sigma\)-p.r.. Entonces \(\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\) y \(\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\) son predicados \(\Sigma\)-p.r..
adhocprefix(b)adhocsufix Sea \(P:S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times L\rightarrow\omega\) un predicado \(\Sigma\)-p.r., con \(S_{1},...,S_{n}\subseteq\omega\) y \(L,L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) no vacios. Supongamos \(\bar{L}\subseteq L\) es \(\Sigma\)-p.r.. Entonces \(\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right]\) y \(\lambda x\vec{x}\vec{\alpha}\left[(\exists\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right]\) son predicados \(\Sigma\)-p.r..

Proof. (a) Sea \[\bar{P}=P|_{\bar{S}\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\cup C_{1}^{1+n,m}|_{(\omega-\bar{S})\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}}\] Notese que \(\bar{P}\) tiene dominio \(\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) y es \(\Sigma\)-p.r.. Ya que \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}P(t,\vec{x},\vec{\alpha})\right] & =\lambda x\vec{x}\vec{\alpha}\left[\prod\limits_{t=0}^{t=x}\bar{P}(t,\vec{x},\vec{\alpha})\right]\\ & =\lambda xy\vec{x}\vec{\alpha}\left[\prod\limits_{t=x}^{t=y}\bar{P}(t,\vec{x},\vec{\alpha})\right]\circ\left[C_{0}^{1+n,m},p_{1}^{1+n,m},...,p_{1+n+m}^{1+n,m}\right] \end{aligned}\] el Lema 4.20 implica que \(\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r..

Ya que \[\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]=\lnot\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\bar{S})_{t\leq x}\;\lnot P(t,\vec{x},\vec{\alpha})\right]\] tenemos que \(\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})_{t\leq x}\;P(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r.

(b) Haremos solo el caso del cuantificador \(\forall\). Primero supongamos que \(\Sigma=\emptyset\). Ya que \(L,L_{1},...,L_{m}\) son no vacios, debera suceder que \(L=L_{1}=...=L_{m}=\{\varepsilon\}\). Ya que \(\bar{L}\subseteq L\), tenemos que \(\bar{L}=\emptyset\) o \(\bar{L}=\{\varepsilon\}\). Si \(\bar{L}=\emptyset\), entonces \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right] & =\lambda x\vec{x}\vec{\alpha}\left[1\right]\\ & =C_{1}^{1+n,m} \end{aligned}\] por lo cual es \(\Sigma\)-p.r.

Si \(\bar{L}=\{\varepsilon\}\), entonces \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right] & =\lambda x\vec{x}\vec{\alpha}\left[(P(\vec{x},\vec{\alpha},\varepsilon)\right]\\ & =P\circ\left[p_{2}^{1+n,m},...,p_{1+n+m}^{1+n,m},C_{\varepsilon}^{1+n,m},\right] \end{aligned}\] por lo cual es \(\Sigma\)-p.r.

Ahora supongamos \(\Sigma\) es no vacio. Sea \(\leq\) un orden total sobre \(\Sigma.\) Sea \(k\) el cardinal de \(\Sigma\). Primero notese que

\(\left\vert \alpha\right\vert \leq x\) sii \(\#^{\leq}(\alpha)\leq\sum_{\iota=1}^{i=x}k^{i}\), cualesquiera sean \(x\in\omega\) y \(\alpha\in\Sigma^{\ast}\)

(queda como ejercicio probar (*). Sean \[\begin{aligned} \#^{\leq}(L) & =\{\#^{\leq}(\alpha):\alpha\in L\}\\ \#^{\leq}(\bar{L}) & =\{\#^{\leq}(\alpha):\alpha\in\bar{L}\} \end{aligned}\] Notese que \[\begin{aligned} \chi_{\#^{\leq}(L)}^{\omega} & =\chi_{L}^{\Sigma^{\ast}}\circ\ast^{\leq}\\ \chi_{\#^{\leq}(\bar{L})}^{\omega} & =\chi_{\bar{L}}^{\Sigma^{\ast}}\circ\ast^{\leq} \end{aligned}\] por lo cual \(\#^{\leq}(L)\) y \(\#^{\leq}(\bar{L})\) son \(\Sigma\)-p.r.. Sea \(H=\lambda t\vec{x}\vec{\alpha}\left[P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right].\) Notese que \[D_{H}=\#^{\leq}(L)\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\] y \(H\) es \(\Sigma\)-p.r.. O sea que por (a) tenemos que \[\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq x}H(t,\vec{x},\vec{\alpha})\right]=\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq x}P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right]\] es \(\Sigma\)-p.r.. Llamemos \(Q\) al predicado \(\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq x}P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right]\). Tenemos que \[\begin{aligned} \lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}P(\vec{x},\vec{\alpha},\alpha)\right] & =\lambda x\vec{x}\vec{\alpha}\left[(\forall t\in\#^{\leq}(\bar{L}))_{t\leq\sum_{\iota=1}^{i=x}k^{i}}P(\vec{x},\vec{\alpha},\ast^{\leq}(t))\right]\text{ (por (*))}\\ & =Q\circ\left[\lambda x\vec{x}\vec{\alpha}\left[\sum\limits_{\iota=1}^{i=x}k^{i}\right],p_{1}^{1+n,m},...,p_{1+n+m}^{1+n,m}\right] \end{aligned}\] Pero \(\lambda x\vec{x}\vec{\alpha}\left[\sum\limits_{\iota=1}^{i=x}k^{i}\right]\) es \(\Sigma\)-p.r. (ejercicio), lo cual nos dice que \(\lambda x\vec{x}\vec{\alpha}\left[(\forall\alpha\in\bar{L})_{\left\vert \alpha\right\vert \leq x}\;P(\vec{x},\vec{\alpha},\alpha)\right]\) lo es

OBSERVACION: La cuantificacion no acotada no preserva la propiedad de ser \(\Sigma\)-p.r.. Como veremos mas adelante si elejimos bien al predicado \(\Sigma\)-p.r. \(P\), obtenemos que el predicado \(\lambda\vec{x}\vec{\alpha}\left[(\exists t\in\bar{S})\;P(t,\vec{x},\vec{\alpha})\right]\) no solo no es \(\Sigma\)-p.r. sino que tampoco es \(\Sigma\)-efectivamente computable (Teorema 4.15).

Algunos ejemplos en los cuales cuantificacion acotada se aplica naturalmente son dados a continuacion.

4.22. Sea \(\Sigma\) un alfabeto finito.

adhocprefix(a)adhocsufix El predicado \(\lambda xy\left[x\text{ divide }y\right]\) es \(\Sigma\)-p.r..
adhocprefix(b)adhocsufix El predicado \(\lambda x\left[x\text{ es primo}\right]\) es \(\Sigma\)-p.r..
adhocprefix(c)adhocsufix El predicado \(\lambda\alpha\beta\left[\alpha\text{\ }\mathrm{inicial}\ \beta\right]\) es \(\Sigma\)-p.r..

Proof. (a) Sea \(P=\lambda tx_{1}x_{2}\left[x_{2}=t.x_{1}\right]\). Es claro que \(P\) es \(\Sigma\)-p.r.. El lema anterior nos dice que \(\lambda xx_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x}\;P(t,x_{1},x_{2})\right]\) es \(\Sigma\)-p.r.. Notese que \(x_{1}\) divide \(x_{2}\) si y solo si hay un \(t\leq x_{2}\) tal que \(x_{2}=t.x_{1}\). Esto nos dice que \[\lambda x_{1}x_{2}\left[x_{1}\text{ divide }x_{2}\right]=\lambda x_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x_{2}}\;P(t,x_{1},x_{2})\right]\] Pero \[\lambda x_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x_{2}}\;P(t,x_{1},x_{2})\right]=\lambda xx_{1}x_{2}\left[(\exists t\in\omega)_{t\leq x}\;P(t,x_{1},x_{2})\right]\circ\left[p_{2}^{2,0},p_{1}^{2,0},p_{2}^{2,0}\right]\] por lo cual \(\lambda x_{1}x_{2}\left[x_{1}\text{ divide }x_{2}\right]\) es \(\Sigma\)-p.r.

(b) Ya que \[x\text{ es primo sii }x>1\wedge\left((\forall t\in\omega)_{t\leq x}\;t=1\vee t=x\vee\lnot(t\text{ divide }x)\right)\] podemos usar un argumento similar al de la prueba de (a).

La idea fundamental subyacente en las aplicaciones anteriores es que en muchos casos de predicados obtenidos por cuantificacion a partir de otros predicados, la variable cuantificada tiene una cota natural en terminos de las otras variables y entonces componiendo adecuadamente se lo puede presentar como un caso de cuantificacion acotada

4.2.4 Minimizacion y funciones \(\Sigma\)-recursivas

Tal como fue explicado anteriormente, para obtener la clase de las funciones \(\Sigma\)-recursivas debemos agregar un nuevo constructor a los ya definidos de composicion y recursion primitiva, a saber el constructor de minimizacion. Tiene dos casos aunque solo usaremos el primero para la definicion de funcion \(\Sigma\)-recursiva.

4.2.4.1 Minimizacion de variable numerica

Sea \(\Sigma\) un alfabeto finito y sea \(P:D_{P}\subseteq\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) un predicado. Dado \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\), cuando exista al menos un \(t\in\omega\) tal que \(P(t,\vec{x},\vec{\alpha})=1\), usaremos \(\min_{t}P(t,\vec{x},\vec{\alpha})\) para denotar al menor de tales \(t^{\prime}s\). Notese que la expresion \(\min_{t}P(t,\vec{x},\vec{\alpha})\) esta definida solo para aquellas \((n+m)\)-uplas \((\vec{x},\vec{\alpha})\) para las cuales hay al menos un \(t\) tal que se da \(P(t,\vec{x},\vec{\alpha})=1\). Dicho de otra forma, \(\min_{t}P(t,\vec{x},\vec{\alpha})\) no estara definida cuando para cada \(t\in\omega\) se de que \((t,\vec{x},\vec{\alpha})\) no pertenece a \(D_{P}\) o \(P(t,\vec{x},\vec{\alpha})=0\). Otro detalle importante a tener en cuenta es que la expresion \(\min_{t}P(t,\vec{x},\vec{\alpha})\) no depende de la variable \(t\). Por ejemplo, las expresiones \(\min_{t}P(t,\vec{x},\vec{\alpha})\) y \(\min_{i}P(i,\vec{x},\vec{\alpha})\) son equivalentes en el sentido que estan definidas en las mismas \((n+m)\)-uplas y cuando estan definidas asumen el mismo valor.

Definamos \[M(P)=\lambda\vec{x}\vec{\alpha}\left[\min\nolimits_{t}P(t,\vec{x},\vec{\alpha})\right]\] Notese que \[\begin{aligned} D_{M(P)} & =\left\{ (\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}:(\exists t\in\omega)\ P(t,\vec{x},\vec{\alpha})\right\} \\ M(P)(\vec{x},\vec{\alpha}) & =\min\nolimits_{t}P(t,\vec{x},\vec{\alpha})\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M(P)} \end{aligned}\] Diremos que \(M(P)\) se obtiene por minimizacion de variable numerica a partir de \(P\).

Tal como lo vimos recien muchas veces que querramos encontrar un predicado \(P\) tal que \(M(P)\) sea igual a una funcion dada \(f\), sera mas facil encontrar un \(P\) el cual cumpla \[f(\vec{x},\vec{\alpha})=\mathrm{\ unico\ }t\in\omega\mathrm{\ tal\ que\ }P(t,\vec{x},\vec{\alpha})\] es decir un predicado \(P\) que caracterice al valor que toma \(f\). Enunciamos esto en forma de regla.

REGLA U: Si tenemos una funcion \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y buscamos un predicado \(P\) tal que \(f=M(P)\) muchas veces es util tratar de diseñar \(P\) de manera que para cada \((\vec{x},\vec{\alpha})\in D_{f}\) se de que \[f(\vec{x},\vec{\alpha})=\mathrm{\ unico\ }t\in\omega\mathrm{\ tal\ que\ }P(t,\vec{x},\vec{\alpha})\]

4.23. Si \(P:D_{P}\subseteq\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) es un predicado \(\Sigma\)-efectivamente computable y \(D_{P}\) es \(\Sigma\)-efectivamente computable, entonces la funcion \(M(P)\) es \(\Sigma\)-efectivamente computable.

Lamentablemente si quitamos la hipotesis en el lema anterior de que \(D_{P}\) sea \(\Sigma\)-efectivamente computable, el lema resulta falso. Mas adelante veremos un contraejemplo basado en la tesis de Church (Proposicion 4.16). Por el momento el lector puede ejercitar su comprencion del tema convenciendose de que aun teniendo un procedimiento efectivo que compute a un predicado \(P:D_{P}\subseteq\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), no es claro como construir un procedimiento efectivo que compute a \(M(P)\).

4.2.4.2 Definicion de funcion \(\Sigma\)-recursiva

Con este nuevo constructor de funciones estamos en condiciones de definir la clase de las funciones \(\Sigma\)-recursivas. Definamos los conjuntos \(\mathrm{R}_{0}^{\Sigma}\subseteq\mathrm{R}_{1}^{\Sigma}\subseteq\mathrm{R}_{2}^{\Sigma}\subseteq...\subseteq\mathrm{R}^{\Sigma}\) de la siguiente manera \[\begin{array}{lll} \mathrm{R}_{0}^{\Sigma} & = & \mathrm{PR}_{0}^{\Sigma}\\ \mathrm{R}_{k+1}^{\Sigma} & = & \mathrm{R}_{k}^{\Sigma}\cup\left\{ f\circ[f_{1},...,f_{n}]:f,f_{1},...,f_{r}\in\mathrm{R}_{k}^{\Sigma}\text{, }r\geq1\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ R(f,\mathcal{G}):R(f,\mathcal{G})\text{ esta definida y }\{f\}\cup\{\mathcal{G}_{a}:a\in\Sigma\}\subseteq\mathrm{R}_{k}^{\Sigma}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ R(f,g):R(f,g)\text{ esta definida y }f,g\in\mathrm{R}_{k}^{\Sigma}\right\} \cup\\ & & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left\{ M(P):P\text{ es un predicado }\Sigma\text{-total y }P\in\mathrm{R}_{k}^{\Sigma}\right\} \\ \mathrm{R}^{\Sigma} & = & \bigcup_{k\geq0}\mathrm{R}_{k}^{\Sigma} \end{array}\] Una funcion \(f\) es llamada \(\Sigma\)-recursiva si pertenece a \(\mathrm{R}^{\Sigma}\). Cabe destacar que aunque \(M(P)\) fue definido para predicados no necesariamente \(\Sigma\)-totales, en la definicion de los conjuntos \(\mathrm{R}_{k}^{\Sigma}\), nos restringimos al caso en que \(P\) es \(\Sigma\)-total.

Notese que \(\mathrm{PR}_{k}^{\Sigma}\subseteq\mathrm{R}_{k}^{\Sigma}\), para cada \(k\in\omega\), por lo cual \(\mathrm{PR}^{\Sigma}\subseteq\mathrm{R}^{\Sigma}\).

Proof. Dejamos al lector la prueba por induccion en \(k\) de que si \(f\in\mathrm{R}_{k}^{\Sigma}\), entonces \(f\) es \(\Sigma\)-efectivamente computable.

Este resultado no es facil de probar. Mas adelante (Proposicion 4.13) veremos ejemplos naturales de funciones \(\Sigma\)-recursivas que no son \(\Sigma\)-p.r.. Otro ejemplo natural es la famosa funcion de Ackermann.

4.2.4.3 Lema de minimizacion acotada de variable numerica de predicados \(\Sigma\)-p.r.

Aunque no siempre que \(P\in\mathrm{R}^{\Sigma}\), tendremos que \(M(P)\in\mathrm{R}^{\Sigma}\) (Proposicion 4.16), el siguiente lema nos garantiza que este es el caso cuando \(P\in\mathrm{PR}^{\Sigma}\) y ademas da condiciones para que \(M(P)\) sea \(\Sigma\)-p.r..

4.24. Sean \(n,m\geq0\). Sea \(P:D_{P}\subseteq\omega\times\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) un predicado \(\Sigma\)-p.r.. Entonces

adhocprefix(a)adhocsufix \(M(P)\) es \(\Sigma\)-recursiva.
adhocprefix(b)adhocsufix Si hay una funcion \(\Sigma\)-p.r. \(f:\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) tal que \[M(P)(\vec{x},\vec{\alpha})=\min\nolimits_{t}P(t,\vec{x},\vec{\alpha})\leq f(\vec{x},\vec{\alpha})\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M(P)}\text{,}\] entonces \(M(P)\) es \(\Sigma\)-p.r..

Proof. (a) Sea \(\bar{P}=P\cup C_{0}^{n+1,m}|_{(\omega^{n+1}\times\Sigma^{\ast m})-D_{P}}\). Note que \(\bar{P}\) es \(\Sigma\)-p.r. (por que?). Veremos a continuacion que \(M(P)=M(\bar{P})\). Notese que \[\{t\in\omega:P(t,\vec{x},\vec{\alpha})=1\}=\{t\in\omega:\bar{P}(t,\vec{x},\vec{\alpha})=1\}\] Esto claramente dice que \(D_{M(P)}=D_{M(\bar{P})}\) y que \(M(P)(\vec{x},\vec{\alpha})=M(\bar{P})(\vec{x},\vec{\alpha})\), para cada \((\vec{x},\vec{\alpha})\in D_{M(P)}\)., por lo cual \(M(P)=M(\bar{P})\).

Veremos entonces que \(M(\bar{P})\) es \(\Sigma\)-recursiva. Sea \(k\) tal que \(\bar{P}\in\mathrm{PR}_{k}^{\Sigma}\). Ya que \(\bar{P}\) es \(\Sigma\)-total y \(\bar{P}\in\mathrm{PR}_{k}^{\Sigma}\subseteq\mathrm{R}_{k}^{\Sigma}\), tenemos que \(M(\bar{P})\in\mathrm{R}_{k+1}^{\Sigma}\) y por lo tanto \(M(\bar{P})\in\mathrm{R}^{\Sigma}\).

(b) Ya que \(M(P)=M(\bar{P})\), basta con probar que \(M(\bar{P})\) es \(\Sigma\)-p.r. Primero veremos que \(D_{M(\bar{P})}\) es un conjunto \(\Sigma\)-p.r.. Notese que \[\chi_{D_{M(\bar{P})}}^{\omega^{n}\times\Sigma^{\ast m}}=\lambda\vec{x}\vec{\alpha}\left[(\exists t\in\omega)_{t\leq f(\vec{x},\vec{\alpha})}\;\bar{P}(t,\vec{x},\vec{\alpha})\right]\] lo cual nos dice que \[\chi_{D_{M(\bar{P})}}^{\omega^{n}\times\Sigma^{\ast m}}=\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\omega)_{t\leq x}\;\bar{P}(t,\vec{x},\vec{\alpha})\right]\circ\left[f,p_{1}^{n,m},...,p_{n+m}^{n,m}\right]\] Pero el Lema 4.21 nos dice que \(\lambda x\vec{x}\vec{\alpha}\left[(\exists t\in\omega)_{t\leq x}\;\bar{P}(t,\vec{x},\vec{\alpha})\right]\) es \(\Sigma\)-p.r. por lo cual tenemos que \(\chi_{D_{M(\bar{P})}}^{\omega^{n}\times\Sigma^{\ast m}}\) lo es.

Sea \[P_{1}=\lambda t\vec{x}\vec{\alpha}\left[\bar{P}(t,\vec{x},\vec{\alpha})\wedge(\forall j\in\omega)_{j\leq t}\;j=t\vee\lnot\bar{P}(j,\vec{x},\vec{\alpha})\right]\] Note que \(P_{1}\) es \(\Sigma\)-total. Dejamos al lector usando lemas anteriores probar que \(P_{1}\) es \(\Sigma\)-p.r. Ademas notese que para \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) se tiene que \[P_{1}(t,\vec{x},\vec{\alpha})=1\text{ si y solo si }(\vec{x},\vec{\alpha})\in D_{M(\bar{P})}\text{ y }t=M(\bar{P})(\vec{x},\vec{\alpha})\] Esto nos dice que \[M(\bar{P})=\left(\lambda\vec{x}\vec{\alpha}\left[\prod_{t=0}^{f(\vec{x},\vec{\alpha})}t^{P_{1}(t,\vec{x},\vec{\alpha})}\right]\right)|_{D_{M(\bar{P})}}\] por lo cual para probar que \(M(\bar{P})\) es \(\Sigma\)-p.r. solo nos resta probar que \[F=\lambda\vec{x}\vec{\alpha}\left[\prod_{t=0}^{f(\vec{x},\vec{\alpha})}t^{P_{1}(t,\vec{x},\vec{\alpha})}\right]\] lo es. Pero \[F=\lambda xy\vec{x}\vec{\alpha}\left[\prod_{t=x}^{y}t^{P_{1}(t,\vec{x},\vec{\alpha})}\right]\circ\left[C_{0}^{n,m},f,p_{1}^{n,m},...,p_{n+m}^{n,m}\right]\] y por lo tanto el Lema 4.20 nos dice que \(F\) es \(\Sigma\)-p.r..

OBSERVACION: No siempre que \(P\) sea \(\Sigma\)-p.r. tendremos que \(M(P)\) lo sera. Notese que si \(M(P)\) fuera \(\Sigma\)-p.r., cada ves que \(P\) lo sea, entonces tendriamos que \(\mathrm{PR}^{\Sigma}=\mathrm{R}^{\Sigma}\) (justifique) lo cual contradiria la Proposicion 4.6. Mas adelante (Corolario 4.5) veremos un ejemplo de un predicado \(P\) el cual es \(\Sigma\)-p.r. pero \(M(P)\) no es \(\Sigma\)-p.r.

El lema de minimizacion recien probado es muy util como veremos en los siguientes dos lemas.

4.25. Sea \(\Sigma\) un alfabeto finito. Las siguientes funciones son \(\Sigma\)-p.r.:

adhocprefix(a)adhocsufix \(\begin{array}[t]{rll} Q:\omega\times\mathbf{N} & \rightarrow & \omega\\ (x,y) & \rightarrow & \text{cociente de la division de }x\text{ por }y \end{array}\)
adhocprefix(b)adhocsufix \(\begin{array}[t]{rll} R:\omega\times\mathbf{N} & \rightarrow & \omega\\ (x,y) & \rightarrow & \text{resto de la division de }x\text{ por }y \end{array}\)
adhocprefix(c)adhocsufix \(\begin{array}[t]{rll} pr:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n\text{-esimo numero primo} \end{array}\)

Proof. (a) Ya vimos anteriormente que \(Q=M(P^{\prime})\), donde \(P^{\prime}=\lambda tx_{1}x_{2}\left[x_{1}\geq t.x_{2}\text{ y }x_{1}<(t+1).x_{2}\right]\). Ya que \(P^{\prime}\) es \(\Sigma\)-p.r. y \[Q(x_{1},x_{2})\leq p_{1}^{2,0}(x_{1},x_{2}),\text{ para cada }(x_{1},x_{2})\in\omega\times\mathbf{N}\] (b) del Lema 4.24 implica que \(Q\in\mathrm{PR}^{\Sigma}\).

(b) Notese que \[R=\lambda xy\left[x\dot{-}Q(x,y).y\right]\] y por lo tanto \(R\in\mathrm{PR}^{\Sigma}\).

(c) Para ver que \(pr\) es \(\Sigma\)-p.r., veremos que la extension \(h:\omega\rightarrow\omega\), dada por \(h(0)=0\) y \(h(n)=pr(n)\), \(n\geq1\), es \(\Sigma\)-p.r.. Luego \(pr=h|_{\mathbf{N}}\) resultara \(\Sigma\)-p.r. por ser la restriccion de una funcion \(\Sigma\)-p.r. a un conjunto \(\Sigma\)-p.r.. Primero note que \[\begin{aligned} h(0) & =0\\ h(t+1) & =\min\nolimits_{i}\left(i\text{ es primo}\wedge i>h(t)\right) \end{aligned}\] O sea que \(h=R\left(C_{0}^{0,0},g\right)\), donde \[\begin{array}[t]{rll} g:\omega\times\omega & \rightarrow & \omega\\ (A,t) & \rightarrow & \min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right) \end{array}\] Es decir que solo nos resta ver que \(g\) es \(\Sigma\)-p.r.. Pero notese que \(g=M(P)\), donde \(P=\lambda iAt\left[i\text{ es primo}\wedge i>A\right]\). Claramente \(P\) es \(\Sigma\)-p.r. por lo cual para poder aplicar (b) del lema anterior debemos encontrar una funcion \(f:\omega\times\omega\rightarrow\omega\) tal que \[M(P)(A,t)\leq f(A,t)\text{, para cada }(A,t)\in\omega^{2}\] Es decir \(f\) debera cumplir \[\min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right)\leq f(A,t)\text{, para cada }(A,t)\in\omega^{2}\] Definamos \(f=\lambda At[A!+1]\). Debemos probar entonces que \[\min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right)\leq A!+1\text{, para cada }A\in\omega\] Sea \(p\) un primo tal que \(p\) divide a \(A!+1\). Es facil ver que entonces \(p>A\) ya que de lo contrario \(p\) dividiria a \(A!\) lo cual nos diria que \(p\) divide a \(1=A!+1-A!\), lo cual es absurdo. Pero esto claramente nos dice que \[\min\nolimits_{i}\left(i\text{ es primo}\wedge i>A\right)\leq p\leq A!+1\] O sea que (b) del Lema 4.24 implica que \(g=M(P)\) es \(\Sigma\)-p.r.

4.26. Las funciones \(\lambda xi\left[(x)_{i}\right]\) y \(\lambda x\left[Lt(x)\right]\) son \(\Sigma\)-p.r.

Proof. Note que \(D_{\lambda xi\left[(x)_{i}\right]}=\mathbf{N}\times\mathbf{N}\). Sea \[P=\lambda txi\left[\lnot(pr(i)^{t+1}\ \text{divide }x)\right]\] Note que \(P\) es \(\Sigma\)-p.r. y que \(D_{P}=\omega\times\omega\times\mathbf{N}\). Dejamos al lector la prueba de que \(\lambda xi\left[(x)_{i}\right]=M(P)\). Ya que \((x)_{i}\leq x\), para todo \((x,i)\in\mathbf{N}\times\mathbf{N}\), (b) del Lema 4.24 implica que \(\lambda xi\left[(x)_{i}\right]\) es \(\Sigma\)-p.r..

Veamos que \(\lambda x\left[Lt(x)\right]\) es \(\Sigma\)-p.r.. Sea \[Q=\lambda tx\left[(\forall i\in\mathbf{N})_{i\leq x}\;(i\leq t\vee(x)_{i}=0)\right]\] Notese que \(D_{Q}=\omega\times\mathbf{N}\) y que ademas por el Lema 4.21 tenemos que \(Q\) es \(\Sigma\)-p.r. (dejamos al lector explicar como se aplica tal lema en este caso). Ademas notese que \(\lambda x\left[Lt(x)\right]=M(Q)\) y que \[Lt(x)\leq x,\text{para todo }x\in\mathbf{N}\] lo cual por (b) del Lema 4.24 nos dice que \(\lambda x\left[Lt(x)\right]\) es \(\Sigma\)-p.r..

Para \(x_{1},...,x_{n}\in\omega\), con \(n\geq1\), escribiremos \(\left\langle x_{1},...,x_{n}\right\rangle\) en lugar de \(\left\langle x_{1},...,x_{n},0,...\right\rangle\).

4.27. Sea \(n\geq1\). La funcion \(\lambda x_{1}...x_{n}\left[\left\langle x_{1},...,x_{n}\right\rangle \right]\) es \(\Sigma\)-p.r.

Proof. Sea \(f_{n}=\lambda x_{1}...x_{n}\left[\left\langle x_{1},...,x_{n}\right\rangle \right]\). Claramente \(f_{1}\) es \(\Sigma\)-p.r.. Ademas note que para cada \(n\geq1\), tenemos \[f_{n+1}=\lambda x_{1}...x_{n+1}\left[\left(f_{n}(x_{1},...,x_{n})pr(n+1)^{x_{n+1}}\right)\right]\text{.}\] O sea que podemos aplicar un argumento inductivo.

4.2.4.4 Minimizacion de variable alfabetica

Supongamos que \(\Sigma\neq\emptyset\). Sea \(\leq\) un orden total sobre \(\Sigma\). Recordemos que \(\leq\) puede ser naturalmente extendido a un orden total sobre \(\Sigma^{\ast}\). Sea \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\times\Sigma^{\ast}\rightarrow\omega\) un predicado. Cuando \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\) es tal que existe al menos un \(\alpha\in\Sigma^{\ast}\) tal que \(P(\vec{x},\vec{\alpha},\alpha)=1\), usaremos \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) para denotar al menor \(\alpha\in\Sigma^{\ast}\) tal que \(P(\vec{x},\vec{\alpha},\alpha)=1\). Notese que la expresion \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) esta definida solo para aquellas \((n+m)\)-uplas \((\vec{x},\vec{\alpha})\) para las cuales hay al menos un \(\alpha\) tal que se da \(P(\vec{x},\vec{\alpha},\alpha)=1\). Dicho de otra forma, \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) no estara definida cuando para cada \(\alpha\in\Sigma^{\ast}\) se de que \((\vec{x},\vec{\alpha},\alpha)\) no pertenece a \(D_{P}\) o \(P(\vec{x},\vec{\alpha},\alpha)=0\). Otro detalle importante a tener en cuenta es que la expresion \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) no depende de la variable \(\alpha\). Por ejemplo, las expresiones \(\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\) y \(\min_{\beta}^{\leq}P(\vec{x},\vec{\alpha},\beta)\) son equivalentes en el sentido que estan definidas en las mismas \((n+m)\)-uplas y cuando estan definidas asumen el mismo valor.

Definamos \[\begin{array}{c} M^{\leq}(P)=\lambda\vec{x}\vec{\alpha}\left[\min_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\right]\end{array}\] Notese que \[\begin{aligned} D_{M^{\leq}(P)} & =\left\{ (\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}:(\exists\alpha\in\Sigma^{\ast})\ P(\vec{x},\vec{\alpha},\alpha)\right\} \\ M^{\leq}(P)(\vec{x},\vec{\alpha}) & =\min\nolimits_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M^{\leq}(P)} \end{aligned}\] Diremos que \(M^{\leq}(P)\) es obtenida por minimizacion de variable alfabetica a partir de \(P\).

Vemos un ejemplo. Sea \(\Sigma=\{@,a,b,c,d,e\}\) y sea \(\leq\) un orden total sobre \(\Sigma\). Sea \(Dir=\{\alpha_{1}\in\Sigma^{\ast}:\left\vert \alpha_{1}\right\vert _{@}=1\}\) y definamos \(U:Dir\rightarrow\Sigma^{\ast}\) de la siguiente manera \[U(\alpha_{1})=\text{unico }\alpha\text{ tal que }\alpha@\text{ es tramo inicial de }\alpha_{1}\] Sea \[P=\lambda\alpha_{1}\alpha[\alpha_{1}\in Dir\text{ y }\alpha@\text{ es tramo inicial de }\alpha_{1}]\] Tenemos que \[\begin{aligned} D_{M^{\leq}(P)} & =\left\{ \alpha_{1}\in\Sigma^{\ast}:(\exists\alpha\in\Sigma^{\ast})\ P(\alpha_{1},\alpha)\right\} \\ & =\left\{ \alpha_{1}\in\Sigma^{\ast}:\alpha_{1}\in Dir\text{ y }(\exists\alpha\in\Sigma^{\ast})\ \alpha@\text{ es tramo inicial de }\alpha_{1}\right\} \\ & =Dir \end{aligned}\] y ademas es claro que \(M^{\leq}(P)(\alpha_{1})=U(\alpha_{1})\), para cada \(\alpha_{1}\in Dir\), por lo cual \(M^{\leq}(P)=U\). Intente explicar por que se utiizaron los nombres \(Dir\) y \(U\).

4.2.4.5 Lema de minimizacion acotada de variable alfabetica de predicados \(\Sigma\)-p.r.

4.28. Supongamos que \(\Sigma\neq\emptyset\). Sea \(\leq\) un orden total sobre \(\Sigma\), sean \(n,m\geq0\) y sea \(P:D_{P}\subseteq\omega^{n}\times\Sigma^{\ast m}\times\Sigma^{\ast}\rightarrow\omega\) un predicado \(\Sigma\)-p.r.. Entonces

adhocprefix(a)adhocsufix \(M^{\leq}(P)\) es \(\Sigma\)-recursiva.
adhocprefix(b)adhocsufix Si existe una funcion \(\Sigma\)-p.r. \(f:\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) tal que \[\left\vert M^{\leq}(P)(\vec{x},\vec{\alpha})\right\vert =\left\vert \min\nolimits_{\alpha}^{\leq}P(\vec{x},\vec{\alpha},\alpha)\right\vert \leq f(\vec{x},\vec{\alpha})\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M^{\leq}(P)}\text{,}\] entonces \(M^{\leq}(P)\) es \(\Sigma\)-p.r..

Proof. Sea \(Q=P\circ\left[p_{2}^{1+n,m},...,p_{1+n+m}^{1+n,m},\ast^{\leq}\circ p_{1}^{1+n,m}\right]\). Note que \[M^{\leq}(P)=\ast^{\leq}\circ M(Q)\] lo cual por (a) del Lema 4.24 implica que \(M^{\leq}(P)\) es \(\Sigma\)-recursiva.

Sea \(k\) el cardinal de \(\Sigma\). Ya que \[\left\vert \ast^{\leq}(M(Q)(\vec{x},\vec{\alpha}))\right\vert =\left\vert M^{\leq}(P)(\vec{x},\vec{\alpha})\right\vert \leq f(\vec{x},\vec{\alpha})\text{,}\] para todo \((\vec{x},\vec{\alpha})\in D_{M^{\leq}(P)}=D_{M(Q)}\), tenemos que \[M(Q)(\vec{x},\vec{\alpha})\leq\sum_{\iota=1}^{i=f(\vec{x},\vec{\alpha})}k^{i}\text{, para cada }(\vec{x},\vec{\alpha})\in D_{M(Q)}\text{.}\] O sea que por (b) del Lema 4.24, \(M(Q)\) es \(\Sigma\)-p.r. y por lo tanto \(M^{\leq}(P)\) lo es.

En el ejemplo de recien vimos que \(U=M(P)\), con \(P=\lambda\alpha_{1}\alpha[\alpha@\) es tramo inicial de \(\alpha_{1}]\) por lo cual, dado que \(P\) es \(\Sigma\)-p.r. y ademas \[\left\vert U(\alpha_{1})\right\vert \leq\left\vert \alpha_{1}\right\vert \text{, para cada }\alpha_{1}\in Dir\] el lema anterior nos dice que \(U\) es \(\Sigma\)-p.r.

4.2.5 Conjuntos \(\Sigma\)-recursivamente enumerables

Ya que la nocion de funcion \(\Sigma\)-recursiva es el modelo matematico Godeliano del concepto de funcion \(\Sigma\)-efectivamente computable, nos podriamos preguntar entonces cual es el modelo matematico Godeliano del concepto de conjunto \(\Sigma\)-efectivamente enumerable. Si prestamos atencion a la definicion de conjunto \(\Sigma\)-efectivamente enumerable, notaremos que depende de la existencia de ciertas funciones \(\Sigma\)-efectivamente computables por lo cual la siguiente definicion cae de maduro:

Diremos que un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) sera llamado \(\Sigma\)-recursivamente enumerable cuando sea vacio o haya una funcion \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que \(I_{F}=S\) y \(F_{(i)}\) sea \(\Sigma\)-recursiva, para cada \(i\in\{1,...,n+m\}\).

Deberia entonces quedar claro que si el concepto de funcion \(\Sigma\)-recursiva modeliza correctamente al concepto de funcion \(\Sigma\)-efectivamente computable, entonces el concepto de conjunto \(\Sigma\)-recursivamente enumerable recien definido modeliza correctamente al concepto de conjunto \(\Sigma\)-efectivamente enumerable.

4.2.6 Conjuntos \(\Sigma\)-recursivos

La version Godeliana del concepto de conjunto \(\Sigma\)-efectivamente computable es facil de dar: un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) sera llamado \(\Sigma\)-recursivo cuando la funcion \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) sea \(\Sigma\)-recursiva.

4.2.7 Algunos resultados basicos

Muchos resultados ya probados para el caso primitivo recursivo pueden ser probados usando basicamente las mismas pruebas e ideas para el caso recursivo. Por ejemplo las pruebas de los siguientes cuatro lemas son identicas a las del caso primitivo recursivo

4.29. Si \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) son predicados \(\Sigma\)-r., entonces \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) lo son tambien.

4.30. Si \(S_{1},S_{2}\subseteq\omega^{n}\times\Sigma^{\ast m}\) son \(\Sigma\)-r., entonces \(S_{1}\cup S_{2}\), \(S_{1}\cap S_{2}\) y \(S_{1}-S_{2}\) lo son.

4.31. Supongamos \(S_{1},...,S_{n}\subseteq\omega\), \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) son conjuntos no vacios. Entonces \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-r. sii \(S_{1},...,S_{n},L_{1},...,L_{m}\) son \(\Sigma\)-r.

4.32. Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) es \(\Sigma\)-r. y \(S\subseteq D_{f}\) es \(\Sigma\)-r., entonces \(f|_{S}\) es \(\Sigma\)-r

Tambien se puede probar una version del lema de division por casos para funciones \(\Sigma\)-recursivas con dominio \(\Sigma\)-recursivo, la cual generaliza el caso \(\Sigma\)-p.r.. La prueba es la misma que la del caso primitivo recursivo aunque al lema previo de existencia de extensiones lo probaremos en forma mas directa que para el caso primitivo recursivo. A saber:

4.33. Si \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) es \(\Sigma\)-r. y \(D_{f}\) es \(\Sigma\)-r., entonces existe una funcion \(\Sigma\)-r. \(\bar{f}:\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), tal que \(f=\bar{f}|_{D_{f}}\)

Proof. Si \(f=\emptyset\), es facil de probar y dejado al lector. Supongamos entonces \(f\) es no vacia. Sin perdida de generalidad podemos suponer que \((0,...,0,\varepsilon,...,\varepsilon)\in D_{f}\). Sea \[\begin{array}[t]{rll} F:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega^{n}\times\Sigma^{\ast m}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} (\vec{x},\vec{\alpha}) & & \text{si }(\vec{x},\vec{\alpha})\in D_{f}\\ (0,...,0,\varepsilon,...,\varepsilon) & & \text{caso contrario} \end{array}\right. \end{array}\] Ya que \[\begin{aligned} F_{(i)} & =\lambda\vec{x}\vec{\alpha}\left[x_{i}.\chi_{D_{f}}^{\omega^{n}\times\Sigma^{\ast m}}(\vec{x},\vec{\alpha})\right]\text{, para }i=1,...,n\\ F_{(i)} & =\lambda\vec{x}\vec{\alpha}\left[\alpha_{i}^{\chi_{D_{f}}^{\omega^{n}\times\Sigma^{\ast m}}(\vec{x},\vec{\alpha})}\right]\text{, para }i=n+1,...,n+m \end{aligned}\] tenemos que cada \(F_{(i)}\) es \(\Sigma\)-recursiva. Es claro que \(\bar{f}=f\circ F\) cumple que \(f=\bar{f}|_{D_{f}}\) por lo cual solo falta ver que \(\bar{f}\) es \(\Sigma\)-recursiva. Pero esto es obvio ya que \(F=\left[F_{(1)},...,F_{(n+m)}\right]\)

4.34. Supongamos \(f_{i}:D_{f_{i}}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), \(i=1,...,k\), son funciones \(\Sigma\)-recursivas tales que cada \(D_{f_{i}}\) es \(\Sigma\)-recursivo y \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\). Entonces la funcion \(f_{1}\cup...\cup f_{k}\) es \(\Sigma\)-recursiva.

4.35. Si \(S\) es \(\Sigma\)-recursivo, entonces \(S\) es \(\Sigma\)-r.e.

Proof. Supongamos \(\emptyset\neq S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Sea \((z_{1},...,z_{n},\gamma_{1},...,\gamma_{m})\in S\) fijo. Sea \(\leq\) un orden total sobre \(\Sigma\). Sea \(G:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) dada por \[G(x)=\left((x+1)_{1},...,(x+1)_{n},\ast^{\leq}((x+1)_{n+1}),...,\ast^{\leq}((x+1)_{n+m})\right)\] Es claro que cada \(G_{(i)}\) es \(\Sigma\)-recursiva y que \(\operatorname{Im}G=\omega^{n}\times\Sigma^{\ast m}\).

Para \(i=1,...,n\), definamos \(F_{i}:\omega\rightarrow\omega\) de la siguiente manera \[F_{i}(x)=\left\{ \begin{array}{ccl} G_{(i)}(x) & & \text{si }G(x)\in S\\ z_{i} & & \text{caso contrario} \end{array}\right.\] Para \(i=n+1,...,n+m\), definamos \(F_{i}:\omega\rightarrow\Sigma^{\ast}\) de la siguiente manera \[F_{i}(x)=\left\{ \begin{array}{ccl} G_{(i)}(x) & & \text{si }G(x)\in S\\ \gamma_{i} & & \text{caso contrario} \end{array}\right.\] Usando que \(S\) es \(\Sigma\)-recursivo podemos aplicar el lema anterior y ver que cada \(F_{i}\) es \(\Sigma\)-recursiva. Sea \(F=[F_{1},...,F_{n+m}]\). Notese que \(F_{(i)}=F_{i}\) para cada \(i=1,...,n+m\). Esto nos dice que \(S\) es \(\Sigma\)-r.e. ya que \(\operatorname{Im}F=S\).

Mas adelante (Lema 4.61) daremos un ejemplo natural de un conjunto que es \(\Sigma\)-r.e. pero el cual no es \(\Sigma\)-recursivo.

Deberia quedar claro que si el modelo de Godel es correcto, entonces todos los resultados probados dentro del paradigma filosofico de la computabilidad efectiva son ciertos una ves reenunciados de acuerdo al paradigma Godeliano. Tal como vimos arriba muchos de estos resultados se prueban en forma facil en su version recursiva. Sin envargo muchos otros requieren mas trabajo y es necesario utilizar algun paradigma mas constructivo (como el imperativo o el de Turing) para poder probarlos en su version recursiva. Por ejemplo consideremos el teorema siguiente dado en el contexto del paradigma filosofico:

4.1. Sea \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Son equivalentes

adhocprefix(a)adhocsufix \(S\) es \(\Sigma\)-efectivamente computable
adhocprefix(b)adhocsufix \(S\) y \((\omega^{n}\times\Sigma^{\ast m})-S\) son \(\Sigma\)-efectivamente enumerables

Se tiene que la version recursiva de (a)\(\Rightarrow\)(b) es probada sin problemas en el lema anterior pero para probar la version recursiva de (b)\(\Rightarrow\)(a), nos sera necesario utilizar el paradigma imperativo (Teorema 4.11). Lo mismo sucede con el lema de division por casos en su forma mas general (Lema 3.4) y con el teorema de caracterizacion de conjuntos \(\Sigma\)-efectivamente enumerables (Teorema 3.2), ambos cuando son enunciados en su version recursiva no son faciles de probar con las herramientas desarrolladas hasta ahora y nos sera necesario usar el paradigma imperativo para representar a los objetos recursivos involucrados. Estas pruebas estan en la Seccion [survey recursivo] donde se compilan todos los resultados basicos (expresados en paradigma recursivo) y se obtienen algunos resultados los cuales en esta instancia todavia no se pueden probar ya que para obtenerlos es necesario hacer uso de la formalizacion matematica de ambos paradigmas el funcional y el imperativo (por ejemplo la existencia de un conjunto que es \(\Sigma\)-r.e. pero el cual no es \(\Sigma\)-recursivo).

4.2.8 Recursion primitiva sobre valores anteriores

Dada una funcion \(h:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\), con \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\), no vacios, definamos \(h^{\downarrow}:\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\) de la siguiente manera \[\begin{aligned} h^{\downarrow}(x,\vec{x},\vec{\alpha}) & =\left\langle h(0,\vec{x},\vec{\alpha}),h(1,\vec{x},\vec{\alpha}),...,h(x,\vec{x},\vec{\alpha})\right\rangle \\ & =\Pi_{i=0}^{x}pr(i+1)^{h(i,\vec{x},\vec{\alpha})} \end{aligned}\]

4.36. Supongamos \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\\ g & :\omega\times\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega\\ h & :\omega\times S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\omega \end{aligned}\] son funciones tales que \[\begin{aligned} h(0,\vec{x},\vec{\alpha}) & =f(\vec{x},\vec{\alpha})\\ h(x+1,\vec{x},\vec{\alpha}) & =g(h^{\downarrow}(x,\vec{x},\vec{\alpha}),x,\vec{x},\vec{\alpha})\text{,} \end{aligned}\] para cada \(x\in\omega\) y \((\vec{x},\vec{\alpha})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\). Entonces \(h\) es \(\Sigma\)-r. (resp. \(\Sigma\)-p.r.) si \(f\) y \(g\) lo son.

Proof. Supongamos \(f,g\) son \(\Sigma\)-p.r.. Primero veremos que \(h^{\downarrow}\) es \(\Sigma\)-r. (resp. \(\Sigma\)-p.r.). Notese que para cada \((\vec{x},\vec{\alpha})\in S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) tenemos que \[\begin{aligned} h^{\downarrow}(0,\vec{x},\vec{\alpha}) & =\left\langle h(0,\vec{x},\vec{\alpha})\right\rangle \\ & =\left\langle f(\vec{x},\vec{\alpha})\right\rangle \\ & =2^{f(\vec{x},\vec{\alpha})}\\ h^{\downarrow}(x+1,\vec{x},\vec{\alpha}) & =h^{\downarrow}(x,\vec{x},\vec{\alpha})pr(x+2)^{h(x+1,\vec{x},\vec{\alpha})}\\ & =h^{\downarrow}(x,\vec{x},\vec{\alpha})pr(x+2)^{g(h^{\downarrow}(x,\vec{x},\vec{\alpha}),x,\vec{x},\vec{\alpha})} \end{aligned}\] lo cual nos dice que \(h^{\downarrow}=R(f_{1},g_{1})\) donde \[\begin{aligned} f_{1} & =\lambda\vec{x}\vec{\alpha}\left[2^{f(\vec{x},\vec{\alpha})}\right]\\ g_{1} & =\lambda Ax\vec{x}\vec{\alpha}\left[Apr(x+2)^{g(A,x,\vec{x},\vec{\alpha})}\right] \end{aligned}\] O sea que \(h^{\downarrow}\) es \(\Sigma\)-r. (resp. \(\Sigma\)-p.r.) ya que \(f_{1}\) y \(g_{1}\) lo son. Finalmente notese que \[h=\lambda ix[(x)_{i}]\circ\left[Suc\circ p_{1}^{1+n,m},h^{\downarrow}\right]\] lo cual nos dice que \(h\) es \(\Sigma\)-r. (resp. \(\Sigma\)-p.r.).

4.2.9 Independencia del alfabeto

Probaremos que los conceptos de \(\Sigma\)-recursividad y \(\Sigma\)-recursividad primitiva son en realidad independientes del alfabeto \(\Sigma\), es decir que si \(f\) es una funcion la cual es \(\Sigma\)-mixta y \(\Gamma\)-mixta, entonces \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.) sii \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.).

Ya definimos para el caso de un alfabeto \(\Sigma\neq\emptyset\) y \(\leq\) un orden total sobre \(\Sigma\), las funciones \(\#^{\leq}\) y \(\ast^{\leq}\). Sea \(\Sigma=\emptyset\). Notese que el conjunto \(\emptyset\) es un orden total sobre \(\Sigma\) (de hecho es el unico orden total sobre \(\Sigma\)). Definamos \[\begin{array}{rll} \#^{\emptyset}:\{0\} & \rightarrow & \{\varepsilon\}\\ 0 & \rightarrow & \varepsilon \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} \ast^{\emptyset}:\{\varepsilon\} & \rightarrow & \{0\}\\ \varepsilon & \rightarrow & 0 \end{array}\] Ya que \(\Sigma^{\ast}=\{\varepsilon\}\), las funciones \(\#^{\emptyset}\) y \(\ast^{\emptyset}\) son biyecciones mutuamente inversas entre \(\{0\}\) y \(\Sigma^{\ast}\). Ademas notese que estas funciones son \(\Sigma\)-p.r..

4.37. Supongamos \(\Sigma\subseteq\Gamma\).

adhocprefix(a)adhocsufix Si \(\leq\) es un orden total sobre \(\Sigma\), entonces las funciones \(\Sigma\)-mixtas \(\ast^{\leq}\) y \(\#^{\leq}\) son \(\Gamma\)-p.r..
adhocprefix(b)adhocsufix Si \(\leq^{\prime}\) es un orden total sobre \(\Gamma\), entonces las funciones \(\Sigma\)-mixtas \(\#^{\leq^{\prime}}|_{\Sigma^{\ast}}\) y \(\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\) son \(\Sigma\)-p.r..

Proof. (a) Si \(\Sigma=\emptyset\), entonces es facil ver que \(\ast^{\leq}\) y \(\#^{\leq}\) son \(\Gamma\)-p.r., y es dejado como ejercicio. Supongamos \(\Sigma=\{a_{1},...,a_{k}\}\) con \(k\geq1\) y \(\leq\) es dado por \(a_{1}<...<a_{k}\). Sea \(s_{e}^{\leq}:\Gamma^{\ast}\rightarrow\Gamma^{\ast}\) dada por \[\begin{aligned} s_{e}^{\leq}(\varepsilon) & =a_{1}\\ s_{e}^{\leq}(\alpha a_{i}) & =\alpha a_{i+1}\text{, si }i<k\\ s_{e}^{\leq}(\alpha a_{k}) & =s_{e}^{\leq}(\alpha)a_{1}\\ s_{e}^{\leq}(\alpha a) & =\varepsilon\text{, si }a\in\Gamma-\Sigma. \end{aligned}\] Note que \(s_{e}^{\leq}\) es \(\Gamma\)-p.r. y que \(s_{e}^{\leq}|_{\Sigma^{\ast}}=s^{\leq}\). Ya que \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(x+1) & =s^{\leq}(\ast^{\leq}(x)) \end{aligned}\] para cada \(x\in\omega\), tenemos que \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(x+1) & =s_{e}^{\leq}(\ast^{\leq}(x)) \end{aligned}\] Pero esto nos dice que \(\ast^{\leq}=R(C_{\varepsilon}^{0,0},g)\) donde \[\begin{array}{lll} g:\omega\times\Gamma^{\ast} & \rightarrow & \Gamma^{\ast}\\ \;\;\;\;\;(x,\alpha) & \rightarrow & s_{e}^{\leq}(\alpha) \end{array}\] Pero es claro que \(g\) es \(\Gamma\)-p.r. por lo cual \(\ast^{\leq}\) es \(\Gamma\)-p.r..

Para ver que \(\#^{\leq}:\Sigma^{\ast}\rightarrow\omega\) es \(\Gamma\)-p.r., sea \(\#_{e}^{\leq}:\Gamma^{\ast}\rightarrow\omega\) dada por \[\begin{aligned} \#_{e}^{\leq}(\varepsilon) & =0\\ \#_{e}^{\leq}(\alpha a_{i}) & =\#_{e}^{\leq}(\alpha).k+i\\ \#_{e}^{\leq}(\alpha a) & =0\text{, si }a\in\Gamma-\Sigma. \end{aligned}\] Ya que \(\#_{e}^{\leq}\) es \(\Gamma\)-p.r., eso es \(\#^{\leq}=\#_{e}^{\leq}|_{\Sigma^{\ast}}\).

(b) El caso \(\Sigma=\emptyset\) es facil y queda como ejercicio. Supongamos entonces \(\Sigma\) es no vacio. Sea \(n\) el cardinal de \(\Gamma.\) Ya que \[\begin{aligned} \#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\varepsilon) & =0\\ \#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\alpha a) & =\#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\alpha).n+\#^{\leq^{\prime}}(a)\text{, para cada }a\in\Sigma \end{aligned}\] la funcion \(\#^{\leq^{\prime}}|_{\Sigma^{\ast}}\) es \(\Sigma\)-p.r.. O sea que el predicado \(P=\lambda x\alpha\left[\#^{\leq^{\prime}}|_{\Sigma^{\ast}}(\alpha)=x\right]\) es \(\Sigma\)-p.r.. Sea \(\leq\) un orden total sobre \(\Sigma\). Note que \(\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}=M^{\leq}(P)\), lo cual ya que \[\left\vert \ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}(x)\right\vert \leq x\] nos dice que \(\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\) es \(\Sigma\)-p.r. (Lema 4.28).

4.38. \(\mathrm{PR}^{\emptyset}\subseteq\mathrm{PR}^{\Sigma}\) y \(\mathrm{R}^{\emptyset}\subseteq\mathrm{R}^{\Sigma}\)

Proof. Veamos que \(\mathrm{R}^{\emptyset}\subseteq\mathrm{R}^{\Sigma}\). Probaremos por induccion en \(k\) que \(\mathrm{R}_{k}^{\emptyset}\subseteq\mathrm{R}^{\Sigma}\). El caso \(k=0\) es trivial. Supongamos entonces que vale la hipotesis inductiva \(\mathrm{R}_{k}^{\emptyset}\subseteq\mathrm{R}^{\Sigma}\) y veamos que \(\mathrm{R}_{k+1}^{\emptyset}\subseteq\mathrm{R}^{\Sigma}\). Sea \(F\in\mathrm{R}_{k+1}^{\emptyset}-\mathrm{R}_{k}^{\emptyset}\) veremos que \(F\in\mathrm{R}^{\Sigma}\). Hay varios casos:

Caso \(F=R(f,\mathcal{G})\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\emptyset^{\ast}\\ \mathcal{G}_{a} & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast}\times\emptyset^{\ast}\rightarrow\emptyset^{\ast}\text{, para cada }a\in\emptyset \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacio. Por hipotesis inductiva tenemos que \(f\in\mathrm{R}^{\Sigma}\). Notese que \(\mathcal{G}=\emptyset\), lo cual nos dice que por definicion \[\begin{array}{rll} R(f,\mathcal{G}):S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast} & \rightarrow & \emptyset^{\ast}\\ (\vec{x},\varepsilon,...,\varepsilon,\varepsilon) & \rightarrow & f(\vec{x},\varepsilon,...,\varepsilon) \end{array}\] Es claro que \(\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}\) es un conjunto \(\Sigma\)-p.r. por lo cual las funciones \(p_{i}^{n,m+1}|_{\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}}\) son \(\Sigma\)-p.r. (aqui las \(p_{i}^{n,m+1}\) son respecto de \(\Sigma\)). Ya que \[R(f,\mathcal{G})=f\circ\left[p_{1}^{n,m+1}|_{\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}},...,p_{n+m}^{n,m+1}|_{\omega^{n}\times\Sigma^{\ast m}\times\emptyset^{\ast}}\right]\] tenemos que \(F\) es \(\Sigma\)-recursiva

Caso \(F=R(f,g)\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\rightarrow\emptyset^{\ast}\\ g & :\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\emptyset^{\ast}\rightarrow\emptyset^{\ast} \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\emptyset}\) y cada \(S_{i}\) no vacio. Por hipotesis inductiva tenemos que \(f,g\in\mathrm{R}^{\Sigma}\). Notese que respecto de \(\Sigma\), la funcion \(R(f,g)\) no esta definida ya que por la forma de \(f\), el dominio de \(g\) deberia ser \(\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\Sigma^{\ast}\). Sea \[\tilde{g}=g\circ\left[p_{1}^{1+n,m+1},...,p_{1+n+m}^{1+n,m+1},C_{\varepsilon}^{1+n,m+1}\right]\] (aqui las \(p_{i}^{1+n,m+1}\) y \(C_{\varepsilon}^{1+n,m+1}\) son respecto de \(\Sigma\)). Notese que \(D_{\tilde{g}}=\omega\times S_{1}\times...\times S_{n}\times\emptyset^{\ast m}\times\Sigma^{\ast}\) y \(\tilde{g}\) es \(\Sigma\)-recursiva. Ademas es facil ver que \(F=Rf,\tilde{g})\) (respecto del alfabeto \(\Sigma\)) por lo cual \(F\) es \(\Sigma\)-recursiva

Caso \(F=M(P)\), con \(P:\omega\times\omega^{n}\times\emptyset^{\ast m}\rightarrow\omega\), un predicado en \(\mathrm{R}_{k}^{\emptyset}\). Por hipotesis inductiva tenemos que \(P\in\mathrm{R}^{\Sigma}\). Sea \[\bar{P}=P\circ\left[p_{1}^{1+n,m},...,p_{1+n}^{1+n,m},C_{\varepsilon}^{1+n,m},...,C_{\varepsilon}^{1+n,m}\right]\] Notese que \(\bar{P}\) es \(\Sigma\)-total y \(\Sigma\)-recursivo y ademas extiende a \(P\). Sea \[\tilde{P}=\lambda xy[x.y]\circ\left[\bar{P},\chi_{\omega\times\omega^{n}\times\emptyset^{\ast m}}^{\omega\times\omega^{n}\times\Sigma^{\ast m}}\right]\] Tambien \(\tilde{P}\) es \(\Sigma\)-total y \(\Sigma\)-recursivo y extiende a \(P\) pero ademas fuera del dominio de \(P\) vale \(0\). Esto nos dice que \(M(\tilde{P})=M(P)\) por lo cual \(F\) es \(\Sigma\)-recursiva ya que \(M(\tilde{P})\) lo es

Los otros casos de recursion primitiva son parecidos a los hechos y el caso de la composicion es trivial.

La prueba de que \(\mathrm{PR}^{\emptyset}\subseteq\mathrm{PR}^{\Sigma}\) es muy similar. Se dejan los detalles como ejercicio para el lector

Sea \(\Sigma\) un alfabeto finito (puede ser vacio) y sea \(\leq\) un orden total sobre \(\Sigma\). Para \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\), definamos \[f^{\#^{\leq}}=f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq}\circ p_{n+1}^{n+m,0},...,\ast^{\leq}\circ p_{n+m}^{n+m,0}\right]\] Similarmente, para \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\), definamos \[f^{\#^{\leq}}=\#^{\leq}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq}\circ p_{n+1}^{n+m,0},...,\ast^{\leq}\circ p_{n+m}^{n+m,0}\right]\]

4.39. Sea \(\Gamma\) un alfabeto finito y sea \(\leq\) un orden total sobre \(\Gamma\). Dada \(h\) una funcion \(\Gamma\)-mixta, son equivalentes

adhocprefix(1)adhocsufix \(h\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.)
adhocprefix(2)adhocsufix \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.)

Proof. (2)\(\Rightarrow\)(1). Supongamos \(h:D_{h}\subseteq\omega^{n}\times\Gamma^{\ast m}\rightarrow\Gamma^{\ast}\) es tal que \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Dejamos al lector chequear que \[h=\ast^{\leq}\circ h^{\#^{\leq}}\circ\left[p_{1}^{n,m},...,p_{n}^{n,m},\#^{\leq}\circ p_{n+1}^{n,m},...,\#^{\leq}\circ p_{n+m}^{n,m}\right]\] (aqui las \(p_{i}^{n,m}\) son respecto de \(\Gamma\)). Por el lema anterior tenemos que \(h^{\#^{\leq}}\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Ya que (aun cuando \(\Gamma=\emptyset\)) tenemos que las funciones \(\ast^{\leq}\) y \(\#^{\leq}\) son \(\Gamma\)-p.r., tenemos que \(h\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.) ya que es composicion de funciones \(\Gamma\)-recursivas (resp. \(\Gamma\)-p.r.).

(1)\(\Rightarrow\)(2). El caso \(\Gamma=\emptyset\) es trivial ya que \(h^{\#^{\leq}}\) se define como composicion de funciones \(\emptyset\)-recursivas (resp. \(\emptyset\)-p.r.). Supongamos entonces que \(\Gamma=\{a_{1},...,a_{r}\}\), con \(a_{1}<a_{2}<...<a_{r}\) y \(r>0\). Probaremos por induccion en \(k\) que

Si \(h\in\mathrm{R}_{k}^{\Gamma}\) (resp. \(h\in\mathrm{PR}_{k}^{\Gamma}\)), entonces \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.).

El caso \(k=0\) es facil y dejado al lector. Supongamos (*) vale para un \(k\) fijo. Veremos que vale para \(k+1\). Sea \(h\in\mathrm{R}_{k+1}^{\Gamma}\) (resp. \(h\in\mathrm{PR}_{k+1}^{\Gamma}\)). Hay varios casos

Caso 1. Supongamos \(h=f\circ[f_{1},...,f_{n}]\), con \(f,f_{1},...,f_{n}\in\mathrm{R}_{k}^{\Gamma}\) (resp. \(f,f_{1},...,f_{n}\in\mathrm{PR}_{k}^{\Gamma}\)). Por hipotesis inductiva tenemos que \(f^{\#^{\leq}},f_{1}^{\#^{\leq}},...,f_{n}^{\#^{\leq}}\) son \(\emptyset\)-recursivas (resp. \(\emptyset\)-p.r.). Ya que \(h^{\#^{\leq}}=f^{\#^{\leq}}\circ\left[f_{1}^{\#^{\leq}},...,f_{n}^{\#^{\leq}}\right]\), tenemos que \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.).

Caso 2. Supongamos \(h=M(P)\), con \(P:\omega\times\omega^{n}\times\Gamma^{\ast m}\rightarrow\omega\), un predicado en \(\mathrm{R}_{k}^{\Gamma}\). Ya que \(h^{\#^{\leq}}=M(P^{\#^{\leq}})\), tenemos que \(h^{\#^{\leq}}\) es \(\emptyset\)-recursiva.

Caso 3. Supongamos \(h=R(f,\mathcal{G})\), con \[\begin{aligned} f & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\rightarrow\Gamma^{\ast}\\ \mathcal{G}_{a} & :S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\times\Gamma^{\ast}\times\Gamma^{\ast}\rightarrow\Gamma^{\ast}\text{, }a\in\Gamma \end{aligned}\] funciones en \(\mathrm{R}_{k}^{\Gamma}\) (resp. \(\mathrm{PR}_{k}^{\Gamma}\)) y \(S_{1},...,S_{n}\subseteq\omega\) y \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\), no vacios. Notese que \[\begin{aligned} f^{\#^{\leq}} & :S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\rightarrow\omega\\ \mathcal{G}_{a}^{\#^{\leq}} & :S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\times\omega\rightarrow\omega\text{, }a\in\Gamma\\ h^{\#^{\leq}} & :S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\rightarrow\omega \end{aligned}\] Por hipotesis inductiva tenemos que \(f^{\#^{\leq}}\) y cada \(\mathcal{G}_{a}^{\#^{\leq}}\) son \(\emptyset\)-recursivas (resp. \(\emptyset\)-p.r.). Sea \[\begin{array}{rll} i_{0}:\omega & \rightarrow & \omega\\ x & \rightarrow & \left\{ \begin{array}{lll} r & & \text{si }r\text{ divide }x\\ R(x,r) & & \text{caso contrario} \end{array}\right. \end{array}\] y sea \[B=\lambda x\left[Q(x\dot{-}i_{0}(x),r)\right]\] (\(R\) y \(Q\) son definidas en el Lema 4.25). Note que \(i_{0}\) y \(B\) son \(\emptyset\)-p.r. y que \[\ast^{\leq}(x)=\ast^{\leq}(B(x))a_{i_{0}(x)}\text{, para }x\geq1\] (ejercicio). Tambien tenemos para cada \((\vec{x},\vec{y},t)\in S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\) se da \[\begin{aligned} h^{\#^{\leq}}(\vec{x},\vec{y},t+1) & =\#^{\leq}(h(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(t+1)))\\ & =\#^{\leq}(h(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1))a_{i_{0}(t+1)}))\\ & =\#^{\leq}\left(\mathcal{G}_{a_{i_{0}(t+1)}}(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1)),h(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1)))\right)\\ & =\#^{\leq}\left(\mathcal{G}_{a_{i_{0}(t+1)}}(\vec{x},\ast^{\leq}(\vec{y}),\ast^{\leq}(B(t+1)),\ast^{\leq}(h^{\#^{\leq}}(\vec{x},\vec{y},B(t+1))))\right)\\ & =\mathcal{G}_{a_{i_{0}(t+1)}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),h^{\#^{\leq}}(\vec{x},\vec{y},B(t+1))) \end{aligned}\] y ya que \(B(t+1)<t+1\), tenemos que

\(h^{\#^{\leq}}(\vec{x},\vec{y},t+1)=\mathcal{G}_{a_{i_{0}(t+1)}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),\left(\left\langle h^{\#^{\leq}}(\vec{x},\vec{y},0),...,h^{\#^{\leq}}(\vec{x},\vec{y},t)\right\rangle \right)_{B(t+1)+1})\), para cada \((\vec{x},\vec{y},t)\in S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\times\omega\)

A continuacion aplicaremos la idea del Lema 4.36. Sera mas claro asi ya que para aplicarlo directamente deberiamos cambiar el orden de los parametros de las funciones \(h^{\#^{\leq}}\), \(\mathcal{G}_{a_{i}}^{\#^{\leq}}\) componiendolas adecuadamente y seria muy engorroso notacionalmente.

Definamos \[H=\lambda t\vec{x}\vec{y}\left[\left\langle h^{\#^{\leq}}(\vec{x},\vec{y},0),...,h^{\#^{\leq}}(\vec{x},\vec{y},t)\right\rangle \right]\] Notar que \[D_{H}=\omega\times S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\] Tenemos que \[\begin{aligned} H(0,\vec{x},\vec{y}) & =\left\langle h^{\#^{\leq}}(\vec{x},\vec{y},0)\right\rangle =\left\langle f^{\#^{\leq}}(\vec{x},\vec{y})\right\rangle =2^{f^{\#^{\leq}}(\vec{x},\vec{y})}\\ H(t+1,\vec{x},\vec{y}) & =\left(H(t,\vec{x},\vec{y}).pr(t+2)^{h^{\#^{\leq}}(\vec{x},\vec{y},t+1)}\right)\\ & =\left(H(t,\vec{x},\vec{y}).pr(t+2)^{\mathcal{G}_{a_{i_{0}(t+1)}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(H(t,\vec{x},\vec{y}))_{B(t+1)+1})}\right)\text{ (por (**))} \end{aligned}\] para cada \((t,\vec{x},\vec{y})\in\omega\times S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\). O sea que si definimos \[g:\omega\times\omega\times S_{1}\times...\times S_{n}\times\#^{\leq}(L_{1})\times...\times\#^{\leq}(L_{m})\rightarrow\omega\] por \[g(A,t,\vec{x},\vec{y})=\left\{ \begin{array}{clc} \left(A.pr(t+2)^{\mathcal{G}_{a_{1}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(A)_{B(t+1)+1})}\right) & \text{si} & i_{0}(t+1)=1\\ \vdots & & \vdots\\ \left(A.pr(t+2)^{\mathcal{G}_{a_{r}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(A)_{B(t+1)+1})}\right) & \text{si} & i_{0}(t+1)=r \end{array}\right.\] tenemos que \(H=R(\lambda x\left[2^{x}\right]\circ f^{\#^{\leq}},g)\). Note que \(g\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.), ya que \[g=\lambda At\vec{x}\vec{y}\left[f_{1}(A,t,\vec{x},\vec{y})P_{1}(A,t,\vec{x},\vec{y})+...+f_{r}(A,t,\vec{x},\vec{y})P_{r}(A,t,\vec{x},\vec{y})\right]\text{,}\] con \[\begin{aligned} f_{i} & =\lambda At\vec{x}\vec{y}\left[\left(A.pr(t+2)^{\mathcal{G}_{a_{i}}^{\#^{\leq}}(\vec{x},\vec{y},B(t+1),(A)_{B(t+1)})}\right)\right]\\ P_{i} & =\lambda At\vec{x}\vec{y}\left[i_{0}(t+1)=i\right] \end{aligned}\] O sea que \(H\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.) y por lo tanto lo es \[h^{\#^{\leq}}=\lambda\vec{x}\vec{y}t\left[(H(t,\vec{x},\vec{y}))_{t+1}\right]\] Los otros casos en los cuales \(h\) es obtenida por recursion primitiva son similares.

4.2. Sean \(\Sigma\) y \(\Gamma\) alfabetos cualesquiera.

adhocprefix(a)adhocsufix Supongamos una funcion \(f\) es \(\Sigma\)-mixta y \(\Gamma\)-mixta, entonces \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.) sii \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.).
adhocprefix(b)adhocsufix Supongamos un conjunto \(S\) es \(\Sigma\)-mixto y \(\Gamma\)-mixto, entonces \(S\) es \(\Sigma\)-recursivo (resp. \(\Sigma\)-r.e., \(\Sigma\)-p.r.) sii \(S\) es \(\Gamma\)-recursivo (resp. \(\Gamma\)-r.e., \(\Gamma\)-p.r.).

Proof. (a) Ya que \(f\) es \((\Sigma\cap\Gamma)\)-mixta, podemos suponer sin perdida de generalidad que \(\Sigma\subseteq\Gamma\) (por que?). Sea \(\leq\) un orden total sobre \(\Sigma\) y sea \(\leq^{\prime}\) un orden total sobre \(\Gamma\). Primero supongamos que \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.). Probaremos que \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Ya que \(f\) es \(\Sigma\) mixta, tenemos que \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), con \(O\in\{\omega,\Sigma^{\ast}\}\). Haremos el caso \(O=\Sigma^{\ast}\). Ya que las funciones \(\#^{\leq^{\prime}}|_{\Sigma^{\ast}}\) y \(\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\) son \(\Sigma\)-p.r. (Lema 4.37) y ademas \[\begin{aligned} f^{\#^{\leq^{\prime}}} & =\#^{\leq^{\prime}}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq^{\prime}}\circ p_{n+1}^{n+m,0},...,\ast^{\leq^{\prime}}\circ p_{n+m}^{n+m,0}\right]\\ & =\#^{\leq^{\prime}}|_{\Sigma^{\ast}}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\circ p_{n+1}^{n+m,0},...,\ast^{\leq^{\prime}}|_{\#^{\leq^{\prime}}(\Sigma^{\ast})}\circ p_{n+m}^{n+m,0}\right] \end{aligned}\] (justifique) tenemos que \(f^{\#^{\leq^{\prime}}}\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.). Por el lema anterior tenemos que \(\left(f^{\#^{\leq^{\prime}}}\right)^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.), pero notese que \(\left(f^{\#^{\leq^{\prime}}}\right)^{\#^{\leq}}=f^{\#^{\leq^{\prime}}}\) ya que \(f^{\#^{\leq^{\prime}}}\) es de tipo \((n+m,0,\#)\), por lo cual tenemos que \(f^{\#^{\leq^{\prime}}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Pero esto por el lema anterior nos dice que \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.).

Supongamos ahora que \(f\) es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Probaremos que \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.). Ya que \(\#^{\leq}\) y \(\ast^{\leq}\) son \(\Gamma\)-p.r. (Lema 4.37), la funcion \[f^{\#^{\leq}}=\#^{\leq}\circ f\circ\left[p_{1}^{n+m,0},...,p_{n}^{n+m,0},\ast^{\leq}\circ p_{n+1}^{n+m,0},...,\ast^{\leq}\circ p_{n+m}^{n+m,0}\right]\] es \(\Gamma\)-recursiva (resp. \(\Gamma\)-p.r.). Por el lema anterior \(\left(f^{\#^{\leq}}\right)^{\#^{\leq^{\prime}}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Pero notese que \(\left(f^{\#^{\leq}}\right)^{\#^{\leq^{\prime}}}=f^{\#^{\leq}}\) ya que \(f^{\#^{\leq}}\) es de tipo \((n+m,0,\#)\), por lo cual \(f^{\#^{\leq}}\) es \(\emptyset\)-recursiva (resp. \(\emptyset\)-p.r.). Esto por el lema anterior nos dice que \(f\) es \(\Sigma\)-recursiva (resp. \(\Sigma\)-p.r.).

(b) Supongamos \(S\) es \(\Sigma\)-mixto y \(\Gamma\)-mixto. Ya que \(S\) es \((\Sigma\cap\Gamma)\)-mixto, podemos suponer sin perdida de generalidad que \(\Sigma\subseteq\Gamma\). Que \[S\text{ es }\Sigma\text{-r.e. sii }S\text{ es }\Gamma\text{-r.e.}\] sigue directo de (a). Supongamos ahora que \(S\) es \(\Sigma\)-recursivo. Veremos que \(S\) es \(\Gamma\)-recursivo. Supongamos \(S\) es de tipo \((n,m)\) es decir \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Por definicion tenemos que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-recursiva. Pero \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es tambien \(\Gamma\)-mixta, por lo cual (a) nos dice que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Gamma\)-recursiva. Ademas es claro que el conjunto \((\omega^{n}\times\Gamma^{\ast m})-(\omega^{n}\times\Sigma^{\ast m})\) es \(\Gamma\)-recursivo. Ya que \[\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}=\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\cup C_{0}^{n,m}|_{(\omega^{n}\times\Gamma^{\ast m})-(\omega^{n}\times\Sigma^{\ast m})}\] los Lemas 4.32 y 4.34 nos dicen que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}\) es \(\Gamma\)-recursiva (aqui \(C_{0}^{n,m}\) es respecto del alfabeto \(\Gamma\)).

Supongamos ahora que \(S\) es \(\Gamma\)-recursivo. Veremos que \(S\) es \(\Sigma\)-recursivo. Por definicion tenemos que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}\) es \(\Gamma\)-recursiva. Ya que \(\omega^{n}\times\Sigma^{\ast m}\) es \(\Gamma\)-recursivo, tenemos que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}|_{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Gamma\)-recursiva. Por (a) tenemos que \(\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}|_{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-recursiva. Pero \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}=\chi_{S}^{\omega^{n}\times\Gamma^{\ast m}}|_{\omega^{n}\times\Sigma^{\ast m}}\) por lo cual \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) es \(\Sigma\)-recursiva, obteniendo que \(S\) es \(\Sigma\)-recursivo.

4.2 El paradigma de Godel: Funciones \(\Sigma\)-recursivas