1.10 Funciones y conjuntos $\Sigma$-mixtos

Sea $\Sigma$ un alfabeto finito. Dados $n,m\in \omega$, usaremos ${\omega }^n\times {\Sigma }^{\ast m}$ para abreviar la expresion $$\stackrel{n\text{veces}}{\stackrel{}{\omega \times ...\times \omega }}\times \stackrel{m\text{veces}}{\stackrel{}{{\Sigma }^{\ast }\times ...\times {\Sigma }^{\ast }}}$$ Por ejemplo, ${\omega }^3\times {\Sigma }^{\ast 4}$ 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 }^{\ast 4}$ 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:

1. - Cuando $n=m=0$, tenemos que ${\omega }^n\times {\Sigma }^{\ast m}$ denota el conjunto $\left\{◊\right\}$

2. - Si $m=0$, entonces ${\omega }^n\times {\Sigma }^{\ast m}$ denota el conjunto ${\omega }^n$

3. - Si $n=0$, entonces ${\omega }^n\times {\Sigma }^{\ast m}$ denota el conjunto ${\Sigma }^{\ast m}$

4. - Cuando $\Sigma =\varnothing$, tenemos que ${\Sigma }^{\ast }=\left\{\epsilon \right\}$. O sea que por ejemplo $${\omega }^n\times {\Sigma }^{\ast 5}=\left\{\right(x_1,...,x_n,\epsilon ,\epsilon ,\epsilon ,\epsilon ,\epsilon ):x_1,...,x_n\in \omega \}$$

Es decir que tenemos que tener cuidado cuando leemos esta notacion y no caer en la confucion de interpretarla mal.

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 $(\overrightarrow{x},\overrightarrow{\alpha })$ en lugar de $(x_1,...,x_n,{\alpha }_1,...,{\alpha }_m)$.

1.10.1 Definicion de funcion $\Sigma$-mixta

Sea $\Sigma$ un alfabeto finito. Dada una funcion $f$, diremos que $f$ es $\Sigma$-mixta si cumple las siguientes propiedades

1. (M1) Existen $n,m\ge 0$, tales que $D_f\subseteq {\omega }^n\times {\Sigma }^{\ast m}$

2. (M2) Ya sea $I_f\subseteq \omega$ o $I_f\subseteq {\Sigma }^{\ast }$

Algunos ejemplos:

1. (E1) Sea $\Sigma =\{\square ,\%,▲\}$. La funcion $$\begin{array}{ccc}f:\left\{\right(1,\square \%\%),(100,\%▲▲\left)\right\}& \to & \omega \\ (x,\alpha )& \to & x+\left|\alpha \right|\end{array}$$ es $\Sigma$-mixta ya que se cumple (M1) con $n=m=1$ y tambien cumple (M2). Notese que $f$ no es $\{\square ,\%\}$-mixta ya que no cumple (M1) respecto del alfabeto $\{\square ,\%\}$. Sin envargo note que $f$ es $\{\square ,\%,▲,@\}$-mixta

2. (E2) La funcion $$\begin{array}{ccc}{\omega }^4& \to & \omega \\ (x,y,z,w)& \to & x+y\end{array}$$ es $\Sigma$-mixta cualesquiera sea el alfabeto $\Sigma$

3. (E3) Sea $\Sigma =\{\square ,@\}$. La funcion $$\begin{array}{ccc}\{\square \square \square ,@@\}& \to & \omega \\ \alpha & \to & \left|\alpha \right|\end{array}$$

   es $\Sigma$-mixta ya que se cumple (M1) (con $n=0$ y $m=1$) y (M2)

4. (E4) Supongamos $\Sigma =\varnothing$. Tenemos entonces que ${\Sigma }^{\ast }=\left\{\epsilon \right\}$. Por ejemplo $$\begin{array}{ccc}D& \to & \omega \\ (x,\epsilon ,\epsilon ,\epsilon )& \to & x^2\end{array}$$ donde $D=\left\{\right(x,\epsilon ,\epsilon ,\epsilon ):x$ es impar$\}$, es $\Sigma$-mixta (con $n=1$ y $m=3$ en (M1)). Tambien notese que $$\begin{array}{ccc}\left\{\right(\epsilon ,\epsilon \left)\right\}& \to & \left\{\epsilon \right\}\\ (\epsilon ,\epsilon )& \to & \epsilon \end{array}$$ es $\Sigma$-mixta (con $n=0$ y $m=2$ en (M1)).

