3.1 Funciones Σ$\Sigma$-efectivamente computables

Una funcion Σ$\Sigma$-mixta f:Df⊆ωn×Σ∗m→ω$f:D_f\subseteq {\omega }^n\times {\Sigma }^{\ast m}\to \omega$ sera llamada Σ$\Sigma$-efectivamente computable si hay un procedimiento efectivo P tal que

1. (1) El conjunto de datos de entrada de P es ωn×Σ∗m

2. (2) El conjunto de datos de salida esta contenido en ω.

3. (3) Si (→x,→α)∈Df, entonces P se detiene partiendo de (→x,→α), dando como dato de salida f(→x,→α).

4. (4) Si (→x,→α)∈(ωn×Σ∗m)−Df, entonces P no se detiene partiendo desde (→x,→α)

Analogamente una funcion Σ-mixta f:Df⊆ωn×Σ∗m→Σ∗ sera llamada Σ-efectivamente computable si hay un procedimiento efectivo P tal que

1. (1) El conjunto de datos de entrada de P es ωn×Σ∗m

2. (2) El conjunto de datos de salida esta contenido en Σ∗.

3. (3) Si (→x,→α)∈Df, entonces P se detiene partiendo de (→x,→α), dando como dato de salida f(→x,→α).

4. (4) Si (→x,→α)∈(ωn×Σ∗m)−Df, entonces P no se detiene partiendo desde (→x,→α)

En ambos casos descriptos arriba diremos que P computa a la funcion f.

Notese que esta definicion para el caso f=∅ tiene a priori cierta ambiguedad ya que cualesquiera sean n,m∈ω y O∈{ω,Σ∗} tenemos que ∅:∅⊆ωn×Σ∗m→O ya que D∅=∅ y I∅=∅. De todas maneras, cualesquiera sean los n,m y O elejidos, siempre hay un procedimiento efectivo que computa a f=∅, i.e. un procedimiento que nunca se detiene, cualesquiera sea el dato de entrada de ωn×Σ∗m. Es decir que la funcion ∅ es Σ-efectivamente computable cualesquiera sea el alfabeto Σ. Cabe destacar que para el caso de una funcion f≠∅, nuestra definicion es inambigua ya que hay unicos n,m∈ω y O∈{ω,Σ∗} tales que f:Df⊆ωn×Σ∗m→O.

Veamos algunos ejemplos:

1. (E1) La funcion λxy[x+y] es Σ-efectivamente computable, cualquiera sea el alfabeto Σ ya que el procedimiento enseñado en la escuela primaria para sumar numeros en notacion decimal es efectivo y computa esta funcion. Tambien las funciones λxy[x.y] y λxy[xy] son Σ-efectivamente computables via los procedimientos clasicos enseñados en la escuela primaria.

2. (E2) La funcion C1,23 es Σ-efectivamente computable ya que el siguiente procedimiento P con conjunto de datos de entrada ω×Σ∗2 la computa:

   1. - Independientemente de quien sea el dato de entrada (x1,α1,α2), terminar y dar como salida el numero 3

3. (E3) La funcion p2,33 es Σ-efectivamente computable ya que el siguiente procedimiento con conjunto de datos de entrada ω2×Σ∗3 la computa:

   1. - Dado el dato de entrada (x1,x2,α1,α2,α3), terminar y dar como salida la palabra α1

4. (E4) Pred es Σ-efectivamente computable. Para realizar el procedimiento efectivo que compute a Pred necesitaremos el procedimiento de la escuela primaria que dado un numero no nulo x, expresado en notacion decimal, calcula el numero x−1, en notacion decimal. Llamemos P−1 a dicho procedimiento. El siguiente procedimiento (con conjunto de datos de entrada igual a ω) computa a Pred:

   Dado como dato de entrada un elemento x∈ω, realizar lo siguiente:

   Etapa 1

   Si x=0, entonces ir a Etapa 3, en caso contrario ir a Etapa 2.

   Etapa 2

   Correr P−1 con dato de entrada x obteniendo y como dato de salida. Detenerse y dar y como dato de salida.

   Etapa 3

   Si x=0, entonces ir a Etapa 1.

   Como puede notarse el procedimiento anterior es efectivo ya que debemos entender que en la Etapa 2, los sucesivos pasos efectuados al correr P−1 son todos simples y efectivamente realizables ya que P−1 es efectivo. Por supuesto si uno quisiera ser mas prolijo, deberia reemplazar la Etapa 2 por las distintas instrucciones de P−1, referidas a x.

