3.1 Funciones $\Sigma$-efectivamente computables

Una funcion $\Sigma$-mixta $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 ${\omega }^n\times {\Sigma }^{\ast m}$

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

3. (3) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in D_f$, entonces $P$ se detiene partiendo de $(\overrightarrow{x},\overrightarrow{\alpha })$, dando como dato de salida $f(\overrightarrow{x},\overrightarrow{\alpha })$.

4. (4) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in ({\omega }^n\times {\Sigma }^{\ast m})-D_f$, entonces $P$ no se detiene partiendo desde $(\overrightarrow{x},\overrightarrow{\alpha })$

Analogamente una funcion $\Sigma$-mixta $f:D_f\subseteq {\omega }^n\times {\Sigma }^{\ast m}\to {\Sigma }^{\ast }$ sera llamada $\Sigma$-efectivamente computable si hay un procedimiento efectivo $P$ tal que

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

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

3. (3) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in D_f$, entonces $P$ se detiene partiendo de $(\overrightarrow{x},\overrightarrow{\alpha })$, dando como dato de salida $f(\overrightarrow{x},\overrightarrow{\alpha })$.

4. (4) Si $(\overrightarrow{x},\overrightarrow{\alpha })\in ({\omega }^n\times {\Sigma }^{\ast m})-D_f$, entonces $P$ no se detiene partiendo desde $(\overrightarrow{x},\overrightarrow{\alpha })$

Cuando un procedimiento $P$ cumpla los items (1), (2), (3) y (4) de arriba diremos que $P$ computa a la funcion $f$ o que $f$ es computada por $P$.

Notese que esta definicion para el caso $f=\varnothing$ tiene a priori cierta ambiguedad ya que cualesquiera sean $n,m\in \omega$ y $O\in \{\omega ,{\Sigma }^{\ast }\}$ tenemos que $\varnothing :\varnothing \subseteq {\omega }^n\times {\Sigma }^{\ast m}\to O$ ya que $D_{\varnothing }=\varnothing$ y $I_{\varnothing }=\varnothing$. De todas maneras, cualesquiera sean los $n,m$ y $O$ elejidos, siempre hay un procedimiento efectivo que computa a $f=\varnothing$, 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 $\varnothing$ es $\Sigma$-efectivamente computable cualesquiera sea el alfabeto $\Sigma$. Cabe destacar que para el caso de una funcion $f\ne \varnothing$, 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}\to O$.

Veamos algunos ejemplos:

1. $($E$1)$ La funcion $\lambda xy[x+y]$ 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[x.y]$ y $\lambda xy\left[x^y\right]$ son $\Sigma$-efectivamente computables via los procedimientos clasicos enseñados en la escuela primaria.

2. $($E$2)$ La funcion $C_3^{1,2}$ es $\Sigma$-efectivamente computable ya que el siguiente procedimiento $P$ con conjunto de datos de entrada $\omega \times {\Sigma }^{\ast 2}$ la computa:

   1. - Independientemente de quien sea el dato de entrada $(x_1,{\alpha }_1,{\alpha }_2)$, terminar y dar como salida el numero $3$

3. $($E$3)$ 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 }^{\ast 3}$ la computa:

   1. - 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. $($E$4)$ $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 $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 $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. $($E$5)$ 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. (E$6$) Veamos que la funcion $\lambda \alpha \left[\left|\alpha \right|\right]$ es $\Sigma$-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 $\alpha \in {\Sigma }^{\ast }$, realizar lo siguiente:

   Etapa 1: Hacer las siguientes asignaciones $$\begin{array}{cc}A& \leftarrow \alpha \\ B& \leftarrow 0\end{array}$$ e ir a Etapa 2.

   Etapa 2: Si $A$ no es $\epsilon$, 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 $$\begin{array}{cc}A& \leftarrow \text{resultado de remover el 1er simbolo de}A\\ B& \leftarrow y\end{array}$$ 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[\left|\alpha \right|\right]$

7. (E$7$) Si $\le$ es el orden total sobre $\Sigma =\{▲,\%\}$ dado por $▲<\%$, entonces veremos que la funcion $s^{\le }$ es $\Sigma$-efectivamente computable. Primero es importante notar que cualquiera sea $\alpha \in {\Sigma }^{\ast }$, se cumple $$\begin{array}{cc}{s}^{\le }\left(\epsilon \right)& =▲\\ s^{\le }\left(\alpha ▲\right)& =\alpha \%\\ s^{\le }\left(\alpha \%\right)& =s^{\le }\left(\alpha \right)▲\end{array}$$ Usaremos estas ecuaciones para dar un procedimiento efectivo (con conjunto de datos de entrada igual a ${\Sigma }^{\ast }$) que compute a $s^{\le }$.

   Etapa 1: Dado el dato de entrada $\alpha \in {\Sigma }^{\ast }$, hacer las siguientes asignaciones $$\begin{array}{cc}A& \leftarrow \alpha \\ B& \leftarrow \epsilon \\ F& \leftarrow ▲\end{array}$$ e ir a Etapa 2.

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

   Etapa 4: Dar como salida $F$

8. $($E$8)$ Usando que $s^{\le }$ es $\Sigma$-efectivamente computable podemos ver que ${\ast }^{\le }:\omega \to {\Sigma }^{\ast }$ tambien lo es ya que ${\ast }^{\le }$ es definida con las ecuaciones $$\begin{array}{cc}{\ast }^{\le }\left(0\right)& =\epsilon \\ {\ast }^{\le }(x+1)& =s^{\le }\left({\ast }^{\le }\right(x\left)\right)\end{array}$$

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

1. - $\lambda xy[x$ divide a $y]$

2. - $\lambda x\left[pr\right(x\left)\right]$

3. - $\lambda ix\left[\right(x{)}_i]$

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

Nota Importante: en lo que sigue muchas veces nos permitiremos trabajar con procedimientos que son efectivos en terminos de otros que ya se han dado, es decir daremos procedimientos que en principio no es claro que sean efectivos pero los cuales se volverian efectivos 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.