Sea Σ un alfabeto finito. Dados n,m∈ω, usaremos ωn×Σ∗m para abreviar la expresion n vecesω×...×ω×m vecesΣ∗×...×Σ∗ Por ejemplo, ω3×Σ∗4 sera una forma abreviada de escribir ω×ω×ω×Σ∗×Σ∗×Σ∗×Σ∗. Debe quedar claro que estamos haciendo cierto abuso notacional ya que en principio si no hacemos esta convencion notacional, ω3×Σ∗4 denota un conjunto de pares y ω×ω×ω×Σ∗×Σ∗×Σ∗×Σ∗ es un conjunto de 7-uplas.
Notese que:
- Cuando n=m=0, tenemos que ωn×Σ∗m denota el conjunto {◊}
- Si m=0, entonces ωn×Σ∗m denota el conjunto ωn
- Si n=0, entonces ωn×Σ∗m denota el conjunto Σ∗m
- Cuando Σ=∅, tenemos que Σ∗={ε}. O sea que por ejemplo ωn×Σ∗5={(x1,...,xn,ε,ε,ε,ε,ε):x1,...,xn∈ω}
Es decir que tenemos que tener cuidado cuando leemos esta notacion y no caer en la confucion de interpretarla mal. A manera de ultimo ejemplo,
Con esta convencion notacional, un elemento generico de ωn×Σ∗m es una (n+m)-upla de la forma (x1,...,xn,α1,...,αm). Para abreviar, escribiremos (→x,→α) en lugar de (x1,...,xn,α1,...,αm).
Sea Σ un alfabeto finito. Dada una funcion f, diremos que f es Σ-mixta si cumple las siguientes propiedades
(M1) Existen n,m≥0, tales que Df⊆ωn×Σ∗m
(M2) Ya sea If⊆ω o If⊆Σ∗
Algunos ejemplos:
E1 Sea Σ={□,%,▲}. La funcion f:ω×{□,%,▲}∗→ω(x,α)→x+|α| es Σ-mixta ya que se cumple (M1) con n=m=1 y (M2). Notese que f no es {□,%}-mixta ya que no cumple (M1) respecto del alfabeto {□,%}. Sin envargo note que f es {□,%,▲,@}-mixta
E2 La funcion ω4→ω(x,y,z,w)→x+y es Σ-mixta cualesquiera sea el alfabeto Σ
E3 Sea Σ={□,@}. La funcion {□□□,@@}→ωα→|α|
es Σ-mixta ya que se cumple (M1) (con n=0 y m=1) y (M2)
E4 Supongamos Σ=∅. Tenemos entonces que Σ∗={ε}. Por ejemplo D→ω(x,ε,ε,ε)→x2 donde D={(x,ε,ε,ε):x es impar}, es Σ-mixta (con n=1 y m=3 en (M1)). Tambien notese que {(ε,ε)}→{ε}(ε,ε)→ε es Σ-mixta (con n=0 y m=2 en (M1)).
Dejamos al lector la facil prueba del siguiente resultado basico.
1.7. Supongamos Σ⊆Γ son alfabetos finitos. Entonces si f es una funcion Σ-mixta, f es Γ-mixta
Una funcion Σ-mixta f es Σ-total cuando haya n,m∈ω tales que Df=ωn×Σ∗m. El lema anterior nos dice que si Σ⊆Γ, entonces toda funcion Σ-mixta es Γ-mixta. Sin envargo una funcion puede ser Σ-total y no ser Γ-total, cuando Σ⊆Γ. Por ejemplo tomemos Σ={□,%,▲} y Γ={□,%,▲,!}, y consideremos la funcion f:ω×Σ∗→ω(x,α)→x+|α| Es claro que f es Σ-mixta y Σ-total. Tambien es Γ-mixta ya que Df⊆ω×Γ∗ y If⊆ω, por lo cual cumple (M1) y (M2). Sin envargo f no es Γ-total ya que Df no es igual a ωn×Γ∗m, cualesquiera sean n y m.
Como hemos visto recien, una funcion f puede ser Σ-mixta y Γ-mixta para dos alfabetos distintos Σ y Γ e incluso es facil construir un ejemplo en el cual Σ y Γ sean incomparables como conjuntos, es decir que ninguno incluya al otro. Dejamos al lector convencerse de que si f es una funcion que es Σ-mixta para algun alfabeto Σ, entonces hay un alfabeto Σ0 el cual es el menor de todos los alfabetos respecto de los cuales f es mixta, es decir Σ0 cumple que f es Σ0-mixta y si Γ es tal que f es Γ-mixta, entonces Σ0⊆Γ.
A continuacion daremos algunas funciones Σ-mixtas basicas las cuales seran frecuentemente usadas.
La funcion sucesor es definida por Suc:ω→ωn→n+1 La funcion predecesor es definida por Pred:N→ωn→n−1
Sea Σ un alfabeto no vacio. Para cada a∈Σ, definamos da:Σ∗→Σ∗α→αa La funcion da es llamada la funcion derecha sub a, respecto del alfabeto Σ.
Sea Σ un alfabeto. Para n,m,i∈ω tales que 1≤i≤n, definamos pn,mi:ωn×Σ∗m→ω(→x,→α)→xi Para n,m,i∈ω tales que n+1≤i≤n+m, definamos pn,mi:ωn×Σ∗m→Σ∗(→x,→α)→αi−n Las funciones pn,mi son llamadas proyecciones. La funcion pn,mi es llamada la proyeccion n,m,i, respecto del alfabeto Σ. Notese que esta definicion requiere que n+m≥1 ya que i debe cumplir 1≤i≤n+m.
Sea Σ un alfabeto. Para n,m,k∈ω, y α∈Σ∗, definamos Cn,mk:ωn×Σ∗m→ω(→x,→α)→k Cn,mα:ωn×Σ∗m→Σ∗(→x,→α)→α Notese que C0,0k:{◊}→{k} y que C0,0α:{◊}→{α}.
Definamos pr:N→ωn→n-esimo numero primo Notese que pr(1)=2, pr(2)=3, pr(3)=5, etc.
Dada una funcion Σ-mixta f, si n,m∈ω son tales que Df⊆ωn×Σ∗m y ademas If⊆ω, entonces diremos que f es una funcion de tipo (n,m,#). Similarmente si n,m∈ω son tales que Df⊆ωn×Σ∗m y ademas If⊆Σ∗, entonces diremos que f es una funcion de tipo (n,m,∗). Notese que si f≠∅, entonces hay unicos n,m∈ω y s∈{#,∗} tales que f es una funcion de tipo (n,m,s). Sin envargo ∅ es una funcion de tipo (n,m,s) cualesquiera sean n,m∈ω y s∈{#,∗}. De esta forma, cuando f≠∅ hablaremos de "el tipo de f" para refererirnos a esta unica terna (n,m,s). Notese que Suc es de tipo (1,0,#) y da es de tipo (0,1,∗).
Tambien notese que la relacion "f es una funcion de tipo (n,m,s)" no depende del alfabeto Σ (que significa esto?).
Supongamos que k,l,n,m∈ω y que F:DF⊆ωk×Σ∗l→ωn×Σ∗m. Supongamos ademas que n+m≥1. Entonces denotaremos con F(i) a la funcion pn,mi∘F. Notar que F(i):DF⊆ωk×Σ∗l→ω, para cada i=1,...,nF(i):DF⊆ωk×Σ∗l→Σ∗, para cada i=n+1,...,n+m Por lo cual cada una de las funciones F(i) son Σ-mixtas. Ademas notese que F=[F(1),...,F(n+m)]
Un predicado Σ-mixto es una funcion f la cual es Σ-mixta y ademas cumple que If⊆{0,1}. Por ejemplo ω×ω→ω(x,y)→{1 si x=y0 si x≠y {1,2,3,4,5}×Σ∗→ω(x,α)→{1 si x=|α|0 si x≠|α|
Dados predicados P:S⊆ωn×Σ∗m→{0,1} y Q:S⊆ωn×Σ∗m→{0,1}, con el mismo dominio, definamos nuevos predicados (P∨Q), (P∧Q) y ¬P de la siguiente manera (P∨Q):S→ω(→x,→α)→{1si P(→x,→α)=1 o Q(→x,→α)=10caso contrario (P∧Q):S→ω(→x,→α)→{1si P(→x,→α)=1 y Q(→x,→α)=10caso contrario ¬P:S→ω(→x,→α)→{1si P(→x,→α)=00si P(→x,→α)=1
Dado un alfabeto Σ, una familia Σ-indexada de funciones sera una funcion G tal que DG=Σ y para cada a∈DG se tiene que G(a) es una funcion. Algunos ejemplos:
E1 Sea G dada por G:{□,%,▲}→{Suc,Pred}□→Suc%→Suc▲→Pred Claramente G es una familia {□,%,▲}-indexada de funciones. Notar que G={(□,Suc),(%,Suc),(▲,Pred)} Se tiene tambien por ejemplo que G(%)=Suc por lo cual tambien es cierto que G(%)(22)=23, etc.
E2 Si Σ es un alfabeto no vacio, la funcion G:Σ→{f:f es una funcion de Σ∗ en Σ∗}a→da es una familia Σ-indexada de funciones. Notar que G={(a,da):a∈Σ}
E3 ∅ es una flia ∅-indexada de funciones
Si G es una familia Σ-indexada de funciones, entonces para a∈Σ, escribiremos Ga en lugar de G(a).
Un conjunto S es llamado Σ-mixto si hay n,m∈ω tales que S⊆ωn×Σ∗m. Por ejemplo, {(x,α)∈ω×{▲,!}∗:|α|=x} {(0,▲▲▲,ε),(1,%▲%,▲▲)} son conjuntos {▲,%,!}-mixtos. Tambien notese que ∅ y {◊} son conjuntos Σ-mixtos, cualesquiera sea el alfabeto Σ. Por ultimo el conjunto {(x,ε,ε,ε):x∈ω y x es impar} es ∅-mixto (con n=1 y m=3).
Dado un conjunto Σ-mixto S, si n,m∈ω son tales que S⊆ωn×Σ∗m, entonces diremos que S es un conjunto de tipo (n,m). Notese que si S≠∅, entonces hay unicos n,m∈ω tales que S es un conjunto de tipo (n,m). De esta forma, cuando S≠∅ 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 ∅ es un conjunto de tipo (n,m) cualesquiera sean n,m∈ω, por lo cual cuando hablemos de EL tipo de un comjunto deberemos estar seguros de que dicho conjunto es no vacio.
Notese que ω es de tipo (1,0) y Σ∗ es de tipo (0,1).
Un conjunto Σ-mixto S es llamado rectangular si es de la forma S1×...×Sn×L1×...×Lm, con cada Si⊆ω y cada Li⊆Σ∗. Notar que todo subconjunto de ω es rectangular (es el caso n=1 y m=0). Tambien {◊} es rectangular (es el caso n=m=0). Otros ejemplos:
- N×{1,2}×{@@,ε} es rectangular (aqui n=2 y m=1)
- {!!!,!!}×{@@,ε} es rectangular (aqui n=0 y m=2)
Tambien notese que ∅=∅×∅ por lo cual ∅ 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⊆ω×Σ∗. Entonces S es rectangular si y solo si se cumple la siguiente propiedad:
(R) Si (x,α),(y,β)∈S, entonces (x,β)∈S
Proof. Ejercicio.
Supongamos Σ={#,▲,%}. Notese que podemos usar el lema anterior para probar por ejemplo que los siguientes conjuntos no son rectangulares
- {(0,##),(1,%%%)}
- {(x,α):|α|=x}
Dejamos como ejercicio para el lector enunciar un lema analogo al anterior pero que caracterice cuando S⊆ω2×Σ∗3 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
(1) Solo utilizaremos expresiones que involucran variables numericas, las cuales se valuaran en numeros de ω, y variables alfabeticas, las cuales se valuaran en palabras del alfabeto previamente fijado. Las variables numericas seran seleccionadas de la lista x,y,z,w,n,m,k,...x1,x2,...y1,y2,...etc Las variables alfabeticas seran seleccionadas de la lista α,β,γ,η,...α1,α2,...β1,β2,...etc
(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) Otro ejemplo, consideremos la expresion |αβ|+|α|x la cual tiene una variable numerica x y dos variables alfabeticas α y β. Supongamos ademas que el alfabeto previamente fijado es {@,%}. Si le asignamos a x el valor 2, a α el valor @@ y a β el valor %%%, entonces la expresion |αβ|+|α|x produce o representa el valor |@@%%%|+|@@|2=9.
(4) Para ciertas valuaciones de sus variables la expresion puede no estar definida. Por ejemplo la expresion Pred(|α|) no asume valor o no esta definida cuando el valor asignado a α es ε. Otro ejemplo, consideremos la expresion x/(y−|α|)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 α.
(5) En los ejemplos anteriores las expresiones producen valores numericos pero tambien trabajaremos con expresiones que producen valores alfabeticos. Por ejemplo la expresion βy tiene una variable numerica, y, una variable alfabetica, β, y una vez valuadas estas variables produce un valor alfabetico, a saber el resultado de elevar el valor asignado a la variable β, a el valor asignado a y.
(6) Una expresion E para poder ser utilizada en la notacion lambda relativa a un alfabeto Σ debera cumplir alguna de las dos siguientes propiedades
los valores que asuma E cuando hayan sido asignados valores de ω a sus variables numericas y valores de Σ∗ a sus variables alfabeticas deberan ser siempre elementos de ω
los valores que asuma E cuando hayan sido asignados valores de ω a sus variables numericas y valores de Σ∗ a sus variables alfabeticas deberan ser siempre elementos de Σ∗.
(7) Por ejemplo la expresion x/2 no cumple la propiedad dada en (6) ya que para ciertos valores de ω asignados a la variable x, la expresion da valores numericos que se salen de ω por lo cual no cumple ni (a) ni (b).
(8) Otro ejemplo, si el alfabeto fijado es Σ={@,%}, 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 Σ∗ por lo cual no cumple ni (a) ni (b).
(9) 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 el menor numero primo que es mayor que x Es claro que esta expresion para cada valor de ω asignado a la variable x produce o representa un valor concreto de ω. Otro ejemplo: el tercer simbolo de α notese que esta expresion, una ves fijado un alfabeto Σ, estara definida o producira un valor solo cuando le asignamos a α una palabra de Σ∗ de longitud mayor o igual a 3.
(10) Expresiones Booleanas. A las expresiones Booleanas tales como x=y+1 y |α|≤22
las pensaremos que asumen valores del conjunto {0,1}⊆ω. 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 α la palabra ε. Las expresiones Booleanas pensadas de esta forma podran ser utilizadas en la notacion lambda si es que tambien cumplen con las anteriores condiciones.
(11) 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 Σ a las expresiones que cumplan las caracteristicas dadas anteriormente las llamaremos lambdificables con respecto a Σ. 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:
(E1) x/2 no es lambdificable con respecto a Σ cualesquiera sea Σ
(E2) @x$y es lambdificable con respecto a {@,$} y no es lambdificable con respecto a {@,#,%}
(E3) x=y+1 es lambdificable con respecto a Σ cualesquiera sea Σ
(E4) la expresion el menor numero primo que es mayor que x|β| es lambdificable con respecto a Σ cualesquiera sea Σ
(E5) la expresion 5 es lambdificable con respecto a Σ cualesquiera sea Σ
Supongamos ya hemos fijado un alfabeto finito Σ y supongamos E es una expresion la cual es lambdificable con respecto a Σ. Sea x1,...,xn,α1,...,αm una lista de variables todas distintas tal que las variables numericas que ocurren en E estan todas contenidas en la lista x1,...,xn y las variables alfabeticas que ocurren en E estan en la lista α1,...,αm (puede suceder que haya variables de la lista x1,...,xn,α1,...,αm las cuales no ocurran en E). Entonces λx1...xnα1...αm[E] denotara la funcion definida por:
(L1) El dominio de λx1...xnα1...αm[E] es el conjunto de las (n+m)-uplas (k1,...,kn,β1,...,βm)∈ωn×Σ∗m tales que E esta definida cuando le asignamos a cada xi el valor ki y a cada αi el valor βi.
(L2) λx1...xnα1...αm[E](k1,...,kn,β1,...,βm)= valor que asume o representa E cuando le asignamos a cada xi el valor ki y a cada αi el valor βi.
Notese que por tener E la propiedad (6) de mas arriba, la funcion λx1...xnα1...αm[E] es Σ-mixta de tipo (n,m,s) para algun s∈{#,∗}. Algunos ejemplos:
(a) Supongamos fijamos el alfabeto Σ={@,?,¡}. Entonces λxα[α2x] es la funcion ω×{@,?,¡}∗→{@,?,¡}∗(x,α)→α2x Aqui el lector puede notar la dependencia de la notacion lambda respecto del alfabeto fijado. Si en lugar de fijar Σ={@,?,¡} hubieramos fijado Σ={%}, entonces λxα[α2x] denotaria otra funcion, a saber ω×{%}∗→{%}∗(x,α)→α2x
(b) Supongamos fijamos el alfabeto Σ={@,?,¡}. Entonces λxα[5] es la funcion ω×{@,?,¡}∗→ω(x,y,z,α)→5
(c) Supongamos fijamos el alfabeto Σ={%,!}. Entonces λαβ[αβ] es la funcion {%,!}∗×{%,!}∗→{%,!}∗(α,β)→αβ
Tambien tenemos que λβα[αβ] es la funcion {%,!}∗×{%,!}∗→{%,!}∗(β,α)→αβ Notese que estas funciones son distintas. Por ejemplo λαβ[αβ](%,!)=%! y λβα[αβ](%,!)=!%
(d) Independientemente de quien sea Σ el alfabeto previamente fijado, tenemos que λxy[x+y] es la funcion ω2→ω(x,y)→x+y Tambien λxyzw[x+w] es la funcion ω4→ω(x,y,z,w)→x+w
(e) Supongamos fijamos el alfabeto Σ={@,?,¡}. Entonces por la clausula (L1) tenemos que el dominio de la funcion λxyαβ[Pred(|α|)+Pred(y)] es D={(x,y,α,β)∈ω2×Σ∗2:|α|≥1 y y≥1} Es decir que λxyαβ[Pred(|α|)+Pred(y)] es la funcion D→ω(x,y,α,β)→Pred(|α|)+Pred(y)
(f) Atentos a (10) de mas arriba, la funcion λxy[x=y] es el predicado ω×ω→ω(x,y)→{1 si x=y0 si x≠y y λxα[Pred(x)=|α|] es el predicado N×Σ∗→ω(x,α)→{1 si Pred(x)=|α|0 si Pred(x)≠|α| Tambien λαβ[α=β] es el predicado Σ∗×Σ∗→ω(α,β)→{1 si α=β0 si α≠β
(g) Notar que para S⊆ωn×Σ∗m se tiene que χωn×Σ∗mS=λx1...xnα1...αm[(→x,→α)∈S]
(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 λ no tenga variables alfabeticas, la funcion representada no depende del alfabeto
Un par de ejemplos sutiles
(a) La expresion Suc no es lambdificable respecto de cualquier alfabeto Σ. 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 ω ni tampoco una palabra (es una funcion!)
(b) La expresion Suc+(|β|+1) es lambdificable con respecto a Σ cualesquiera sea Σ. Por ejemplo λxβ[Suc+(|β|+1)] es la funcion ∅, ya que la expresion Suc+(|β|+1) cualesquiera sean los valores de x y β no esta definida.