Una función \(\Sigma\)-mixta \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) será llamada \(\Sigma\)-efectivamente computable si hay un procedimiento efectivo \(\mathbb{P}\) tal que
adhocprefix(1)adhocsufix El conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega^{n}\times\Sigma^{\ast m}\)
adhocprefix(2)adhocsufix El conjunto de datos de salida esta contenido en \(\omega\).
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})\).
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})\)
Análogamente una función \(\Sigma\)-mixta \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\Sigma^{\ast}\) será llamada \(\Sigma\)-efectivamente computable si hay un procedimiento efectivo \(\mathbb{P}\) tal que
adhocprefix(1)adhocsufix El conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega^{n}\times\Sigma^{\ast m}\)
adhocprefix(2)adhocsufix El conjunto de datos de salida esta contenido en \(\Sigma^{\ast}\).
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})\).
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})\)
Cuando un procedimiento \(\mathbb{P}\) cumpla los items (1), (2), (3) y (4) de arriba diremos que \(\mathbb{P}\) computa a la función \(f\) o que \(f\) es computada por \(\mathbb{P}\).
Nótese que esta definición para el caso \(f=\emptyset\) tiene a priori cierta ambigüedad 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\) elegidos, 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 función \(\emptyset\) es \(\Sigma\)-efectivamente computable cualesquiera sea el alfabeto \(\Sigma\). Cabe destacar que para el caso de una función \(f\neq\emptyset\), nuestra definición es inambigua ya que hay únicos \(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:
adhocprefix\((\)E\(1)\)adhocsufix La función \(\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 números en notación decimal es efectivo y computa esta función. También las funciones \(\lambda xy\left[x.y\right]\) y \(\lambda xy\left[x^{y}\right]\) son \(\Sigma\)-efectivamente computables vía los procedimientos clásicos enseñados en la escuela primaria.
adhocprefix\((\)E\(2)\)adhocsufix La función \(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:
adhocprefix-adhocsufix Independientemente de quien sea el dato de entrada \((x_{1},\alpha_{1},\alpha_{2})\), terminar y dar como salida el número \(3\)
adhocprefix\((\)E\(3)\)adhocsufix La función \(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:
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}\)
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 número no nulo \(x\), expresado en notación decimal, calcula el número \(x-1\), en notación 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, debería reemplazar la Etapa 2 por las distintas instrucciones de \(\mathbb{P}_{-1}\), referidas a \(x\).
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 notación decimal representan a \(x\) y \(y\). Por supuesto esto lo hace borrando de a un símbolo y viendo si alguna se termina primero. Si resultan de distinta longitud, es fácil darse cuenta como sigue. En caso de que las palabras resulten de igual longitud, entonces se hace el procedimiento clásico de ir comparando dígitos de izquierda a derecha.
adhocprefix(E\(6\))adhocsufix Veamos que la función \(\lambda\alpha[\left\vert \alpha\right\vert ]\) es \(\Sigma\)-efectivamente computable. Como en los lenguajes de programación, usaremos variables y asignaciones para diseñar el procedimiento. Además llamemos \(\mathbb{P}_{+1}\) a el procedimiento de la escuela primaria que dado un número no nulo \(x\), expresado en notación decimal, calcula el número \(x+1\), en notación 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 asignación \[\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 convencerse que el uso de asignaciones puede realizarse usando solo lápiz y papel. Imagine como lo haría en este ejemplo y corrobore que dicho procedimiento es efectivo y además computa a \(\lambda\alpha[\left\vert \alpha\right\vert ]\)
adhocprefix(E\(7\))adhocsufix Si \(\leq\) es el orden total sobre \(\Sigma=\{\blacktriangle,\%\}\) dado por \(\blacktriangle<\%\), entonces veremos que la función \(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\) comienza 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\) comienza 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\)
adhocprefix\((\)E\(8)\)adhocsufix Usando que \(s^{\leq}\) es \(\Sigma\)-efectivamente computable podemos ver que \(\ast^{\leq}:\omega\rightarrow\Sigma^{\ast}\) también 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 ejercicio para el lector diseñar procedimientos efectivos que computen las funciones:
adhocprefix-adhocsufix \(\lambda xy[x\) divide a \(y]\)
adhocprefix-adhocsufix \(\lambda x[pr(x)]\)
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 nos permitiremos trabajar con procedimientos que son efectivos en términos de otros que ya se han dado, es decir daremos procedimientos que en principio no es claro que sean efectivos pero los cuales se volverían efectivos si reemplazáramos ciertas instrucciones por la manera efectiva de simularlas. Para hacer mas dinámico el discurso no distinguiremos entre este tipo de procedimientos (efectivizables) y los efectivos propiamente dichos.