Sea \(\Sigma\) un alfabeto finito. Dados \(n,m\in\omega\), usaremos \(\omega^{n}\times\Sigma^{\ast m}\) para abreviar la expresion \[\overset{n\text{ veces}}{\overbrace{\omega\times...\times\omega}}\times\overset{m\text{ veces}}{\overbrace{\Sigma^{\ast}\times...\times\Sigma^{\ast}}}\] Por ejemplo, \(\omega^{3}\times\Sigma^{\ast4}\) sera una forma abreviada de escribir \(\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\). Debe quedar claro que estamos haciendo cierto abuso notacional ya que en principio si no hacemos esta convencion notacional, \(\omega^{3}\times\Sigma^{\ast4}\) denota un conjunto de pares y \(\omega\times\omega\times\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast}\) es un conjunto de \(7\)-uplas.
Notese que cuando \(n=m=0\), tenemos que \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\{\Diamond\}\) y si \(m=0\), entonces \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\omega^{n}\).
Con esta convencion notacional, un elemento generico de \(\omega^{n}\times\Sigma^{\ast m}\) es una \((n+m)\)-upla de la forma \((x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})\). Para abreviar, escribiremos \((\vec{x},\vec{\alpha})\) en lugar de \((x_{1},...,x_{n},\alpha_{1},...,\alpha_{m})\).
Sea \(\Sigma\) un alfabeto finito. Dada una funcion \(f\), diremos que \(f\) es \(\Sigma\)-mixta si cumple las siguientes propiedades
adhocprefix(M1)adhocsufix Existen \(n,m\geq0\), tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\)
adhocprefix(M2)adhocsufix Ya sea \(I_{f}\subseteq\omega\) o \(I_{f}\subseteq\Sigma^{\ast}\)
Algunos ejemplos:
adhocprefixE\(_{1}\)adhocsufix Sea \(\Sigma=\{\square,\%,\blacktriangle\}\). La funcion \[\begin{array}{rll} f:\omega\times\{\square,\%,\blacktriangle\}^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}\] es \(\Sigma\)-mixta ya que se cumple (M1) con \(n=m=1\) y (M2). Notese que \(f\) no es \(\{\square,\%\}\)-mixta ya que no cumple (M1) respecto del alfabeto \(\{\square,\%\}\). Sin envargo note que \(f\) es \(\{\square,\%,\blacktriangle,@\}\)-mixta
adhocprefixE\(_{2}\)adhocsufix La funcion \[\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+y \end{array}\] es \(\Sigma\)-mixta cualesquiera sea el alfabeto \(\Sigma\)
adhocprefixE\(_{3}\)adhocsufix Sea \(\Sigma=\{\square,@\}\). La funcion \[\begin{array}{rll} \{\square\square\square,@@\} & \rightarrow & \omega\\ \alpha & \rightarrow & \left\vert \alpha\right\vert \end{array}\]
es \(\Sigma\)-mixta ya que se cumple (M1) (con \(n=0\) y \(m=1\)) y (M2)
adhocprefixE\(_{4}\)adhocsufix Supongamos \(\Sigma=\emptyset\). Tenemos entonces que \(\Sigma^{\ast}=\{\varepsilon\}\). Por ejemplo \[\begin{array}{rll} D & \rightarrow & \omega\\ (x,\varepsilon,\varepsilon,\varepsilon) & \rightarrow & x^{2} \end{array}\] donde \(D=\{(x,\varepsilon,\varepsilon,\varepsilon):x\) es impar\(\}\), es \(\Sigma\)-mixta (con \(n=1\) y \(m=3\) en (M1)). Tambien notese que \[\begin{array}{rll} \{(\varepsilon,\varepsilon)\} & \rightarrow & \{\varepsilon\}\\ (\varepsilon,\varepsilon) & \rightarrow & \varepsilon \end{array}\] es \(\Sigma\)-mixta.
Dejamos al lector la facil prueba del siguiente resultado basico.
1.7. Supongamos \(\Sigma\subseteq\Gamma\) son alfabetos finitos. Entonces si \(f\) es una funcion \(\Sigma\)-mixta, \(f\) es \(\Gamma\)-mixta
Una funcion \(\Sigma\)-mixta \(f\) es \(\Sigma\)-total cuando haya \(n,m\in\omega\) tales que \(D_{f}=\omega^{n}\times\Sigma^{\ast m}\). El lema anterior nos dice que si \(\Sigma\subseteq\Gamma\), entonces toda funcion \(\Sigma\)-mixta es \(\Gamma\)-mixta. Sin envargo una funcion puede ser \(\Sigma\)-total y no ser \(\Gamma\)-total, cuando \(\Sigma\subseteq\Gamma\). Por ejemplo tomemos \(\Sigma=\{\square,\%,\blacktriangle\}\) y \(\Gamma=\{\square,\%,\blacktriangle,!\}\), y consideremos la funcion \[\begin{array}{rll} f:\omega\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & x+\left\vert \alpha\right\vert \end{array}\] Es claro que \(f\) es \(\Sigma\)-mixta y \(\Sigma\)-total. Tambien es \(\Gamma\)-mixta ya que \(D_{f}\subseteq\omega\times\Gamma^{\ast}\) y \(I_{f}\subseteq\omega\), por lo cual cumple (M1) y (M2). Sin envargo \(f\) no es \(\Gamma\)-total ya que \(D_{f}\) no es igual a \(\omega^{n}\times\Gamma^{\ast m}\), cualesquiera sean \(n\) y \(m\).
Como hemos visto recien, una funcion \(f\) puede ser \(\Sigma\)-mixta y \(\Gamma\)-mixta para dos alfabetos distintos \(\Sigma\) y \(\Gamma\) e incluso es facil construir un ejemplo en el cual \(\Sigma\) y \(\Gamma\) sean incomparables como conjuntos, es decir que ninguno incluya al otro. Dejamos al lector convencerse de que si \(f\) es una funcion que es \(\Sigma\)-mixta para algun alfabeto \(\Sigma\), entonces hay un alfabeto \(\Sigma_{0}\) el cual es el menor de todos los alfabetos respecto de los cuales \(f\) es mixta, es decir \(\Sigma_{0}\) cumple que \(f\) es \(\Sigma_{0}\)-mixta y si \(\Gamma\) es tal que \(f\) es \(\Gamma\)-mixta, entonces \(\Sigma_{0}\subseteq\Gamma\).
A continuacion daremos algunas funciones \(\Sigma\)-mixtas basicas las cuales seran frecuentemente usadas.
La funcion sucesor es definida por \[\begin{array}{rll} Suc:\omega & \rightarrow & \omega\\ n & \rightarrow & n+1 \end{array}\] La funcion predecesor es definida por \[\begin{array}{rll} Pred:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n-1 \end{array}\]
Sea \(\Sigma\) un alfabeto no vacio. Para cada \(a\in\Sigma\), definamos \[\begin{array}{rll} d_{a}:\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ \alpha & \rightarrow & \alpha a \end{array}\] La funcion \(d_{a}\) es llamada la funcion derecha sub \(a\), respecto del alfabeto \(\Sigma\).
Sea \(\Sigma\) un alfabeto. Para \(n,m,i\in\omega\) tales que \(1\leq i\leq n\), definamos \[\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & x_{i} \end{array}\] Para \(n,m,i\in\omega\) tales que \(n+1\leq i\leq n+m\), definamos \[\begin{array}{rll} p_{i}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha_{i-n} \end{array}\] Las funciones \(p_{i}^{n,m}\) son llamadas proyecciones. La funcion \(p_{i}^{n,m}\) es llamada la proyeccion \(n,m,i\), respecto del alfabeto \(\Sigma\). Notese que esta definicion requiere que \(n+m\geq1\) ya que \(i\) debe cumplir \(1\leq i\leq n+m\).
Sea \(\Sigma\) un alfabeto. Para \(n,m,k\in\omega\), y \(\alpha\in\Sigma^{\ast}\), definamos \[\begin{array}{rll} C_{k}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & k \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} C_{\alpha}^{n,m}:\omega^{n}\times\Sigma^{\ast m} & \rightarrow & \Sigma^{\ast}\\ (\vec{x},\vec{\alpha}) & \rightarrow & \alpha \end{array}\] Notese que \(C_{k}^{0,0}:\{\Diamond\}\rightarrow\{k\}\) y que \(C_{\alpha}^{0,0}:\{\Diamond\}\rightarrow\{\alpha\}\).
Definamos \[\begin{array}{rll} pr:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n\text{-esimo numero primo} \end{array}\] Notese que \(pr(1)=2\), \(pr(2)=3\), \(pr(3)=5\), etc.
Dada una funcion \(\Sigma\)-mixta \(f\), si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y ademas \(I_{f}\subseteq\omega\), entonces diremos que \(f\) es una funcion de tipo \((n,m,\#)\). Similarmente si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y ademas \(I_{f}\subseteq\Sigma^{\ast}\), entonces diremos que \(f\) es una funcion de tipo \((n,m,\ast)\). Notese que si \(f\neq\emptyset\), entonces hay unicos \(n,m\in\omega\) y \(s\in\{\#,\ast\}\) tales que \(f\) es una funcion de tipo \((n,m,s)\). Sin envargo \(\emptyset\) es una funcion de tipo \((n,m,s)\) cualesquiera sean \(n,m\in\omega\) y \(s\in\{\#,\ast\}\). De esta forma, cuando \(f\neq\emptyset\) hablaremos de "el tipo de \(f\)" para refererirnos a esta unica terna \((n,m,s)\). Notese que \(Suc\) es de tipo \((1,0,\#)\) y \(d_{a}\) es de tipo \((0,1,\ast)\).
Tambien notese que la relacion "\(f\) es una funcion de tipo \((n,m,s)\)" no depende del alfabeto \(\Sigma\) (que significa esto?).
Supongamos que \(k,l,n,m\in\omega\) y que \(F:D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega^{n}\times\Sigma^{\ast m}\). Supongamos ademas que \(n+m\geq1\). Entonces denotaremos con \(F_{(i)}\) a la funcion \(p_{i}^{n,m}\circ F\). Notar que \[\begin{aligned} F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega\text{, para cada }i=1,...,n\\ F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\Sigma^{\ast}\text{, para cada }i=n+1,...,n+m \end{aligned}\] Por lo cual cada una de las funciones \(F_{(i)}\) son \(\Sigma\)-mixtas. Ademas notese que \[F=[F_{(1)},...,F_{(n+m)}]\]
Un predicado \(\Sigma\)-mixto es una funcion \(f\) la cual es \(\Sigma\)-mixta y ademas cumple que \(I_{f}\subseteq\{0,1\}\). Por ejemplo \[\begin{array}{rll} \omega\times\omega & \rightarrow & \omega\\ (x,y) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=y\\ 0\text{ si }x\neq y \end{array}\right. \end{array}\ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} \{1,2,3,4,5\}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=\left\vert \alpha\right\vert \\ 0\text{ si }x\neq\left\vert \alpha\right\vert \end{array}\right. \end{array}\]
Dados predicados \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\), con el mismo dominio, definamos nuevos predicados \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) de la siguiente manera \[\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}\]
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:
adhocprefixE\(_{1}\)adhocsufix Sea \(\mathcal{G}\) dada por \[\begin{array}{rcl} \mathcal{G}:\{\square,\%,\blacktriangle\} & \rightarrow & \{Suc,Pred\}\\ \square & \rightarrow & Suc\\ \% & \rightarrow & Suc\\ \blacktriangle & \rightarrow & Pred \end{array}\] Claramente \(\mathcal{G}\) es una familia \(\{\square,\%,\blacktriangle\}\)-indexada de funciones. Notar que \[\mathcal{G}=\{(\square,Suc),(\%,Suc),(\blacktriangle,Pred)\}\] Se tiene tambien por ejemplo que \(\mathcal{G}(\%)=Suc\) por lo cual tambien es cierto que \(\mathcal{G}(\%)(22)=23\), etc.
adhocprefixE\(_{2}\)adhocsufix Si \(\Sigma\) es un alfabeto no vacio, la funcion \[\begin{array}{rcl} \mathcal{G}:\Sigma & \rightarrow & \{f:f\text{ es una funcion de }\Sigma^{\ast}\text{ en }\Sigma^{\ast}\}\\ a & \rightarrow & d_{a} \end{array}\] es una familia \(\Sigma\)-indexada de funciones. Notar que \[\mathcal{G}=\{(a,d_{a}):a\in\Sigma\}\]
adhocprefixE\(_{3}\)adhocsufix \(\emptyset\) es una flia \(\emptyset\)-indexada de funciones
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)\).
Un conjunto \(S\) es llamado \(\Sigma\)-mixto si hay \(n,m\in\omega\) tales que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Por ejemplo, \[\{(x,\alpha)\in\omega\times\{\blacktriangle,!\}^{\ast}:\left\vert \alpha\right\vert =x\}\] \[\{(0,\blacktriangle\blacktriangle\blacktriangle,\varepsilon),(1,\%\blacktriangle\%,\blacktriangle\blacktriangle)\}\] son conjuntos \(\{\blacktriangle,\%,!\}\)-mixtos. Tambien notese que \(\emptyset\) y \(\{\Diamond\}\) son conjuntos \(\Sigma\)-mixtos, cualesquiera sea el alfabeto \(\Sigma\). Por ultimo el conjunto \[\{(x,\varepsilon,\varepsilon,\varepsilon):x\in\omega\text{ y }x\text{ es impar}\}\] es \(\emptyset\)-mixto (con \(n=1\) y \(m=3\)).
Dado un conjunto \(\Sigma\)-mixto \(S\), si \(n,m\in\omega\) son tales que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\), entonces diremos que \(S\) es un conjunto de tipo \((n,m)\). Notese que si \(S\neq\emptyset\), entonces hay unicos \(n,m\in\omega\) tales que \(S\) es un conjunto de tipo \((n,m)\). De esta forma, cuando \(S\neq\emptyset\) hablaremos de "el tipo de \(S\)" para refererirnos a este unico par \((n,m)\). Tambien es importante notar que de la definicion anterior sale inmediatemante que \(\emptyset\) es un conjunto de tipo \((n,m)\) cualesquiera sean \(n,m\in\omega\), por lo cual cuando hablemos de EL tipo de un comjunto deberemos estar seguros de que dicho conjunto es no vacio.
Notese que \(\omega\) es de tipo \((1,0)\) y \(\Sigma^{\ast}\) es de tipo \((0,1)\).
Un conjunto \(\Sigma\)-mixto \(S\) es llamado rectangular si es de la forma \[S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m},\] con cada \(S_{i}\subseteq\omega\) y cada \(L_{i}\subseteq\Sigma^{\ast}\). Notar que todo subconjunto de \(\omega\) es rectangular (es el caso \(n=1\) y \(m=0\)). Tambien \(\{\Diamond\}\) es rectangular (es el caso \(n=m=0\)). Otros ejemplos:
adhocprefix-adhocsufix \(\mathbf{N}\times\{1,2\}\times\{@@,\varepsilon\}\) es rectangular (aqui \(n=2\) y \(m=1\))
adhocprefix-adhocsufix \(\{!!!,!!\}\times\{@@,\varepsilon\}\) es rectangular (aqui \(n=0\) y \(m=2\))
Tambien notese que \(\emptyset=\emptyset\times\emptyset\) por lo cual \(\emptyset\) es un conjunto rectangular.
El concepto de conjunto rectangular es muy importante en nuestro enfoque. Aunque en general no habra restricciones acerca del dominio de las funciones y predicados, nuestra filosofia sera tratar en lo posible que los dominios de las funciones que utilicemos para hacer nuestro analisis de recursividad de los distintos paradigmas, sean rectangulares. Aunque en principio puede pareser que todos los conjuntos son rectangulares, el siguiente lema mostrara cuan ingenua es esta vision.
1.8. Sea \(S\subseteq\omega\times\Sigma^{\ast}\). Entonces \(S\) es rectangular si y solo si se cumple la siguiente propiedad:
adhocprefix(R)adhocsufix Si \((x,\alpha),(y,\beta)\in S\), entonces \((x,\beta)\in S\)
Proof. Ejercicio.
Supongamos \(\Sigma=\{\#,\blacktriangle,\%\}\). Notese que podemos usar el lema anterior para probar por ejemplo que los siguientes conjuntos no son rectangulares
adhocprefix-adhocsufix \(\{(0,\#\#),(1,\%\%\%)\}\)
adhocprefix-adhocsufix \(\{(x,\alpha):\left\vert \alpha\right\vert =x\}\)
Dejamos como ejercicio para el lector enunciar un lema analogo al anterior pero que caracterice cuando \(S\subseteq\omega^{2}\times\Sigma^{\ast3}\) es rectangular.
Usaremos la notacion lambda de Church en la forma que se explica a continuacion. Esta notacion siempre depende de un alfabeto finito previamente fijado. En general en nuestro lenguaje matematico utilizamos diversas expresiones las cuales involucran variables que una vez fijadas en sus valores hacen que la expresion tambien represente un determinado valor
En el contexto de la notacion lambda solo se podran utilizar expresiones con caracteristicas muy especiales por lo cual a continuacion iremos describiendo que condiciones tienen que cumplir las expresiones para que puedan ser usadas en la notacion lambda
adhocprefix(1)adhocsufix Solo utilizaremos expresiones que involucran variables numericas, las cuales se valuaran en numeros de \(\omega\), y variables alfabeticas, las cuales se valuaran en palabras del alfabeto previamente fijado. Las variables numericas seran seleccionadas de la lista \[\begin{aligned} & x,y,z,w,n,m,k,...\\ & x_{1},x_{2},...\\ & y_{1},y_{2},...\\ & etc \end{aligned}\] Las variables alfabeticas seran seleccionadas de la lista \[\begin{aligned} & \alpha,\beta,\gamma,\eta,...\\ & \alpha_{1},\alpha_{2},...\\ & \beta_{1},\beta_{2},...\\ & etc \end{aligned}\]
adhocprefix(2)adhocsufix Por ejemplo la expresion: \[x+y+1\] tiene dos variables numericas \(x\) e \(y\) (y ninguna alfabetica). Si le asignamos a \(x\) el valor 2 y a \(y\) el valor 45, entonces la expresion \(x+y+1\) produce o representa el valor \(48=2+45+1\).
adhocprefix(3)adhocsufix Otro ejemplo, consideremos la expresion \[\left\vert \alpha\beta\right\vert +\left\vert \alpha\right\vert ^{x}\] la cual tiene una variable numerica \(x\) y dos variables alfabeticas \(\alpha\) y \(\beta\). Supongamos ademas que el alfabeto previamente fijado es \(\{@,\%\}\). Si le asignamos a \(x\) el valor 2, a \(\alpha\) el valor \(@@\) y a \(\beta\) el valor \(\%\%\%\), entonces la expresion \(\left\vert \alpha\beta\right\vert +\left\vert \alpha\right\vert ^{x}\) produce o representa el valor \(\left\vert @@\%\%\%\right\vert +\left\vert @@\right\vert ^{2}=9\).
adhocprefix(4)adhocsufix Para ciertas valuaciones de sus variables la expresion puede no estar definida. Por ejemplo la expresion \[Pred(\left\vert \alpha\right\vert )\] no asume valor o no esta definida cuando el valor asignado a \(\alpha\) es \(\varepsilon\). Otro ejemplo, consideremos la expresion \[x/(y-\left\vert \alpha\right\vert )^{2}\] Esta expresion no esta definida o no asume valor para aquellas asignaciones de valores a sus variables en las cuales el valor asignado a \(y\) sea igual a la longitud del valor asignado a \(\alpha\).
adhocprefix(5)adhocsufix En los ejemplos anteriores las expresiones producen valores numericos pero tambien trabajaremos con expresiones que producen valores alfabeticos. Por ejemplo la expresion \[\beta^{y}\] tiene una variable numerica, \(y\), una variable alfabetica, \(\beta\), y una vez valuadas estas variables produce un valor alfabetico, a saber el resultado de elevar el valor asignado a la variable \(\beta\), a el valor asignado a \(y\).
adhocprefix(6)adhocsufix Una expresion \(E\) para poder ser utilizada en la notacion lambda relativa a un alfabeto \(\Sigma\) debera cumplir alguna de las dos siguientes propiedades
los valores que asuma \(E\) cuando hayan sido asignados valores de \(\omega\) a sus variables numericas y valores de \(\Sigma^{\ast}\) a sus variables alfabeticas deberan ser siempre elementos de \(\omega\)
los valores que asuma \(E\) cuando hayan sido asignados valores de \(\omega\) a sus variables numericas y valores de \(\Sigma^{\ast}\) a sus variables alfabeticas deberan ser siempre elementos de \(\Sigma^{\ast}\).
adhocprefix(7)adhocsufix Por ejemplo la expresion \[x/2\] no cumple la propiedad dada en (6) ya que para ciertos valores de \(\omega\) asignados a la variable \(x\), la expresion da valores numericos que se salen de \(\omega\) por lo cual no cumple ni (a) ni (b).
adhocprefix(8)adhocsufix Otro ejemplo, si el alfabeto fijado es \(\Sigma=\{@,\%\}\), entonces la expresion \[@^{x}\$^{y}\] no cumple la propiedad dada en (6) ya que por ejemplo cuando le asignamos a \(x\) el valor 2 y a \(y\) el valor 6, la expresion nos da la palabra \(@@\$\$\$\$\$\$\) la cual no pertenece a \(\Sigma^{\ast}\) por lo cual no cumple ni (a) ni (b).
adhocprefix(9)adhocsufix No necesariamente las expresiones que usaremos en la notacion lambda deben ser hechas como combinacion de operaciones matematicas conocidas. Muchas veces usaremos expresiones que involucran incluso lenguaje coloquial castellano. Por ejemplo la expresion \[\mathrm{el\ menor\ numero\ primo\ que\ es\ mayor\ que\ }x\] Es claro que esta expresion para cada valor de \(\omega\) asignado a la variable \(x\) produce o representa un valor concreto de \(\omega\). Otro ejemplo: \[\mathrm{el\ tercer\ simbolo\ de\ }\alpha\] notese que esta expresion, una ves fijado un alfabeto \(\Sigma\), estara definida o producira un valor solo cuando le asignamos a \(\alpha\) una palabra de \(\Sigma^{\ast}\) de longitud mayor o igual a \(3\).
adhocprefix(10)adhocsufix Expresiones Booleanas. A las expresiones Booleanas tales como \[x=y+1\text{ y }\left\vert \alpha\right\vert \leq22\]
las pensaremos que asumen valores del conjunto \(\{0,1\}\subseteq\omega\). Por ejemplo la expresion anterior asume o produce el valor \(1\) cuando le asignamos a \(x\) el valor 11, a \(y\) el valor 10 y a \(\alpha\) la palabra \(\varepsilon\). Las expresiones Booleanas pensadas de esta forma podran ser utilizadas en la notacion lambda si es que tambien cumplen con las anteriores condiciones.
adhocprefix(11)adhocsufix La expresion \[5\] no tiene variables por lo cual pensaremos que siempre produce el valor \(5\) cualesquiera sean los valores asignados a las variables.
Dado un alfabeto \(\Sigma\) a las expresiones que cumplan las caracteristicas dadas anteriormente las llamaremos lambdificables con respecto a \(\Sigma\). Notese que este concepto es intuitivo y no un concepto matematicamente definido en forma precisa. Mas aun el concepto de expresion tampoco ha sido definido matematicamente (aunque obviamente si sabemos que una expresion es una palabra de cierto alfabeto). Esto no nos traera problemas para el uso notacional que las utilizaremos. Recien en las secciones de logica veremos la matematizacion de ciertas expresiones (no las lambdificables) y nos servira de ejemplo para imaginar como podriamos matematizar el concepto de expresion.
Algunos ejemplos:
adhocprefix(E1)adhocsufix \(x/2\) no es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E2)adhocsufix \(@^{x}\$^{y}\) es lambdificable con respecto a \(\{@,\$\}\) y no es lambdificable con respecto a \(\{@,\#,\%\}\)
adhocprefix(E3)adhocsufix \(x=y+1\) es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E4)adhocsufix la expresion \[\mathrm{el\ menor\ numero\ primo\ que\ es\ mayor\ que\ }x^{\left\vert \beta\right\vert }\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E5)adhocsufix la expresion \[5\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
Supongamos ya hemos fijado un alfabeto finito \(\Sigma\) y supongamos \(E\) es una expresion la cual es lambdificable con respecto a \(\Sigma\). Sea \(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\) una lista de variables todas distintas tal que las variables numericas que ocurren en \(E\) estan todas contenidas en la lista \(x_{1},...,x_{n}\) y las variables alfabeticas que ocurren en \(E\) estan en la lista \(\alpha_{1},...,\alpha_{m}\) (puede suceder que haya variables de la lista \(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\) las cuales no ocurran en \(E\)). Entonces \[\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\] denotara la funcion definida por:
adhocprefix(L1)adhocsufix El dominio de \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) es el conjunto de las \((n+m)\)-uplas \((k_{1},...,k_{n},\beta_{1},...,\beta_{m})\in\omega^{n}\times\Sigma^{\ast m}\) tales que \(E\) esta definida cuando le asignamos a cada \(x_{i}\) el valor \(k_{i}\) y a cada \(\alpha_{i}\) el valor \(\beta_{i}\).
adhocprefix(L2)adhocsufix \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right](k_{1},...,k_{n},\beta_{1},...,\beta_{m})=\) valor que asume o representa \(E\) cuando le asignamos a cada \(x_{i}\) el valor \(k_{i}\) y a cada \(\alpha_{i}\) el valor \(\beta_{i}\).
Notese que por tener \(E\) la propiedad (6) de mas arriba, la funcion \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) es \(\Sigma\)-mixta de tipo \((n,m,s)\) para algun \(s\in\{\#,\ast\}\). Algunos ejemplos:
adhocprefix(a)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{@,?,\)¡\(\}\). Entonces \(\lambda x\alpha\left[\alpha^{2x}\right]\) es la funcion \[\begin{array}{rll} \omega\times\{@,?,\text{¡}\}^{\ast} & \rightarrow & \{@,?,\text{¡}\}^{\ast}\\ (x,\alpha) & \rightarrow & \alpha^{2x} \end{array}\] Aqui el lector puede notar la dependencia de la notacion lambda respecto del alfabeto fijado. Si en lugar de fijar \(\Sigma=\{@,?,\)¡\(\}\) hubieramos fijado \(\Sigma=\{\%\}\), entonces \(\lambda x\alpha\left[\alpha^{2x}\right]\) denotaria otra funcion, a saber \[\begin{array}{rll} \omega\times\{\%\}^{\ast} & \rightarrow & \{\%\}^{\ast}\\ (x,\alpha) & \rightarrow & \alpha^{2x} \end{array}\]
adhocprefix(b)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{@,?,\)¡\(\}\). Entonces \(\lambda x\alpha\left[5\right]\) es la funcion \[\begin{array}{rll} \omega\times\{@,?,\text{¡}\}^{\ast} & \rightarrow & \omega\\ (x,y,z,\alpha) & \rightarrow & 5 \end{array}\]
adhocprefix(c)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{\%,!\}\). Entonces \(\lambda\alpha\beta\left[\alpha\beta\right]\) es la funcion \[\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\alpha,\beta) & \rightarrow & \alpha\beta \end{array}\]
Tambien tenemos que \(\lambda\beta\alpha\left[\alpha\beta\right]\) es la funcion \[\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\beta,\alpha) & \rightarrow & \alpha\beta \end{array}\] Notese que estas funciones son distintas. Por ejemplo \(\lambda\alpha\beta\left[\alpha\beta\right](\%,!)=\%!\) y \(\lambda\beta\alpha\left[\alpha\beta\right](\%,!)=!\%\)
adhocprefix(d)adhocsufix Independientemente de quien sea \(\Sigma\) el alfabeto previamente fijado, tenemos que \(\lambda xy[x+y]\) es la funcion \[\begin{array}{rll} \omega^{2} & \rightarrow & \omega\\ (x,y) & \rightarrow & x+y \end{array}\] Tambien \(\lambda xyzw[x+w]\) es la funcion \[\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+w \end{array}\]
adhocprefix(e)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{@,?,\)¡\(\}\). Entonces por la clausula (L1) tenemos que el dominio de la funcion \(\lambda xy\alpha\beta\left[Pred(\left\vert \alpha\right\vert )+Pred(y)\right]\) es \[D=\left\{ (x,y,\alpha,\beta)\in\omega^{2}\times\Sigma^{\ast2}:\left\vert \alpha\right\vert \geq1\text{ y }y\geq1\right\}\] Es decir que \(\lambda xy\alpha\beta\left[Pred(\left\vert \alpha\right\vert )+Pred(y)\right]\) es la funcion \[\begin{array}{rll} D & \rightarrow & \omega\\ (x,y,\alpha,\beta) & \rightarrow & Pred(\left\vert \alpha\right\vert )+Pred(y) \end{array}\]
adhocprefix(f)adhocsufix Atentos a (10) de mas arriba, la funcion \(\lambda xy\left[x=y\right]\) es el predicado \[\begin{array}{rll} \omega\times\omega & \rightarrow & \omega\\ (x,y) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }x=y\\ 0\text{ si }x\neq y \end{array}\right. \end{array}\] y \(\lambda x\alpha\left[Pred(x)=\left\vert \alpha\right\vert \right]\) es el predicado \[\begin{array}{rll} \mathbf{N}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }Pred(x)=\left\vert \alpha\right\vert \\ 0\text{ si }Pred(x)\neq\left\vert \alpha\right\vert \end{array}\right. \end{array}\] Tambien \(\lambda\alpha\beta\left[\alpha=\beta\right]\) es el predicado \[\begin{array}{rll} \Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \omega\\ (\alpha,\beta) & \rightarrow & \left\{ \begin{array}{l} 1\text{ si }\alpha=\beta\\ 0\text{ si }\alpha\neq\beta \end{array}\right. \end{array}\]
adhocprefix(g)adhocsufix Notar que para \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) se tiene que \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}=\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[(\vec{x},\vec{\alpha})\in S\right]\)
adhocprefix(h)adhocsufix Como dijimos, la notacion lambda depende del alfabeto previamnete fijado, aunque para el caso en que la lista de variables que sigue a la letra \(\lambda\) no tenga variables alfabeticas, la funcion representada no depende del alfabeto
Un par de ejemplos sutiles
adhocprefix(a)adhocsufix La expresion \[Suc\] no es lambdificable respecto de cualquier alfabeto \(\Sigma\). Esto es porque si bien cualesquiera sea el valor asignado a las variables, ella asume el valor \(Suc\), no cumple (6) de mas arriba ya que \(Suc\) no es un elemento de \(\omega\) ni tampoco una palabra (es una funcion!)
adhocprefix(b)adhocsufix La expresion \[Suc+(\left\vert \beta\right\vert +1)\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\). Por ejemplo \(\lambda x\beta[Suc+(\left\vert \beta\right\vert +1)]\) es la funcion \(\emptyset\), ya que la expresion \(Suc+(\left\vert \beta\right\vert +1)\) cualesquiera sean los valores de \(x\) y \(\beta\) no esta definida.