Dejamos al lector la facil prueba del siguiente resultado basico.

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 ,\%,▲\}$ y $\Gamma =\{\square ,\%,▲,!\}$, y consideremos la funcion $$\begin{array}{ccc}f:\omega \times {\Sigma }^{\ast }& \to & \omega \\ (x,\alpha )& \to & x+\left|\alpha \right|\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.

Funciones $Suc$ y $Pred$

La funcion sucesor es definida por $$\begin{array}{ccc}Suc:\omega & \to & \omega \\ n& \to & n+1\end{array}$$ La funcion predecesor es definida por $$\begin{array}{ccc}Pred:N& \to & \omega \\ n& \to & n-1\end{array}$$

Las funciones $d_a$

Sea $\Sigma$ un alfabeto no vacio. Para cada $a\in \Sigma$, definamos $$\begin{array}{ccc}{d}_a:{\Sigma }^{\ast }& \to & {\Sigma }^{\ast }\\ \alpha & \to & \alpha a\end{array}$$ La funcion $d_a$ es llamada la funcion derecha sub $a$, respecto del alfabeto $\Sigma$.

Las funciones $p_i^{n,m}$

Sea $\Sigma$ un alfabeto. Para $n,m,i\in \omega$ tales que $1\le i\le n$, definamos $$\begin{array}{ccc}{p}_i^{n,m}:{\omega }^n\times {\Sigma }^{\ast m}& \to & \omega \\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & x_i\end{array}$$ Para $n,m,i\in \omega$ tales que $n+1\le i\le n+m$, definamos $$\begin{array}{ccc}{p}_i^{n,m}:{\omega }^n\times {\Sigma }^{\ast m}& \to & {\Sigma }^{\ast }\\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & {\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\ge 1$ ya que $i$ debe cumplir $1\le i\le n+m$. Ademas notese que siempre la funcion $p_i^{n,m}$ aplicada a una $(n+m)$-upla da la coordenada $i$-esima de dicha $(n+m)$-upla. Por ejemplo: $$\begin{array}{ccc}{p}_3^{1,3}:\omega \times {\Sigma }^{\ast }\times {\Sigma }^{\ast }\times {\Sigma }^{\ast }& \to & {\Sigma }^{\ast }\\ (x,{\alpha }_1,{\alpha }_2,{\alpha }_3)& \to & {\alpha }_2\end{array}$$

Las funciones $C_k^{n,m}$ y $C_{\alpha }^{n,m}$

Sea $\Sigma$ un alfabeto. Para $n,m,k\in \omega$, y $\alpha \in {\Sigma }^{\ast }$, definamos $$\begin{array}{ccc}{C}_k^{n,m}:{\omega }^n\times {\Sigma }^{\ast m}& \to & \omega \\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & k\end{array}\begin{array}{ccc}{C}_{\alpha }^{n,m}:{\omega }^n\times {\Sigma }^{\ast m}& \to & {\Sigma }^{\ast }\\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & \alpha \end{array}$$ Por ejemplo: $$\begin{array}{ccc}{C}_3^{1,3}:\omega \times {\Sigma }^{\ast }\times {\Sigma }^{\ast }\times {\Sigma }^{\ast }& \to & \omega \\ (x,{\alpha }_1,{\alpha }_2,{\alpha }_3)& \to & 3\end{array}\begin{array}{ccc}{C}_{\epsilon }^{1,3}:\omega \times {\Sigma }^{\ast }\times {\Sigma }^{\ast }\times {\Sigma }^{\ast }& \to & \omega \\ (x,{\alpha }_1,{\alpha }_2,{\alpha }_3)& \to & \epsilon \end{array}$$ Notese que $C_k^{0,0}:\left\{◊\right\}\to \left\{k\right\}$ y que $C_{\alpha }^{0,0}:\left\{◊\right\}\to \left\{\alpha \right\}$.

La funcion $pr$

Definamos $$\begin{array}{ccc}pr:N& \to & \omega \\ n& \to & n\text{-esimo numero primo}\end{array}$$ Notese que $pr\left(1\right)=2$, $pr\left(2\right)=3$, $pr\left(3\right)=5$, etc.

1.10.2 El tipo de una funcion mixta

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\ne \varnothing$, entonces hay unicos $n,m\in \omega$ y $s\in \{\#,\ast \}$ tales que $f$ es una funcion de tipo $(n,m,s)$. Sin envargo $\varnothing$ es una funcion de tipo $(n,m,s)$ cualesquiera sean $n,m\in \omega$ y $s\in \{\#,\ast \}$. De esta forma, cuando $f\ne \varnothing$ 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?).

1.10.3 Funciones con imagen contenida en ${\omega }^n\times {\Sigma }^{\ast m}$

Supongamos que $k,l,n,m\in \omega$ y que $F:D_F\subseteq {\omega }^k\times {\Sigma }^{\ast l}\to {\omega }^n\times {\Sigma }^{\ast m}$. Supongamos ademas que $n+m\ge 1$. Entonces denotaremos con $F_{\left(i\right)}$ a la funcion $p_i^{n,m}\circ F$. Notar que $$\begin{array}{cc}{F}_{\left(i\right)}& :D_F\subseteq {\omega }^k\times {\Sigma }^{\ast l}\to \omega \text{, para cada}i=1,...,n\\ F_{\left(i\right)}& :D_F\subseteq {\omega }^k\times {\Sigma }^{\ast l}\to {\Sigma }^{\ast }\text{, para cada}i=n+1,...,n+m\end{array}$$ Por lo cual cada una de las funciones $F_{\left(i\right)}$ son $\Sigma$-mixtas. Ademas notese que $$F=[F_{\left(1\right)},...,F_{(n+m)}]$$

1.10.4 Predicados $\Sigma$-mixtos

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}{ccc}\omega \times \omega & \to & \omega \\ (x,y)& \to & \{\begin{array}{c}1\text{si}x=y\\ 0\text{si}x\ne y\end{array}\end{array}\begin{array}{ccc}\{1,2,3,4,5\}\times {\Sigma }^{\ast }& \to & \omega \\ (x,\alpha )& \to & \{\begin{array}{c}1\text{si}x=\left|\alpha \right|\\ 0\text{si}x\ne \left|\alpha \right|\end{array}\end{array}$$

Operaciones logicas entre predicados

Dados predicados $P:S\subseteq {\omega }^n\times {\Sigma }^{\ast m}\to \{0,1\}$ y $Q:S\subseteq {\omega }^n\times {\Sigma }^{\ast m}\to \{0,1\}$, con el mismo dominio, definamos nuevos predicados $(P\vee Q)$, $(P\wedge Q)$ y $\neg P$ de la siguiente manera $$\begin{array}{ccc}(P\vee Q):S& \to & \omega \\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & \{\begin{array}{ccc}1& & \text{si}P(\overrightarrow{x},\overrightarrow{\alpha })=1\text{o}Q(\overrightarrow{x},\overrightarrow{\alpha })=1\\ 0& & \text{caso contrario}\end{array}\end{array}$$ $$\begin{array}{ccc}(P\wedge Q):S& \to & \omega \\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & \{\begin{array}{ccc}1& & \text{si}P(\overrightarrow{x},\overrightarrow{\alpha })=1\text{y}Q(\overrightarrow{x},\overrightarrow{\alpha })=1\\ 0& & \text{caso contrario}\end{array}\end{array}$$ $$\begin{array}{ccc}\neg P:S& \to & \omega \\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & \{\begin{array}{ccc}1& & \text{si}P(\overrightarrow{x},\overrightarrow{\alpha })=0\\ 0& & \text{si}P(\overrightarrow{x},\overrightarrow{\alpha })=1\end{array}\end{array}$$

1.10.5 Familias $\Sigma$-indexadas de funciones

Dado un alfabeto $\Sigma$, una familia $\Sigma$-indexada de funciones sera una funcion $G$ tal que $D_G=\Sigma$ y para cada $a\in D_G$ se tiene que $G\left(a\right)$ es una funcion. Algunos ejemplos:

1. (E1) Sea $G$ dada por $$\begin{array}{ccc}G:\{\square ,\%,▲\}& \to & \{Suc,Pred\}\\ \square & \to & Suc\\ \%& \to & Suc\\ ▲& \to & Pred\end{array}$$ Claramente $G$ es una familia $\{\square ,\%,▲\}$-indexada de funciones. Notar que $$G=\left\{\right(\square ,Suc),(\%,Suc),(▲,Pred\left)\right\}$$ Se tiene tambien por ejemplo que $G\left(\%\right)=Suc$ por lo cual tambien es cierto que $G\left(\%\right)\left(22\right)=23$, etc.

2. (E2) Si $\Sigma$ es un alfabeto no vacio, la funcion $$\begin{array}{ccc}G:\Sigma & \to & \{f:f\text{es una funcion de}{\Sigma }^{\ast }\text{en}{\Sigma }^{\ast }\}\\ a& \to & d_a\end{array}$$ es una familia $\Sigma$-indexada de funciones. Notar que $$G=\left\{\right(a,d_a):a\in \Sigma \}$$

3. (E3) $\varnothing$ es una flia $\varnothing$-indexada de funciones

Si $G$ es una familia $\Sigma$-indexada de funciones, entonces para $a\in \Sigma$, escribiremos $G_a$ en lugar de $G\left(a\right)$.

1.10.6 Definicion de conjunto $\Sigma$-mixto

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, $$\left\{\right(x,\alpha )\in \omega \times \{▲,!{\}}^{\ast }:\left|\alpha \right|=x\}$$ $$\left\{\right(0,▲▲▲,\epsilon ),(1,\%▲\%,▲▲\left)\right\}$$ son conjuntos $\{▲,\%,!\}$-mixtos. Tambien notese que $\varnothing$ y $\left\{◊\right\}$ son conjuntos $\Sigma$-mixtos, cualesquiera sea el alfabeto $\Sigma$. Por ultimo el conjunto $$\left\{\right(x,\epsilon ,\epsilon ,\epsilon ):x\in \omega \text{y}x\text{es impar}\}$$ es $\varnothing$-mixto (con $n=1$ y $m=3$).

1.10.7 El tipo de un conjunto mixto

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\ne \varnothing$, entonces hay unicos $n,m\in \omega$ tales que $S$ es un conjunto de tipo $(n,m)$. De esta forma, cuando $S\ne \varnothing$ 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 $\varnothing$ 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)$.

1.10.8 Conjuntos rectangulares

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 $\left\{◊\right\}$ es rectangular (es el caso $n=m=0$). Otros ejemplos:

1. - $N\times \{1,2\}\times \{@@,\epsilon \}$ es rectangular (aqui $n=2$ y $m=1$)

2. - $\{!!!,!!\}\times \{@@,\epsilon \}$ es rectangular (aqui $n=0$ y $m=2$)

Tambien notese que $\varnothing =\varnothing \times \varnothing$ por lo cual $\varnothing$ 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.

Proof. Ejercicio.  

Supongamos $\Sigma =\{\#,▲,\%\}$. Notese que podemos usar el lema anterior para probar por ejemplo que los siguientes conjuntos no son rectangulares

1. - $\left\{\right(0,\#\#),(1,\%\%\%\left)\right\}$

2. - $\left\{\right(x,\alpha ):\left|\alpha \right|=x\}$

Dejamos como ejercicio para el lector enunciar un lema analogo al anterior pero que caracterice cuando $S\subseteq {\omega }^2\times {\Sigma }^{\ast 3}$ es rectangular.

1.10.9 Notacion lambda

Usaremos la notacion lambda de Church en la forma que se explica a continuacion. La idea de usar la notacion lambda fue sacada del libro de Bell y Machover . 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.

1. (1) 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{array}{cc}& x,y,z,w,n,m,k,...\\ & x_1,x_2,...\\ & y_1,y_2,...\\ & etc\end{array}$$ Las variables alfabeticas seran seleccionadas de la lista $$\begin{array}{cc}& \alpha ,\beta ,\gamma ,\eta ,...\\ & {\alpha }_1,{\alpha }_2,...\\ & {\beta }_1,{\beta }_2,...\\ & etc\end{array}$$

2. (2) 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$.

3. (3) Otro ejemplo, consideremos la expresion $$\left|\alpha \beta \right|+{\left|\alpha \right|}^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|\alpha \beta \right|+{\left|\alpha \right|}^x$ produce o representa el valor $\left|@@\%\%\%\right|+{\left|@@\right|}^2=9$.

4. (4) Para ciertas valuaciones de sus variables la expresion puede no estar definida. Por ejemplo la expresion $$Pred\left(\left|\alpha \right|\right)$$ no asume valor o no esta definida cuando el valor asignado a $\alpha$ es $\epsilon$. Otro ejemplo, consideremos la expresion $$x/(y-\left|\alpha \right|{)}^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$.

5. (5) 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$.

6. (6) Tambien consideraremos expresiones en las cuales no ocurren variables, es decir ellas representan un valor concreto. Por ejemplo la expresion $$5$$ siempre produce el valor $5$. O la expresion $$17+11$$ siempre produce el valor 28. Tambien la expresion $$1/0$$ no tiene variables y ademas es siempre indefinida. Es decir no representa un valor u objeto.

7. (7) Una expresion $E$ para poder ser utilizada en la notacion lambda relativa a un alfabeto $\Sigma$ debera cumplir alguna de las dos siguientes propiedades

   1. 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$

   2. 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 }$.

8. (8) Por ejemplo la expresion $$x/2$$ no cumple la propiedad dada en (7) 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).

9. (9) Otro ejemplo, si el alfabeto fijado es $\Sigma =\{@,\%\}$, entonces la expresion $${@}^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 expresion nos da la palabra $@@\$\$\$\$\$\$$ la cual no pertenece a ${\Sigma }^{\ast }$ por lo cual no cumple ni (a) ni (b).

10. (10) 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 $$elmenornumeroprimoqueesmayorquex$$ 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: $$eltercersimbolode\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$.

11. (11) Expresiones Booleanas. A las expresiones Booleanas tales como $$x=y+1\text{y}\left|\alpha \right|\le 22$$

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 $\epsilon$. Las expresiones Booleanas pensadas de esta forma podran ser utilizadas en la notacion lambda si es que tambien cumplen con las anteriores condiciones. Otro ejemplo $$11=17$$ es una expresion Booleana que no tiene variables y siempre produce el valor 0.

Expresiones lambdificables con respecto a $\Sigma$

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:

1. (E1) $x/2$ no es lambdificable con respecto a $\Sigma$ cualesquiera sea $\Sigma$

2. (E2) ${@}^x{\$}^y$ es lambdificable con respecto a $\{@,\$\}$ y no es lambdificable con respecto a $\{@,\#,\%\}$

3. (E3) $x=y+1$ es lambdificable con respecto a $\Sigma$ cualesquiera sea $\Sigma$

4. (E4) la expresion $$elmenornumeroprimoqueesmayorque{x}^{\left|\beta \right|}$$ es lambdificable con respecto a $\Sigma$ cualesquiera sea $\Sigma$

5. (E5) la expresion $$5$$ es lambdificable con respecto a $\Sigma$ cualesquiera sea $\Sigma$

6. (E6) la expresion $$Suc\left(x/20\right)$$ es lambdificable con respecto a $\Sigma$ cualesquiera sea $\Sigma$. Notese que esta expresion 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 expresion esta definida o produce un valor cuando le asignamos a $x$ un valor multiplo de $20$. Notese que sin enbargo, la expresion $$\left(x/20\right)+1$$ no es lambdificable con respecto a $\Sigma$ cualesquiera sea $\Sigma$ (por que?).

Definicion de $\lambda x_1...x_n{\alpha }_1...{\alpha }_m\left[E\right]$

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$ (con $n,m\in \omega$) 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:

1. (L1) 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$.

2. (L2) $\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 (7) 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 \}$. Tambien notese que cuando $n=m=0$ la expresion $E$ debera no tener variables y $\lambda x_1...x_n{\alpha }_1...{\alpha }_m\left[E\right]$pasara a ser $\lambda \left[E\right]$. Ademas $\lambda \left[E\right]$ sera la funcion vacia cuando $E$ no produsca o represente un valor y en caso contarrio $\lambda \left[E\right]$ tendra dominio igual a $\left\{♢\right\}$. Algunos ejemplos:

1. (a) Supongamos fijamos el alfabeto $\Sigma =\{@,?,$¡$\}$. Entonces $\lambda x\alpha \left[{\alpha }^{2x}\right]$ es la funcion $$\begin{array}{ccc}\omega \times \{@,?,\text{¡}{\}}^{\ast }& \to & \{@,?,\text{¡}{\}}^{\ast }\\ (x,\alpha )& \to & {\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 =\left\{\%\right\}$, entonces $\lambda x\alpha \left[{\alpha }^{2x}\right]$ denotaria otra funcion, a saber $$\begin{array}{ccc}\omega \times \{\%{\}}^{\ast }& \to & \{\%{\}}^{\ast }\\ (x,\alpha )& \to & {\alpha }^{2x}\end{array}$$

2. (b) Supongamos fijamos el alfabeto $\Sigma =\{@,?,$¡$\}$. Entonces $\lambda x\alpha \left[5\right]$ es la funcion $$\begin{array}{ccc}\omega \times \{@,?,\text{¡}{\}}^{\ast }& \to & \omega \\ (x,\alpha )& \to & 5\end{array}$$

3. (c) Supongamos fijamos el alfabeto $\Sigma =\{\%,!\}$. Entonces $\lambda \alpha \beta \left[\alpha \beta \right]$ es la funcion $$\begin{array}{ccc}\{\%,!{\}}^{\ast }\times \{\%,!{\}}^{\ast }& \to & \{\%,!{\}}^{\ast }\\ (\alpha ,\beta )& \to & \alpha \beta \end{array}$$

   Tambien tenemos que $\lambda \beta \alpha \left[\alpha \beta \right]$ es la funcion $$\begin{array}{ccc}\{\%,!{\}}^{\ast }\times \{\%,!{\}}^{\ast }& \to & \{\%,!{\}}^{\ast }\\ (\beta ,\alpha )& \to & \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](\%,!)=!\%$

4. (d) Independientemente de quien sea $\Sigma$ el alfabeto previamente fijado, tenemos que $\lambda xy[x+y]$ es la funcion $$\begin{array}{ccc}{\omega }^2& \to & \omega \\ (x,y)& \to & x+y\end{array}$$ Tambien $\lambda xyzw[x+w]$ es la funcion $$\begin{array}{ccc}{\omega }^4& \to & \omega \\ (x,y,z,w)& \to & x+w\end{array}$$

5. (e) Supongamos fijamos el alfabeto $\Sigma =\{@,?,$¡$\}$. Entonces por la clausula (L1) tenemos que el dominio de la funcion $\lambda xy\alpha \beta \left[Pred\right(\left|\alpha \right|)+Pred(y\left)\right]$ es $$D=\left\{\right(x,y,\alpha ,\beta )\in {\omega }^2\times {\Sigma }^{\ast 2}:\left|\alpha \right|\ge 1\text{y}y\ge 1\}$$ Es decir que $\lambda xy\alpha \beta \left[Pred\right(\left|\alpha \right|)+Pred(y\left)\right]$ es la funcion $$\begin{array}{ccc}D& \to & \omega \\ (x,y,\alpha ,\beta )& \to & Pred\left(\left|\alpha \right|\right)+Pred\left(y\right)\end{array}$$

6. (f) Atentos a (11) de mas arriba, la funcion $\lambda xy[x=y]$ es el predicado $$\begin{array}{ccc}\omega \times \omega & \to & \omega \\ (x,y)& \to & \{\begin{array}{c}1\text{si}x=y\\ 0\text{si}x\ne y\end{array}\end{array}$$ y $\lambda x\alpha \left[Pred\right(x)=\left|\alpha \right|]$ es el predicado $$\begin{array}{ccc}N\times {\Sigma }^{\ast }& \to & \omega \\ (x,\alpha )& \to & \{\begin{array}{c}1\text{si}Pred\left(x\right)=\left|\alpha \right|\\ 0\text{si}Pred\left(x\right)\ne \left|\alpha \right|\end{array}\end{array}$$ Tambien $\lambda \alpha \beta [\alpha =\beta ]$ es el predicado $$\begin{array}{ccc}{\Sigma }^{\ast }\times {\Sigma }^{\ast }& \to & \omega \\ (\alpha ,\beta )& \to & \{\begin{array}{c}1\text{si}\alpha =\beta \\ 0\text{si}\alpha \ne \beta \end{array}\end{array}$$

7. (g) 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[\right(\overrightarrow{x},\overrightarrow{\alpha })\in S]$

8. (h) 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.

9. (i) La funcion $\lambda x\left[Suc\right(x/20\left)\right]$ es la siguiente funcion: $$\begin{array}{ccc}\{x\in \omega :20\text{divide a}x\}& \to & \omega \\ x& \to & x+1\end{array}$$

10. (j) La funcion $\lambda \left[5\right]$ es la funcion $$\begin{array}{ccc}\left\{◊\right\}& \to & \omega \\ ◊& \to & 5\end{array}$$

11. (k) La funcion $\lambda \left[1/0\right]$ es la funcion vacia, es decir $\lambda \left[1/0\right]=\varnothing$

12. (l) La funcion $\lambda [11=17]$ es la funcion $$\begin{array}{ccc}\left\{◊\right\}& \to & \omega \\ ◊& \to & 0\end{array}$$