5. (E5) El predicado λxy[x<y] es Σ-efectivamente computable cualquiera sea el alfabeto Σ. Describiremos con palabras un procedimiento que computa a λxy[x<y]. Su conjunto de datos de entrada es ω2. Dado un par (x,y)∈ω2, el procedimiento primero compara las longitudes de las palabras que en notacion decimal representan a x y y. Por supuesto esto lo hace borrando de a un simbolo y viendo si alguna se termina primero. Si resultan de distinta longitud, es facil darse cuenta como sigue. En caso de que las palabras resulten de igual longitud, entonces se hace el procedimiento clasico de ir comparando digitos de izquierda a derecha.

6. (E6) Veamos que la funcion λα[|α|] es Σ-efectivamente computable. Como en los lenguajes de programacion, usaremos variables y asignaciones para diseñar el procedimiento. Ademas llamemos P+1 a el procedimiento de la escuela primaria que dado un numero no nulo x, expresado en notacion decimal, calcula el numero x+1, en notacion decimal. Sea P el siguiente procedimiento.

   Dado como dato de entrada un elemento α∈Σ∗, realizar lo siguiente:

   Etapa 1: Hacer las siguientes asignaciones A←αB←0 e ir a Etapa 2.

   Etapa 2: Si A no es ε, ir a Etapa 3. En caso contrario terminar y dar como salida B.

   Etapa 3: Correr P+1 con dato de entrada igual al contenido de B, obteniendo y como salida. Hacer la asignacion A←resultado de remover el 1er simbolo de AB←y e ir a Etapa 2.

   Dejamos como ejercicio convenserse que el uso de asignaciones puede realizarse usando solo lapiz y papel. Imagine como lo haria en este ejemplo y corrobore que dicho procedimiento es efectivo y ademas computa a λα[|α|]

7. (E7) Si ≤ es el orden total sobre Σ={▴,%} dado por ▴<%, entonces veremos que la funcion s≤ es Σ-efectivamente computable. Primero es importante notar que cualquiera sea α∈Σ∗, se cumple s≤(ε)=▴s≤(α▴)=α%s≤(α%)=s≤(α)▴ Usaremos estas ecuaciones para dar un procedimiento efectivo (con conjunto de datos de entrada igual a Σ∗) que compute a s≤.

   Etapa 1: Dado el dato de entrada α∈Σ∗, hacer las siguientes asignaciones A←αB←εF←▴ e ir a Etapa 2.

   Etapa 2: Si A comiensa con ▴, entonces hacer las siguientes asignaciones A←resultado de remover el 1er simbolo de AF←B%B←B▴ e ir a la Etapa 2. En caso contrario ir a la Etapa 3.

   Etapa 3: Si A comiensa con %, entonces hacer las siguientes asignaciones A←resultado de remover el 1er simbolo de AF←F▴B←B% e ir a la Etapa 2. En caso contrario ir a la Etapa 4.

   Etapa 4: Dar como salida F

8. (E8) Usando que s≤ es Σ-efectivamente computable podemos ver que ∗≤:ω→Σ∗ tambien lo es ya que ∗≤ es definida con las ecuaciones ∗≤(0)=ε∗≤(x+1)=s≤(∗≤(x))

Dejamos como ejercico para el lector diseñar procedimientos efectivos que computen las funciones:

1. - λxy[x divide a y]

2. - λx[pr(x)]

3. - λix[(x)i]

(Utilice en el diseño de los respectivos procedimientos a los procedimientos que computan las funciones λxy[x+y], λxy[x.y] y λxy[xy])

Nota Importante: en lo que sigue muchas veces daremos procedimientos que son efectivos en terminos de otros que ya se han dado, es decir daremos un procedimiento que en principio no es claro que sea efectivo pero el cual se volveria efectivo si reemplazaramos ciertas instrucciones por la manera efectiva de simularlas. Para hacer mas dinamico el discurso no distinguiremos entre este tipo de procedimientos (efectivisables) y los efectivos propiamente dichos.

3.1.1 Constructores que preservan computabilidad efectiva

