3.1 Funciones \(\Sigma\)-efectivamente computables

Una funcion \(\Sigma\)-mixta \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) sera llamada \(\Sigma\)-efectivamente computable si hay un procedimiento efectivo \(\mathbb{P}\) tal que

1. adhocprefix(1)adhocsufix El conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega^{n}\times\Sigma^{\ast m}\)

2. adhocprefix(2)adhocsufix El conjunto de datos de salida esta contenido en \(\omega\).

3. adhocprefix(3)adhocsufix Si \((\vec{x},\vec{\alpha})\in D_{f}\), entonces \(\mathbb{P}\) se detiene partiendo de \((\vec{x},\vec{\alpha})\), dando como dato de salida \(f(\vec{x},\vec{\alpha})\).

4. adhocprefix(4)adhocsufix Si \((\vec{x},\vec{\alpha})\in(\omega^{n}\times\Sigma^{\ast m})-D_{f}\), entonces \(\mathbb{P}\) no se detiene partiendo desde \((\vec{x},\vec{\alpha})\)

Analogamente una funcion \(\Sigma\)-mixta \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) sera llamada \(\Sigma\)-efectivamente computable si hay un procedimiento efectivo \(\mathbb{P}\) tal que

1. adhocprefix(1)adhocsufix El conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega^{n}\times\Sigma^{\ast m}\)

2. adhocprefix(2)adhocsufix El conjunto de datos de salida esta contenido en \(\Sigma^{\ast}\).

3. adhocprefix(3)adhocsufix Si \((\vec{x},\vec{\alpha})\in D_{f}\), entonces \(\mathbb{P}\) se detiene partiendo de \((\vec{x},\vec{\alpha})\), dando como dato de salida \(f(\vec{x},\vec{\alpha})\).

4. adhocprefix(4)adhocsufix Si \((\vec{x},\vec{\alpha})\in(\omega^{n}\times\Sigma^{\ast m})-D_{f}\), entonces \(\mathbb{P}\) no se detiene partiendo desde \((\vec{x},\vec{\alpha})\)

En ambos casos descriptos arriba diremos que \(\mathbb{P}\) computa a la funcion \(f\).

Notese que esta definicion para el caso \(f=\emptyset\) tiene a priori cierta ambiguedad ya que cualesquiera sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\) tenemos que \(\emptyset:\emptyset\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) ya que \(D_{\emptyset}=\emptyset\) y \(I_{\emptyset}=\emptyset\). De todas maneras, cualesquiera sean los \(n,m\) y \(O\) elejidos, siempre hay un procedimiento efectivo que computa a \(f=\emptyset\), i.e. un procedimiento que nunca se detiene, cualesquiera sea el dato de entrada de \(\omega^{n}\times\Sigma^{\ast m}\). Es decir que la funcion \(\emptyset\) es \(\Sigma\)-efectivamente computable cualesquiera sea el alfabeto \(\Sigma\). Cabe destacar que para el caso de una funcion \(f\neq\emptyset\), nuestra definicion es inambigua ya que hay unicos \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\) tales que \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\).

Veamos algunos ejemplos:

1. adhocprefix\((\)E\(1)\)adhocsufix La funcion \(\lambda xy\left[x+y\right]\) es \(\Sigma\)-efectivamente computable, cualquiera sea el alfabeto \(\Sigma\) 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 \(\lambda xy\left[x.y\right]\) y \(\lambda xy\left[x^{y}\right]\) son \(\Sigma\)-efectivamente computables via los procedimientos clasicos enseñados en la escuela primaria.

2. adhocprefix\((\)E\(2)\)adhocsufix La funcion \(C_{3}^{1,2}\) es \(\Sigma\)-efectivamente computable ya que el siguiente procedimiento \(\mathbb{P}\) con conjunto de datos de entrada \(\omega\times\Sigma^{\ast2}\) la computa:

   1. adhocprefix-adhocsufix Independientemente de quien sea el dato de entrada \((x_{1},\alpha_{1},\alpha_{2})\), terminar y dar como salida el numero \(3\)

3. adhocprefix\((\)E\(3)\)adhocsufix La funcion \(p_{3}^{2,3}\) es \(\Sigma\)-efectivamente computable ya que el siguiente procedimiento con conjunto de datos de entrada \(\omega^{2}\times\Sigma^{\ast3}\) la computa:

   1. adhocprefix-adhocsufix Dado el dato de entrada \((x_{1},x_{2},\alpha_{1},\alpha_{2},\alpha_{3})\), terminar y dar como salida la palabra \(\alpha_{1}\)

