Sea \(\Sigma\) un alfabeto finito. Dados \(n,m\in\omega\), usaremos \(\omega^{n}\times\Sigma^{\ast m}\) para abreviar la expresión \[\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}\) será 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 convención 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.
Nótese que:
adhocprefix-adhocsufix Cuando \(n=m=0\), tenemos que \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\{\lozenge\}\)
adhocprefix-adhocsufix Si \(m=0\), entonces \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\omega^{n}\)
adhocprefix-adhocsufix Si \(n=0\), entonces \(\omega^{n}\times\Sigma^{\ast m}\) denota el conjunto \(\Sigma^{\ast m}\)
adhocprefix-adhocsufix Cuando \(\Sigma=\emptyset\), tenemos que \(\Sigma^{\ast}=\{\varepsilon\}\). O sea que por ejemplo \[\omega^{n}\times\Sigma^{\ast5}=\{(x_{1},...,x_{n},\varepsilon,\varepsilon,\varepsilon,\varepsilon,\varepsilon):x_{1},...,x_{n}\in\omega\}\]
Es decir que tenemos que tener cuidado cuando leemos esta notación y no caer en la confusión de interpretarla mal.
Con esta convención notacional, un elemento genérico 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 función \(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:
adhocprefix(E1)adhocsufix Sea \(\Sigma=\{\square,\%,\blacktriangle\}\). La función \[\begin{array}{rll} f:\{(1,\square\%\%),(100,\%\blacktriangle\blacktriangle)\} & \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 también cumple (M2). Nótese que \(f\) no es \(\{\square,\%\}\)-mixta ya que no cumple (M1) respecto del alfabeto \(\{\square,\%\}\). Sin embargo note que \(f\) es \(\{\square,\%,\blacktriangle,@\}\)-mixta
adhocprefix(E2)adhocsufix La función \[\begin{array}{rll} \omega^{4} & \rightarrow & \omega\\ (x,y,z,w) & \rightarrow & x+y \end{array}\] es \(\Sigma\)-mixta cualesquiera sea el alfabeto \(\Sigma\)
adhocprefix(E3)adhocsufix Sea \(\Sigma=\{\square,@\}\). La función \[\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)
adhocprefix(E4)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)). También nótese que \[\begin{array}{rll} \{(\varepsilon,\varepsilon)\} & \rightarrow & \{\varepsilon\}\\ (\varepsilon,\varepsilon) & \rightarrow & \varepsilon \end{array}\] es \(\Sigma\)-mixta (con \(n=0\) y \(m=2\) en (M1)).
Dejamos al lector la fácil prueba del siguiente resultado básico.
1.8. Supongamos \(\Sigma\subseteq\Gamma\) son alfabetos finitos. Entonces si \(f\) es una función \(\Sigma\)-mixta, \(f\) es \(\Gamma\)-mixta
Una función \(\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 función \(\Sigma\)-mixta es \(\Gamma\)-mixta. Sin embargo una función 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 función \[\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. También 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 embargo \(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 recién, una función \(f\) puede ser \(\Sigma\)-mixta y \(\Gamma\)-mixta para dos alfabetos distintos \(\Sigma\) y \(\Gamma\) e incluso es fácil 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 función que es \(\Sigma\)-mixta para algún 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 continuación daremos algunas funciones \(\Sigma\)-mixtas básicas las cuales serán frecuentemente usadas.
La función sucesor es definida por \[\begin{array}{rll} Suc:\omega & \rightarrow & \omega\\ n & \rightarrow & n+1 \end{array}\] La función predecesor es definida por \[\begin{array}{rll} Pred:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n-1 \end{array}\]
Sea \(\Sigma\) un alfabeto no vacío. Para cada \(a\in\Sigma\), definamos \[\begin{array}{rll} d_{a}:\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ \alpha & \rightarrow & \alpha a \end{array}\] La función \(d_{a}\) es llamada la función 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 función \(p_{i}^{n,m}\) es llamada la proyección \(n,m,i\), respecto del alfabeto \(\Sigma\). Nótese que esta definición requiere que \(n+m\geq1\) ya que \(i\) debe cumplir \(1\leq i\leq n+m\). Además nótese que siempre la función \(p_{i}^{n,m}\) aplicada a una \((n+m)\)-upla da la coordenada \(i\)-ésima de dicha \((n+m)\)-upla. Por ejemplo: \[\begin{array}{rll} p_{3}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & \alpha_{2} \end{array}\]
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}\] Por ejemplo: \[\begin{array}{rll} C_{3}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \omega\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & 3 \end{array}\ \ \ \ \ \ \ \ \ \ \ \begin{array}{rll} C_{\varepsilon}^{1,3}:\omega\times\Sigma^{\ast}\times\Sigma^{\ast}\times\Sigma^{\ast} & \rightarrow & \Sigma^{\ast}\\ (x,\alpha_{1},\alpha_{2},\alpha_{3}) & \rightarrow & \varepsilon \end{array}\] Nótese que \(C_{k}^{0,0}:\{\lozenge\}\rightarrow\{k\}\) y que \(C_{\alpha}^{0,0}:\{\lozenge\}\rightarrow\{\alpha\}\).
Definamos \[\begin{array}{rll} pr:\mathbf{N} & \rightarrow & \omega\\ n & \rightarrow & n\text{-esimo número primo} \end{array}\] Nótese que \(pr(1)=2\), \(pr(2)=3\), \(pr(3)=5\), etc.
Dada una función \(\Sigma\)-mixta \(f\), si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y además \(I_{f}\subseteq\omega\), entonces diremos que \(f\) es una función de tipo \((n,m,\#)\). Similarmente si \(n,m\in\omega\) son tales que \(D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\) y además \(I_{f}\subseteq\Sigma^{\ast}\), entonces diremos que \(f\) es una función de tipo \((n,m,\ast)\). Nótese que si \(f\neq\emptyset\), entonces hay únicos \(n,m\in\omega\) y \(s\in\{\#,\ast\}\) tales que \(f\) es una función de tipo \((n,m,s)\). Sin embargo \(\emptyset\) es una función 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 referirnos a esta única terna \((n,m,s)\). Nótese que \(Suc\) es de tipo \((1,0,\#)\) y \(d_{a}\) es de tipo \((0,1,\ast)\).
También nótese que la relación "\(f\) es una función 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 además que \(n+m\geq1\). Entonces denotaremos con \(F_{(i)}\) a la función \(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. Además nótese que \[F=[F_{(1)},...,F_{(n+m)}]\]
Un predicado \(\Sigma\)-mixto es una función \(f\) la cual es \(\Sigma\)-mixta y además 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 será una función \(\mathcal{G}\) tal que \(D_{\mathcal{G}}=\Sigma\) y para cada \(a\in D_{\mathcal{G}}\) se tiene que \(\mathcal{G}(a)\) es una función. Algunos ejemplos:
adhocprefix(E1)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 también por ejemplo que \(\mathcal{G}(\%)=Suc\) por lo cual también es cierto que \(\mathcal{G}(\%)(22)=23\), etc.
adhocprefix(E2)adhocsufix Si \(\Sigma\) es un alfabeto no vacío, la función \[\begin{array}{rcl} \mathcal{G}:\Sigma & \rightarrow & \{f:f\text{ es una función 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\}\]
adhocprefix(E3)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. También nótese que \(\emptyset\) y \(\{\lozenge\}\) son conjuntos \(\Sigma\)-mixtos, cualesquiera sea el alfabeto \(\Sigma\). Por último 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)\). Nótese que si \(S\neq\emptyset\), entonces hay únicos \(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 referirnos a este único par \((n,m)\). También es importante notar que de la definición anterior sale inmediatamente 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 conjunto deberemos estar seguros de que dicho conjunto es no vacío.
Nótese 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\)). También \(\{\lozenge\}\) es rectangular (es el caso \(n=m=0\)). Otros ejemplos:
adhocprefix-adhocsufix \(\mathbf{N}\times\{1,2\}\times\{@@,\varepsilon\}\) es rectangular (aquí \(n=2\) y \(m=1\))
adhocprefix-adhocsufix \(\{!!!,!!\}\times\{@@,\varepsilon\}\) es rectangular (aquí \(n=0\) y \(m=2\))
También nótese 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 habrá restricciones acerca del dominio de las funciones y predicados, nuestra filosofía será tratar en lo posible que los dominios de las funciones que utilicemos para hacer nuestro análisis de recursividad de los distintos paradigmas, sean rectangulares. Aunque en principio puede parecer que todos los conjuntos son rectangulares, el siguiente lema mostrara cuan ingenua es esta visión.
1.9. 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,\%\}\). Nótese 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 análogo al anterior pero que caracterice cuando \(S\subseteq\omega^{2}\times\Sigma^{\ast3}\) es rectangular.
Usaremos la notación lambda de Church en la forma que se explica a continuación. La idea de usar la notación lambda fue sacada del libro de Bell y Machover. Esta notación siempre depende de un alfabeto finito previamente fijado. En general en nuestro lenguaje matemático utilizamos diversas expresiones las cuales involucran variables que una vez fijadas en sus valores hacen que la expresión también represente un determinado valor. No definiremos en forma precisa el concepto de expresión pero debería quedar claro que una expresión como objeto es una palabra. Podriamos pensar que una expresión es una palabra la cual tiene algún significado matemático. Obviamente esta es una descripción intuitiva y no precisa del concepto de expresión pero a los fines del uso que nosotros daremos a este concepto nos será suficiente.
En el contexto de la notación lambda solo se podrán utilizar expresiones con características muy especiales por lo cual a continuación iremos describiendo que condiciones tienen que cumplir las expresiones para que puedan ser usadas en la notación lambda.
adhocprefix(1)adhocsufix Solo utilizaremos expresiones que involucran variables numéricas, las cuales se valuarán en números de \(\omega\), y variables alfabéticas, las cuales se valuaran en palabras del alfabeto previamente fijado. Las variables numéricas serán 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 alfabéticas serán 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 expresión: \[x+y+1\] tiene dos variables numéricas \(x\) e \(y\) (y ninguna alfabética). Si le asignamos a \(x\) el valor 2 y a \(y\) el valor 45, entonces la expresión \(x+y+1\) produce o representa el valor \(48=2+45+1\).
adhocprefix(3)adhocsufix Otro ejemplo, consideremos la expresión \[\left\vert \alpha\beta\right\vert +\left\vert \alpha\right\vert ^{x}\] la cual tiene una variable numérica \(x\) y dos variables alfabéticas \(\alpha\) y \(\beta\). Supongamos además 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 expresión \(\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 expresión puede no estar definida en el sentido que cuando reemplazamos en ella dichos valores la palabra obtenida no representa en forma precisa un objeto. Por ejemplo la expresión \[Pred(\left\vert \alpha\right\vert )\] cuando le asignamos a \(\alpha\) la palabra \(\varepsilon\), nos queda la expresión \(Pred(\left\vert \varepsilon\right\vert )\) la cual no representa un objeto matemático en forma precisa. Otro ejemplo, consideremos la expresión \[x/(y-\left\vert \alpha\right\vert )^{2}\] Esta expresión 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\). Un último ejemplo, la expresión \[x/y/z\] no esta definida en forma precisa cuando le damos a \(x,y,z\) los valores \(100,10,5\) ya que nos queda la expresión \(100/10/5\) la cual es imprecisa puesto que es ambigua ya que no sabemos en que orden dividir.
adhocprefix(5)adhocsufix En los ejemplos anteriores las expresiones producen valores numéricos pero también trabajaremos con expresiones que producen valores alfabéticos. Por ejemplo la expresión \[\beta^{y}\] tiene una variable numérica, \(y\), una variable alfabética, \(\beta\), y una vez valuadas estas variables produce un valor alfabético, a saber el resultado de elevar el valor asignado a la variable \(\beta\), a el valor asignado a \(y\).
adhocprefix(6)adhocsufix También consideraremos expresiones en las cuales no ocurren variables, es decir ellas representan un valor concreto. Por ejemplo la expresión \[5\] siempre produce el valor \(5\). O la expresión \[17+11\] siempre produce el valor 28. También la expresión \[1/0\] no tiene variables y además es siempre indefinida. Es decir no representa un valor u objeto.
adhocprefix(7)adhocsufix Una expresión \(E\) para poder ser utilizada en la notación lambda relativa a un alfabeto \(\Sigma\) deberá cumplir alguna de las dos siguientes propiedades
los valores que asuma \(E\) cuando hayan sido asignados valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas deberán ser siempre elementos de \(\omega\)
los valores que asuma \(E\) cuando hayan sido asignados valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas deberán ser siempre elementos de \(\Sigma^{\ast}\)
Cabe destacar que la expresión \(E\) puede, para alguna asignación de valores de \(\omega\) a sus variables numéricas y valores de \(\Sigma^{\ast}\) a sus variables alfabéticas, no estar definida o representar en forma precisa algún objeto matemático.
adhocprefix(8)adhocsufix Por ejemplo la expresión \[x/2\] no cumple la propiedad dada en (7) ya que para ciertos valores de \(\omega\) asignados a la variable \(x\), la expresión da valores numéricos que se salen de \(\omega\) por lo cual no cumple ni (a) ni (b).
adhocprefix(9)adhocsufix Otro ejemplo, si el alfabeto fijado es \(\Sigma=\{@,\%\}\), entonces la expresión \[@^{x}\$^{y}\] no cumple la propiedad dada en (7) ya que por ejemplo cuando le asignamos a \(x\) el valor 2 y a \(y\) el valor 6, la expresión nos da la palabra \(@@\$\$\$\$\$\$\) la cual no pertenece a \(\Sigma^{\ast}\) por lo cual no cumple ni (a) ni (b).
adhocprefix(10)adhocsufix No necesariamente las expresiones que usaremos en la notación lambda deben ser hechas como combinación de operaciones matemáticas conocidas. Muchas veces usaremos expresiones que involucran incluso lenguaje coloquial castellano. Por ejemplo la expresión \[\mathrm{el\ menor\ n\acute{u}mero\ primo\ que\ es\ mayor\ que\ }x\] Es claro que esta expresión 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\] nótese que esta expresión, una ves fijado un alfabeto \(\Sigma\), estará definida o producirá un valor solo cuando le asignamos a \(\alpha\) una palabra de \(\Sigma^{\ast}\) de longitud mayor o igual a \(3\).
adhocprefix(11)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 expresión 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 podrán ser utilizadas en la notación lambda si es que también cumplen con las anteriores condiciones. Otro ejemplo \[11=17\] es una expresión Booleana que no tiene variables y siempre produce el valor 0.
adhocprefix(12)adhocsufix Seremos muy estrictos en lo que respecta a cuando “una expresión \(E\) esta definida (o representa o produce) en forma precisa un valor, para una valuación dada de sus variables”. El criterio será similar al usado en la tómbola con los vofois en el sentido que la mas mínima imprecisión ya implicara que para esa valuación la expresión no esta definida. Algunos ejemplos:
Consideremos la expresión \[0.Suc(z,z)\] Uno podría pensar que cualquiera sea el valor de \(\omega\) asignado a la variable \(z\), la expresión produce el valor \(0\), ya que cualquiera sea el valor de \(Suc(z,z)\), al multiplicarlo por \(0\) nos dará \(0\). Sin embargo para nosotros la expresión \(0.Suc(z,z)\) no estará definida en forma precisa cualquiera sea el valor que le asignemos a \(z\) y esto es porque \(Suc(z,z)\) tiene una imprecisión ya que \(Suc\) no se aplica a pares ordenados.
Consideremos la expresión \[0.(4/x/2)\] Esta expresión no estará definida en forma precisa para ningún valor de \(x\) ya que la expresión \(4/x/2\) es ambigua puesto que no aclara en que orden se realizan las definiciones. Nótese que aunque al multiplicar por \(0\) podríamos pensar que la expresión produce siempre \(0\), optamos por convenir que la expresión nunca produce en forma precisa valores u objetos.
Consideremos la expresión Booleana \[Pred(0)=1\text{ o }5\leq x\] Uno podría pensar que esta expresión produce el valor \(1\) cuando le asignamos a \(x\) un valor mayor o igual a \(5\) ya que independientemente de que signifique \(Pred(0)=1\) se hace verdadero que \(5\leq x\) por lo cual será verdadero el “o” de ambos enunciados. Sin embargo esta expresión no esta definida en forma precisa para ninguna asignación de valores a \(x\) ya que \(Pred(0)\) es una imprecisión que es parte de la expresión. (O sea sucede lo mismo que en los vofois).
Consideremos la expresión Booleana \[(\forall t\in\emptyset)\text{ }Pred(x).t\text{ es impar}\] Uno podría pensar que esta expresión produce el valor \(1\) independientemente de cuanto vale \(x\) ya que debemos chequear que \(Pred(x).t\) sea impar para \(0\) valores posibles de \(t\). Sin embargo esta expresión no esta definida en forma precisa para el caso en que hacemos valer \(0\) a \(x\) ya que en este caso \(Pred\) no esta definida. Obviamente para cualquier valor de \(\mathbf{N}\) que asignemos a \(x\) la expresión produce en forma precisa el valor \(1\)
Dado un alfabeto \(\Sigma\) a las expresiones que cumplan las características dadas anteriormente las llamaremos lambdificables con respecto a \(\Sigma\). Nótese que este concepto es intuitivo y no un concepto matemáticamente definido en forma precisa. Mas aun el concepto de expresión tampoco ha sido definido matemáticamente (aunque obviamente si sabemos que una expresión es una palabra de cierto alfabeto). Esto no nos traerá problemas para el uso notacional que las utilizaremos. Recién en las secciones de lógica veremos la matematización de ciertas expresiones (no las lambdificables) y nos servirá de ejemplo para imaginar como podríamos matematizar el concepto de expresión lambdificable.
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 expresión \[\mathrm{el\ menor\ n\acute{u}mero\ primo\ que\ es\ mayor\ que\ }x^{\left\vert \beta\right\vert }\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E5)adhocsufix la expresión \[5\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\)
adhocprefix(E6)adhocsufix la expresión \[Suc(x/20)\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\). Nótese que esta expresión no esta definida o no asume valor para aquellas asignaciones de valores a \(x\) en las cuales \(x/20\) no sea un elemento de \(\omega\) ya que en estos casos \(x/20\) no pertenece al dominio de \(Suc\). Mas concretamente dicha expresión esta definida o produce un valor cuando le asignamos a \(x\) un valor múltiplo de \(20\). Nótese que sin embargo, la expresión \[(x/20)+1\] no es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\) (por que?).
Supongamos ya hemos fijado un alfabeto finito \(\Sigma\) y supongamos \(E\) es una expresión la cual es lambdificable con respecto a \(\Sigma\). Sea \(x_{1},...,x_{n},\alpha_{1},...,\alpha_{m}\) (con \(n,m\in\omega\)) una lista de variables todas distintas tal que las variables numéricas que ocurren en \(E\) están todas contenidas en la lista \(x_{1},...,x_{n}\) y las variables alfabéticas que ocurren en \(E\) están 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]\] denotará la función 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 en forma precisa 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, produce o representa \(E\) cuando le asignamos a cada \(x_{i}\) el valor \(k_{i}\) y a cada \(\alpha_{i}\) el valor \(\beta_{i}\).
Nótese que por tener \(E\) la propiedad (7) de mas arriba, la función \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) es \(\Sigma\)-mixta de tipo \((n,m,s)\) para algún \(s\in\{\#,\ast\}\). También nótese que cuando \(n=m=0\) la expresión \(E\) deberá no tener variables y \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}\left[E\right]\) pasara a ser \(\lambda\left[E\right]\). Además \(\lambda\left[E\right]\) será la función vacía cuando \(E\) no produzca o represente un valor y en caso contrario \(\lambda\left[E\right]\) tendrá dominio igual a \(\{\lozenge\}\). Algunos ejemplos:
adhocprefix(a)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{@,?,\)¡\(\}\). Entonces \(\lambda x\alpha\left[\alpha^{2x}\right]\) es la función \[\begin{array}{rll} \omega\times\{@,?,\text{¡}\}^{\ast} & \rightarrow & \{@,?,\text{¡}\}^{\ast}\\ (x,\alpha) & \rightarrow & \alpha^{2x} \end{array}\] Aquí el lector puede notar la dependencia de la notación lambda respecto del alfabeto fijado. Si en lugar de fijar \(\Sigma=\{@,?,\)¡\(\}\) hubiéramos fijado \(\Sigma=\{\%\}\), entonces \(\lambda x\alpha\left[\alpha^{2x}\right]\) denotaría otra función, 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 función \[\begin{array}{rll} \omega\times\{@,?,\text{¡}\}^{\ast} & \rightarrow & \omega\\ (x,\alpha) & \rightarrow & 5 \end{array}\]
adhocprefix(c)adhocsufix Supongamos fijamos el alfabeto \(\Sigma=\{\%,!\}\). Entonces \(\lambda\alpha\beta\left[\alpha\beta\right]\) es la función \[\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\alpha,\beta) & \rightarrow & \alpha\beta \end{array}\]
También tenemos que \(\lambda\beta\alpha\left[\alpha\beta\right]\) es la función \[\begin{array}{rll} \{\%,!\}^{\ast}\times\{\%,!\}^{\ast} & \rightarrow & \{\%,!\}^{\ast}\\ (\beta,\alpha) & \rightarrow & \alpha\beta \end{array}\] Nótese 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 función \[\begin{array}{rll} \omega^{2} & \rightarrow & \omega\\ (x,y) & \rightarrow & x+y \end{array}\] También \(\lambda xyzw[x+w]\) es la función \[\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 función \(\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 función \[\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 (11) de mas arriba, la función \(\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}\] También \(\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 notación lambda depende del alfabeto previamente fijado, aunque para el caso en que la lista de variables que sigue a la letra \(\lambda\) no tenga variables alfabéticas, la función representada no depende del alfabeto.
adhocprefix(i)adhocsufix La función \(\lambda x\left[Suc(x/20)\right]\) es la siguiente función: \[\begin{array}{rll} \{x\in\omega:20\text{ divide a }x\} & \rightarrow & \omega\\ x & \rightarrow & x+1 \end{array}\]
adhocprefix(j)adhocsufix La función \(\lambda\left[5\right]\) es la función \[\begin{array}{rll} \{\lozenge\} & \rightarrow & \omega\\ \lozenge & \rightarrow & 5 \end{array}\]
adhocprefix(k)adhocsufix La función \(\lambda\left[1/0\right]\) es la función vacía, es decir \(\lambda\left[1/0\right]=\emptyset\)
adhocprefix(l)adhocsufix La función \(\lambda\left[11=17\right]\) es la función \[\begin{array}{rll} \{\lozenge\} & \rightarrow & \omega\\ \lozenge & \rightarrow & 0 \end{array}\]
Algunos ejemplos sutiles
adhocprefix(a)adhocsufix La expresión \[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\) (ya que no tiene variables), no cumple (6) de mas arriba ya que \(Suc\) no es un elemento de \(\omega\) ni tampoco una palabra (es una función!)
adhocprefix(b)adhocsufix La expresión \[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 función \(\emptyset\), ya que la expresión \(Suc+(\left\vert \beta\right\vert +1)\) cualesquiera sean los valores de \(x\) y \(\beta\) no esta definida.
adhocprefix(c)adhocsufix La expresión \[Suc+1\] es lambdificable con respecto a \(\Sigma\) cualesquiera sea \(\Sigma\) ya que no esta definida nunca y obtenemos entonces que \(\lambda x_{1}...x_{n}\alpha_{1}...\alpha_{m}[Suc+1]\) es la función \(\emptyset\), cualesquiera sean las variables \(x_{1}...x_{n}\alpha_{1}...\alpha_{m}\). En particular \(\lambda[Suc+1]=\emptyset\).