Hay muchos procesos constructivos que nos sirven para definir o construir una funcion en terminos de otras funciones dadas. Un ejemplo de esto es la composicion de funciones, la cual dadas dos funciones f,g nos permite construir su composicion, a saber f∘g. Otro ejemplo es el contructor de predicados que dados dos predicados Σ-mixtos P:S⊆ωn×Σ∗m→{0,1} y Q:S⊆ωn×Σ∗m→{0,1}, con el mismo dominio, nos define el predicado (P∨Q):S→ω(→x,→α)→{1si P(→x,→α)=1 o Q(→x,→α)=10caso contrario Otro constructor muy importante que utilizaremos mucho es aquel que a partir de funciones fi:Dfi→O, i=1,...,k, tales que Dfi∩Dfj=∅ para i≠j, nos da la nueva funcion f1∪...∪fk, la cual cumple Df1∪...∪Dfk→Oe→{f1(e)si e∈Df1⋮⋮fk(e)si e∈Dfk

3.1.2 Composicion

Dadas funciones Σ-mixtas f,f1,...,fr, con r≥1, diremos que la funcion f∘[f1,...,fr] es obtenida por composicion a partir de las funciones f,f1,...,fr. Para probar que la composicion preserva la computabilidad efectiva necesitaremos el siguiente lema.

Proof. Notese que f≠∅ y [f1,...,fr]≠∅ (por que?). Ya que f≠∅ tenemos que hay unicos n,m∈ω y s∈{#,∗} tales que f es de tipo (n,m,s). Ya que f∘[f1,...,fr]≠∅ y I[f1,...,fr]⊆If1×...×Ifr, tenemos que

1. - r=n+m

2. - Ifi⊆ω, para cada i=1,...,n

3. - Ifi⊆Σ∗, para cada i=n+1,...,n+m

Ya que [f1,...,fr]≠∅ tenemos que D[f1,...,fr]=⋂ri=1Dfi≠∅, por lo cual los conjuntos Df1,...,Dfn+m deberan ser todos de un mismo tipo, digamos de tipo (k,l). Es decir que fi es de tipo (k,l,#), para cada i=1,...,n y fi es de tipo (k,l,∗), para cada i=n+1,...,n+m.

Las ultimas observaciones del lema son directas de las definiciones de [f1,...,fn+m] y de composicion de funciones  

Ahora si podemos probar facilmente que se preserva la computabilidad efectiva cuando componemos

Proof. Si f∘[f1,...,fr]=∅, entonces claramente es Σ-efectivamente computable. Supongamos entonces que f∘[f1,...,fr]≠∅. Por el lema anterior hay n,m,k,l∈ω y s∈{#,∗} tales que

1. - r=n+m

2. - f es de tipo (n,m,s)

3. - fi es de tipo (k,l,#), para cada i=1,...,n

4. - fi es de tipo (k,l,∗), para cada i=n+1,...,n+m

Sean P,P1,...,Pn+m procedimientos efectivos los cuales computen las funciones f,f1,...,fn+m, respectivamente. Usando estos procedimientos es facil definir un procedimiento efectivo el cual compute a f∘[f1,...,fn+m].  

3.1.3 Lema de division por casos para funciones Σ-efectivamente computables

Recordemos que si fi:Dfi→O, i=1,...,k, son funciones tales que Dfi∩Dfj=∅ para i≠j, entonces f1∪...∪fk es la funcion Df1∪...∪Dfk→Oe→{f1(e)si e∈Df1⋮⋮fk(e)si e∈Dfk

Proof. Haremos el caso O=Σ∗ y k=2. Sean P1 y P2 procedimientos efectivos que computen a f1 y f2, respectivamente. Sea P el procedimiento efectivo siguiente:

- Conjunto de datos de entrada de P igual a ωn×Σ∗m

- Conjunto de datos de salida de P contenido en Σ∗

- Funcionamiento:

Etapa 1

Hacer T=1

Etapa 2

Correr el procedimiento P1 una cantidad T de pasos. En caso de que termine guardar la salida en la variable X e ir a Etapa 5. Si no termina ir a Etapa 3.

Etapa 3

Correr el procedimiento P2 una cantidad T de pasos. En caso de que termine guardar la salida en la variable X e ir a Etapa 6. Si no termina ir a Etapa 4.

Etapa 4

Hacer T=T+1 e ir a Etapa 2

Etapa 5

Dar como salida el contenido de X y terminar.

Dejamos al lector corroborar que el procedimiento P computa a la funcion f1∪f2.