4. adhocprefix\((\)E\(4)\)adhocsufix \(Pred\) es \(\Sigma\)-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 \(\mathbb{P}_{-1}\) a dicho procedimiento. El siguiente procedimiento (con conjunto de datos de entrada igual a \(\omega\)) computa a \(Pred\):

   Dado como dato de entrada un elemento \(x\in\omega\), realizar lo siguiente:

   Etapa 1

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

   Etapa 2

   Correr \(\mathbb{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 \(\mathbb{P}_{-1}\) son todos simples y efectivamente realizables ya que \(\mathbb{P}_{-1}\) es efectivo. Por supuesto si uno quisiera ser mas prolijo, deberia reemplazar la Etapa 2 por las distintas instrucciones de \(\mathbb{P}_{-1}\), referidas a \(x\).

5. adhocprefix\((\)E\(5)\)adhocsufix El predicado \(\lambda xy[x<y]\) es \(\Sigma\)-efectivamente computable cualquiera sea el alfabeto \(\Sigma\). Describiremos con palabras un procedimiento que computa a \(\lambda xy[x<y]\). Su conjunto de datos de entrada es \(\omega^{2}\). Dado un par \((x,y)\in\omega^{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. adhocprefix(E\(6\))adhocsufix Veamos que la funcion \(\lambda\alpha[\left\vert \alpha\right\vert ]\) es \(\Sigma\)-efectivamente computable. Como en los lenguajes de programacion, usaremos variables y asignaciones para diseñar el procedimiento. Ademas llamemos \(\mathbb{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 \(\mathbb{P}\) el siguiente procedimiento.

   Dado como dato de entrada un elemento \(\alpha\in\Sigma^{\ast}\), realizar lo siguiente:

   Etapa 1: Hacer las siguientes asignaciones \[\begin{aligned} A & \leftarrow\alpha\\ B & \leftarrow0 \end{aligned}\] e ir a Etapa 2.

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

   Etapa 3: Correr \(\mathbb{P}_{+1}\) con dato de entrada igual al contenido de \(B\), obteniendo \(y\) como salida. Hacer la asignacion \[\begin{aligned} A & \leftarrow\text{resultado de remover el 1er simbolo de }A\\ B & \leftarrow y \end{aligned}\] 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 \(\lambda\alpha[\left\vert \alpha\right\vert ]\)

7. adhocprefix(E\(7\))adhocsufix Si \(\leq\) es el orden total sobre \(\Sigma=\{\blacktriangle,\%\}\) dado por \(\blacktriangle<\%\), entonces veremos que la funcion \(s^{\leq}\) es \(\Sigma\)-efectivamente computable. Primero es importante notar que cualquiera sea \(\alpha\in\Sigma^{\ast}\), se cumple \[\begin{aligned} s^{\leq}(\varepsilon) & =\blacktriangle\\ s^{\leq}(\alpha\blacktriangle) & =\alpha\%\\ s^{\leq}(\alpha\%) & =s^{\leq}(\alpha)\blacktriangle \end{aligned}\] Usaremos estas ecuaciones para dar un procedimiento efectivo (con conjunto de datos de entrada igual a \(\Sigma^{\ast}\)) que compute a \(s^{\leq}\).

   Etapa 1: Dado el dato de entrada \(\alpha\in\Sigma^{\ast}\), hacer las siguientes asignaciones \[\begin{aligned} A & \leftarrow\alpha\\ B & \leftarrow\varepsilon\\ F & \leftarrow\blacktriangle \end{aligned}\] e ir a Etapa 2.

   Etapa 2: Si \(A\) comiensa con \(\blacktriangle\), entonces hacer las siguientes asignaciones \[\begin{aligned} A & \leftarrow\text{resultado de remover el 1er simbolo de }A\\ F & \leftarrow B\%\\ B & \leftarrow B\blacktriangle \end{aligned}\] 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 \[\begin{aligned} A & \leftarrow\text{resultado de remover el 1er simbolo de }A\\ F & \leftarrow F\blacktriangle\\ B & \leftarrow B\% \end{aligned}\] e ir a la Etapa 2. En caso contrario ir a la Etapa 4.

   Etapa 4: Dar como salida \(F\)

8. adhocprefix\((\)E\(8)\)adhocsufix Usando que \(s^{\leq}\) es \(\Sigma\)-efectivamente computable podemos ver que \(\ast^{\leq}:\omega\rightarrow\Sigma^{\ast}\) tambien lo es ya que \(\ast^{\leq}\) es definida con las ecuaciones \[\begin{aligned} \ast^{\leq}(0) & =\varepsilon\\ \ast^{\leq}(x+1) & =s^{\leq}(\ast^{\leq}(x)) \end{aligned}\]

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

1. adhocprefix-adhocsufix \(\lambda xy[x\) divide a \(y]\)

2. adhocprefix-adhocsufix \(\lambda x[pr(x)]\)

3. adhocprefix-adhocsufix \(\lambda ix[(x)_{i}]\)

(Utilice en el diseño de los respectivos procedimientos a los procedimientos que computan las funciones \(\lambda xy\left[x+y\right]\), \(\lambda xy\left[x.y\right]\) y \(\lambda xy\left[x^{y}\right]\))

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\circ g\). Otro ejemplo es el contructor de predicados que dados dos predicados \(\Sigma\)-mixtos \(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, nos define el predicado \[\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}\] Otro constructor muy importante que utilizaremos mucho es aquel que a partir de funciones \(f_{i}:D_{f_{i}}\rightarrow O\), \(i=1,...,k\), tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\), nos da la nueva funcion \(f_{1}\cup...\cup f_{k}\), la cual cumple \[\begin{array}{rll} D_{f_{1}}\cup...\cup D_{f_{k}} & \rightarrow & O\\ e & \rightarrow & \left\{ \begin{array}{clc} f_{1}(e) & & \text{si }e\in D_{f_{1}}\\ \vdots & & \vdots\\ f_{k}(e) & & \text{si }e\in D_{f_{k}} \end{array}\right. \end{array}\]

3.1.2 Composicion

Dadas funciones \(\Sigma\)-mixtas \(f,f_{1},...,f_{r}\), con \(r\geq1\), diremos que la funcion \(f\circ[f_{1},...,f_{r}]\) es obtenida por composicion a partir de las funciones \(f,f_{1},...,f_{r}\). Para probar que la composicion preserva la computabilidad efectiva necesitaremos el siguiente lema.

Proof. Notese que \(f\neq\emptyset\) y \([f_{1},...,f_{r}]\neq\emptyset\) (por que?). Ya que \(f\neq\emptyset\) tenemos que hay unicos \(n,m\in\omega\) y \(s\in\{\#,\ast\}\) tales que \(f\) es de tipo \((n,m,s)\). Ya que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\) y \(I_{[f_{1},...,f_{r}]}\subseteq I_{f_{1}}\times...\times I_{f_{r}}\), tenemos que

1. adhocprefix-adhocsufix \(r=n+m\)

2. adhocprefix-adhocsufix \(I_{f_{i}}\subseteq\omega\), para cada \(i=1,...,n\)

3. adhocprefix-adhocsufix \(I_{f_{i}}\subseteq\Sigma^{\ast}\), para cada \(i=n+1,...,n+m\)

Ya que \([f_{1},...,f_{r}]\neq\emptyset\) tenemos que \(D_{[f_{1},...,f_{r}]}=\bigcap_{i=1}^{r}D_{f_{i}}\neq\emptyset\), por lo cual los conjuntos \(D_{f_{1}},...,D_{f_{n+m}}\) deberan ser todos de un mismo tipo, digamos de tipo \((k,l)\). Es decir que \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\) y \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\).

Las ultimas observaciones del lema son directas de las definiciones de \([f_{1},...,f_{n+m}]\) y de composicion de funciones  

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

Proof. Si \(f\circ[f_{1},...,f_{r}]=\emptyset\), entonces claramente es \(\Sigma\)-efectivamente computable. Supongamos entonces que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\). Por el lema anterior hay \(n,m,k,l\in\omega\) y \(s\in\{\#,\ast\}\) tales que

1. adhocprefix-adhocsufix \(r=n+m\)

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

3. adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\)

4. adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\)

Sean \(\mathbb{P},\mathbb{P}_{1},...,\mathbb{P}_{n+m}\) procedimientos efectivos los cuales computen las funciones \(f,f_{1},...,f_{n+m}\), respectivamente. Usando estos procedimientos es facil definir un procedimiento efectivo el cual compute a \(f\circ[f_{1},...,f_{n+m}]\).  

3.1.3 Lema de division por casos para funciones \(\Sigma\)-efectivamente computables

Recordemos que si \(f_{i}:D_{f_{i}}\rightarrow O\), \(i=1,...,k\), son funciones tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\), entonces \(f_{1}\cup...\cup f_{k}\) es la funcion \[\begin{array}{rll} D_{f_{1}}\cup...\cup D_{f_{k}} & \rightarrow & O\\ e & \rightarrow & \left\{ \begin{array}{clc} f_{1}(e) & & \text{si }e\in D_{f_{1}}\\ \vdots & & \vdots\\ f_{k}(e) & & \text{si }e\in D_{f_{k}} \end{array}\right. \end{array}\]

Proof. Haremos el caso \(O=\Sigma^{\ast}\) y \(k=2\). Sean \(\mathbb{P}_{1}\) y \(\mathbb{P}_{2}\) procedimientos efectivos que computen a \(f_{1}\) y \(f_{2}\), respectivamente. Sea \(\mathbb{P}\) el procedimiento efectivo siguiente:

- Conjunto de datos de entrada de \(\mathbb{P}\) igual a \(\omega^{n}\times\Sigma^{\ast m}\)

- Conjunto de datos de salida de \(\mathbb{P}\) contenido en \(\Sigma^{\ast}\)

- Funcionamiento:

Etapa 1

Hacer \(T=1\)

Etapa 2

Correr el procedimiento \(\mathbb{P}_{1}\) 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 \(\mathbb{P}_{2}\) 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 \(\mathbb{P}\) computa a la funcion \(f_{1}\cup f_{2}\).