1.3 Procedimientos efectivos

Un concepto importante en ciencias de la computación es el de procedimiento o método para realizar alguna tarea determinada. Nos interesan los procedimientos que están definidos en forma precisa e inambigua, es decir aquellos en los cuales en cada paso a seguir, la tarea a realizar esta objetivamente descripta. También deben ser repetibles, en el sentido de que si realizamos un procedimiento dos veces con el mismo dato de entrada, entonces ambas ejecuciones deben ser idénticas, es decir se realizaran las mismas tareas y en el mismo orden.

Nos interesan los procedimientos \(\mathbb{P}\) que posean las siguientes características:

1. adhocprefix(1)adhocsufix El interprete o ejecutante de \(\mathbb{P}\) es una persona que trabajara con papel y lápiz (ambos recursos disponibles en forma ilimitada).

2. adhocprefix(2)adhocsufix Cada paso o tarea que \(\mathbb{P}\) encomiende a realizar debe ser simple y fácil de realizar en forma efectiva por cualquier persona.

3. adhocprefix(3)adhocsufix El procedimiento \(\mathbb{P}\) comienza a funcionar siempre a partir de cierto dato de entrada y una ves que haya comenzado, siempre sucederá una de las dos siguientes posibilidades

   1. adhocprefix(a)adhocsufix \(\mathbb{P}\) luego de cierta cantidad de pasos realizados, se detiene y da cierto dato de salida

   2. adhocprefix(b)adhocsufix \(\mathbb{P}\) nunca se detiene, es decir a medida que se van realizando las instrucciones o tareas, \(\mathbb{P}\) siempre direcciona a realizar nuevas tareas y lo hace sucesiva e indefinidamente.

   En el caso (a) diremos que \(\mathbb{P}\) se detiene partiendo del dato de entrada en cuestión y en el caso (b) diremos que \(\mathbb{P}\) no se detiene partiendo de dicho dato

4. adhocprefix(4)adhocsufix Hay \(n,m\in\omega\) y un alfabeto \(\Sigma\) tales que el conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega^{n}\times\Sigma^{\ast m}\). Cabe aclarar que para ciertas \((n+m)\)-uplas de \(\omega^{n}\times\Sigma^{\ast m}\) el procedimiento \(\mathbb{P}\) se detendrá y para ciertas otras no lo hará.

Llamaremos procedimientos efectivos a aquellos procedimientos que posean las características arriba mencionadas.

El conjunto de datos de salida de \(\mathbb{P}\) es el conjunto de todos los datos que el procedimiento \(\mathbb{P}\) dará como salida en alguna de las posibles ejecuciones al variar todos los datos de entrada posibles. Si bien siempre el conjunto de datos de entrada será de la forma \(\omega^{n}\times\Sigma^{\ast m}\), puede ser muy difícil o imposible, en general, conocer con precisión el conjunto de datos de salida de un procedimiento (esto lo justificaremos mas adelante).

Ya que el interprete de \(\mathbb{P}\) es una persona dotada de lápiz y papel, supondremos que los elementos de \(\omega\) que intervienen en los datos de entrada y de salida estarán representados por palabras de \(Num\) usando la notación decimal clásica (i.e. con 0).

Quizás el procedimiento efectivo mas famoso de la matemática es aquel que se enseña en los colegios para sumar dos números naturales expresados en notación decimal. Notar que el conjunto de datos de entrada de dicho procedimiento es \(\omega^{2}\) y el conjunto de datos de salida es el conjunto formado por todas las sumas posibles de pares de elementos de \(\omega\), es decir \(\omega\). Por supuesto este procedimiento solo usa lápiz, papel y pasos extremadamente simples a seguir en cada momento de la computación, es decir, en algún sentido, no es necesario "entender que es lo que se esta haciendo" para llegar al final y obtener la palabra que representa en notación decimal a la suma de los números iniciales. Dejamos al lector repasar este procedimiento así como el que calcula dado un número \(x\) no nulo de \(\omega\), al número \(x-1\), los cuales nos harán falta mas adelante en los ejemplos.

1.3.1 Funciones \(\Sigma\)-efectivamente computables

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

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})\)

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

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})\)

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:

1. 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.

2. 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:

   1. 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\)

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:

   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 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\).

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 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.

6. 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 ]\)

7. 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\)

8. 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:

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 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.

1.3.2 Conjuntos \(\Sigma\)-efectivamente computables

Un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-efectivamente computable cuando la función \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\) sea \(\Sigma\)-efectivamente computable. O sea que \(S\) es \(\Sigma\)-efectivamente computable sii hay un procedimiento efectivo \(\mathbb{P}\), el cual computa \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\), es decir:

1. adhocprefix-adhocsufix El conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega^{n}\times\Sigma^{\ast m}\), siempre termina y da como dato de salida un elemento de \(\{0,1\}\).

2. adhocprefix-adhocsufix Dado \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\), \(\mathbb{P}\) da como salida al número \(1\) si \((\vec{x},\vec{\alpha})\in S\) y al número \(0\) si \((\vec{x},\vec{\alpha})\notin S\).

Nótese que esta definición para el caso \(S=\emptyset\) tiene a priori cierta ambigüedad ya que cualesquiera sean \(n,m\in\omega\) tenemos que \(\emptyset\subseteq\omega^{n}\times\Sigma^{\ast m}\). De todas maneras, cualesquiera sean los \(n,m\) elegidos, siempre hay un procedimiento efectivo que computa a \(\chi_{\emptyset}^{\omega^{n}\times\Sigma^{\ast m}}\), i.e. un procedimiento que siempre da como salida \(0\), cualesquiera sea el dato de entrada de \(\omega^{n}\times\Sigma^{\ast m}\). Es decir que el conjunto \(\emptyset\) es \(\Sigma\)-efectivamente computable cualesquiera sea el alfabeto \(\Sigma\). Cabe destacar que para el caso de un conjunto \(S\neq\emptyset\), nuestra definición es inambigua ya que hay únicos \(n,m\in\omega\) tales que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\).

Si \(\mathbb{P}\) es un procedimiento efectivo el cual computa a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\), diremos que \(\mathbb{P}\) decide la pertenencia a \(S\), con respecto al conjunto \(\omega^{n}\times\Sigma^{\ast m}\).

Dejamos al lector la fácil prueba del siguiente resultado.

El siguiente lema caracteriza cuando un conjunto rectangular es \(\Sigma\)-efectivamente computable

Proof. Nótese que si \(n=m=0\), entonces \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}=\{\lozenge\}\) el cual es \(\Sigma\)-efectivamente computable por lo cual el lema se cumple. Vemos entonces el caso \(n+m\geq1\). Para hacer mas legible la prueba haremos el caso \(n=m=1\). La prueba general es completamente análoga.

(\(\Rightarrow\)) Ya que \(S_{1}\) y \(L_{1}\) son conjuntos no vacíos, hay \(x_{0}\in S_{1}\) y \(\alpha_{0}\in L_{1}\). Ya que \(S_{1}\times L_{1}\) es \(\Sigma\)-efectivamente computable, tenemos que \(\chi_{S_{1}\times L_{1}}^{\omega\times\Sigma^{\ast}}\) es \(\Sigma\)-efectivamente computable. Nótese que: \[x\in S_{1}\text{ sii }(x,\alpha_{0})\in S_{1}\times L_{1}\text{ sii }\chi_{S_{1}\times L_{1}}^{\omega\times\Sigma^{\ast}}(x,\alpha_{0})=1\text{ }\] Por lo tanto, es fácil usando un procedimiento efectivo que compute a \(\chi_{S_{1}\times L_{1}}^{\omega\times\Sigma^{\ast}}\) diseñar un procedimiento efectivo que compute a \(\chi_{S_{1}}^{\omega}\). En forma similar se prueba que \(L_{1}\) es \(\Sigma\)-efectivamente computable.

(\(\Leftarrow\)) Es fácil, usando procedimientos efectivos que computen a \(\chi_{S_{1}}^{\omega}\) y \(\chi_{L_{1}}^{\Sigma^{\ast}}\), armar un procedimiento efectivo que compute a \(\chi_{S_{1}\times L_{1}}^{\omega\times\Sigma^{\ast}}\).  

1.3.3 Conjuntos \(\Sigma\)-efectivamente enumerables

Un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) será llamado \(\Sigma\)-efectivamente enumerable cuando sea vacío o haya una función \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que \(I_{F}=S\) y \(F_{(i)}\) sea \(\Sigma\)-efectivamente computable, para cada \(i\in\{1,...,n+m\}\). Nótese que para el caso \(n=m=0\), la condición de que \(F_{(i)}\) sea \(\Sigma\)-efectivamente computable, para cada \(i\in\{1,...,n+m\}\) se cumple vacuamente y por lo tanto la definición anterior nos dice que un conjunto \(S\subseteq\omega^{0}\times\Sigma^{\ast0}=\{\lozenge\}\) será \(\Sigma\)-efectivamente enumerable sii es vacío o hay una función \(F:\omega\rightarrow\{\lozenge\}\), tal que \(I_{F}=S\). Por supuesto, esto nos dice que \(\emptyset\) y \(\{\lozenge\}\) son \(\Sigma\)-efectivamente enumerables.

El siguiente resultado nos permite entender mejor la idea subyacente a esta definición.

Proof. El caso \(n=m=0\) es fácil y es dejado al lector. Supongamos entonces que \(n+m\geq1\).

(\(\Rightarrow\)) Supongamos que \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es \(\Sigma\)-efectivamente enumerable. Ya que \(S\) es no vacío, por definición hay una función \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que \(I_{F}=S\) y cada \(F_{(i)}\) es \(\Sigma\)-efectivamente computable. Para cada \(i\in\{1,...,n+m\}\) sea \(\mathbb{P}_{i}\) un procedimiento efectivo que compute a \(F_{(i)}\). Notar que cada \(\mathbb{P}_{i}\) tiene a \(\omega\) como conjunto de datos de entrada y siempre termina. Sea \(\mathbb{P}\) el siguiente procedimiento efectivo, con conjunto de datos de entrada igual a \(\omega\) y conjunto de datos de salida contenido en \(\omega^{n}\times\Sigma^{\ast m}\).

Etapa 1: Correr \(\mathbb{P}_{1}\) con dato de entrada \(x\) y alojar el dato de salida en la variable \(X_{1}\)

Etapa 2: Correr \(\mathbb{P}_{2}\) con dato de entrada \(x\) y alojar el dato de salida en la variable \(X_{2}\)

\(\ \ \ \ \vdots\)

Etapa \(n\): Correr \(\mathbb{P}_{n}\) con dato de entrada \(x\) y alojar el dato de salida en la variable \(X_{n}\)

Etapa \(n+1\): Correr \(\mathbb{P}_{n+1}\) con dato de entrada \(x\) y alojar el dato de salida en la variable \(A_{1}\)

Etapa \(n+2\): Correr \(\mathbb{P}_{n+2}\) con dato de entrada \(x\) y alojar el dato de salida en la variable \(A_{2}\)

\(\ \ \ \ \vdots\)

Etapa \(n+m\): Correr \(\mathbb{P}_{n+m}\) con dato de entrada \(x\) y alojar el dato de salida en la variable \(A_{m}\)

Etapa \(n+m+1\): Detenerse y dar \((X_{1},...,X_{n},A_{1},...,A_{m})\) como dato de salida

Dejamos al lector la verificación de que el procedimiento \(\mathbb{P}\) es efectivo y cumple las propiedades (1), (2) y (3).

(\(\Leftarrow\)) Supongamos \(\mathbb{P}\) es un procedimiento efectivo el cual cumple las propiedades (1), (2) y (3). Definamos \(F:\omega\rightarrow\omega^{n}\times\Sigma^{\ast m}\), de la siguiente manera: \[F(x)=\text{ dato de salida de }\mathbb{P}\text{ cuando lo corremos desde }x\] Notar que para cada \(i\in\{1,...,n+m\}\) la función \(F_{(i)}\) es \(\Sigma\)-efectivamente computable ya que el siguiente procedimiento efectivo la computa:

Etapa 1: Correr \(\mathbb{P}\) desde \(x\) y guardar la salida en la variable \(V\)

Etapa 2: Dar como salida la coordenada \(i\)-ésima de \(V\)  

Cuando un procedimiento \(\mathbb{P}\) cumpla (1), (2) y (3) del lema anterior, diremos que \(\mathbb{P}\) enumera a \(S\). O sea que \(S\) es \(\Sigma\)-efectivamente enumerable sii es vacío o hay un procedimiento efectivo el cual enumera a \(S\).

Dicho de otra forma un conjunto no vacío \(S\) es \(\Sigma\)-efectivamente enumerable sii hay un procedimiento efectivo \(\mathbb{P}\) el cual tiene conjunto de datos de entrada \(\omega\) y además para los sucesivos datos de entrada \(0,1,2,3,...\), el procedimiento \(\mathbb{P}\) produce respectivamente los datos de salida \(e_{0},e_{1},e_{2},e_{3},...\) de manera que \(S=\{e_{0},e_{1},e_{2},...\}\). Cabe destacar aquí que puede suceder que \(e_{i}=e_{j}\), para ciertos \(i,j\), con \(i\neq j\).

Algunos ejemplos:

1. adhocprefix(E1)adhocsufix El conjunto \(S=\{x\in\omega:x\) es par\(\}\) es \(\Sigma\)-efectivamente enumerable, cualesquiera sea \(\Sigma\). El siguiente procedimiento enumera a \(S\):

   1. adhocprefix-adhocsufix Calcular \(2x\), darlo como dato de salida y terminar.

2. adhocprefix(E2)adhocsufix Un procedimiento que enumera \(\omega\times\omega\) es el siguiente:

   Etapa 1

   Si \(x=0\), dar como salida el par \((0,0)\) y terminar. Si \(x\neq0\), calcular \(x_{1}=(x)_{1}\) y \(x_{2}=(x)_{2}\).

   Etapa 2

   Dar como dato de salida el par \((x_{1},x_{2})\) y terminar

   Como puede notarse el procedimiento es efectivo y además el conjunto de datos de salida es \(\omega\times\omega\) ya que si tomamos un par cualquiera \((a,b)\in\omega\times\omega\), el procedimiento lo dará como dato de salida para la entrada \(x=2^{a}3^{b}\).

3. adhocprefix(E3)adhocsufix Veamos que \(\omega^{2}\times\Sigma^{\ast3}\) es \(\Sigma\)-efectivamente enumerable cualquiera sea el alfabeto no vacío \(\Sigma\). Sea \(\leq\) un orden total para el alfabeto \(\Sigma\). Utilizando el orden \(\leq\) podemos diseñar el siguiente procedimiento para enumerar \(\omega^{2}\times\Sigma^{\ast3}\):

   Etapa 1

   Si \(x=0\), dar como salida \((0,0,\varepsilon,\varepsilon,\varepsilon)\) y terminar. Si \(x\neq0\), calcular

   \(x_{1}=(x)_{1}\)

   \(x_{2}=(x)_{2}\)

   \(\alpha_{1}=\ast^{\leq}((x)_{3})\)

   \(\alpha_{2}=\ast^{\leq}((x)_{4})\)

   \(\alpha_{3}=\ast^{\leq}((x)_{5})\)

   Etapa 2

   Dar como dato de salida la 5-upla \((x_{1},x_{2},\alpha_{1},\alpha_{2},\alpha_{3})\).

Proof. El caso en el que alguno de los conjuntos es vacío es trivial. Supongamos que ambos conjuntos son no vacíos y sean \(\mathbb{P}_{1}\) y \(\mathbb{P}_{2}\) procedimientos que enumeran a \(S_{1}\) y \(S_{2}\). El siguiente procedimiento enumera al conjunto \(S_{1}\cup S_{2}\):

1. adhocprefix-adhocsufix Si \(x\) es par realizar \(\mathbb{P}_{1}\) partiendo de \(x/2\) y dar el elemento de \(S_{1}\) obtenido como salida. Si \(x\) es impar realizar \(\mathbb{P}_{2}\) partiendo de \((x-1)/2\) y dar el elemento de \(S_{2}\) obtenido como salida.

Veamos ahora que \(S_{1}\cap S_{2}\) es \(\Sigma\)-efectivamente enumerable. Si \(S_{1}\cap S_{2}=\emptyset\) entonces no hay nada que probar. Supongamos entonces que \(S_{1}\cap S_{2}\) es no vacío. Sea \(e_{0}\) un elemento fijo de \(S_{1}\cap S_{2}\). Sea \(\mathbb{P}\) un procedimiento efectivo el cual enumere a \(\omega\times\omega\) (ver el ejemplo de mas arriba). Un procedimiento que enumera a \(S_{1}\cap S_{2}\) es el siguiente

Etapa 1

Realizar \(\mathbb{P}\) con dato de entrada \(x\), para obtener un par \((x_{1},x_{2})\in\omega\times\omega\).

Etapa 2

Realizar \(\mathbb{P}_{1}\) con dato de entrada \(x_{1}\) para obtener un elemento \(e_{1}\in S_{1}\)

Etapa 3

Realizar \(\mathbb{P}_{2}\) con dato de entrada \(x_{2}\) para obtener un elemento \(e_{2}\in S_{2}\)

Etapa 4

Si \(e_{1}=e_{2}\), entonces dar como dato de salida \(e_{1}.\) En caso contrario dar como dato de salida \(e_{0}\).

Dejamos al lector la prueba de que este procedimiento enumera a \(S_{1}\cap S_{2}\).  

Dejamos al lector la prueba del siguiente resultado.

Proof. Supongamos \(S\neq\emptyset\). Sea \((\vec{z},\gamma)\in S\), fijo. Sea \(\mathbb{P}\) un procedimiento efectivo que compute a \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\). Ya vimos en el ejemplo anterior que \(\omega^{2}\times\Sigma^{\ast3}\) es \(\Sigma\)-efectivamente enumerable. En forma similar se puede ver que \(\omega^{n}\times\Sigma^{\ast m}\) lo es. Sea \(\mathbb{P}_{1}\) un procedimiento efectivo que enumera a \(\omega^{n}\times\Sigma^{\ast m}\). Entonces el siguiente procedimiento enumera a \(S\):

Etapa 1

Realizar \(\mathbb{P}_{1}\) con \(x\) de entrada para obtener \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\).

Etapa 2

Realizar \(\mathbb{P}\) con \((\vec{x},\vec{\alpha})\) de entrada para obtener el valor Booleano \(e\) de salida.

Etapa 3

Si \(e=1\) dar como dato de salida \((\vec{x},\vec{\alpha}).\) Si \(e=0\) dar como dato de salida \((\vec{z},\gamma)\).  

Como veremos mas adelante (Proposición 4.17), hay conjuntos que son \(\Sigma\)-efectivamente enumerables y no \(\Sigma\)-efectivamente computables. Sin embargo tenemos el siguiente interesante resultado:

Proof. (a)\(\Rightarrow\)(b). Por el lema anterior tenemos que \(S\) es \(\Sigma\)-efectivamente enumerable. Nótese además que, dado que \(S\) es \(\Sigma\)-efectivamente computable, \((\omega^{n}\times\Sigma^{\ast m})-S\) también lo es (por que?). Es decir que aplicando nuevamente el lema anterior tenemos que \((\omega^{n}\times\Sigma^{\ast m})-S\) es \(\Sigma\)-efectivamente enumerable.

(b)\(\Rightarrow\)(a). Si \(S=\emptyset\) o \(S=\omega^{n}\times\Sigma^{\ast m}\) es claro que se cumple (a). O sea que podemos suponer que ni \(S\) ni \((\omega^{n}\times\Sigma^{\ast m})-S\) son igual al conjunto vacío. Sea \(\mathbb{P}_{1}\) un procedimiento efectivo que enumere a \(S\) y sea \(\mathbb{P}_{2}\) un procedimiento efectivo que enumere a \((\omega^{n}\times\Sigma^{\ast m})-S\). Es fácil ver que el siguiente procedimiento computa el predicado predicado \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\):

Etapa 1

Darle a la variable \(T\) el valor \(0\).

Etapa 2

Realizar \(\mathbb{P}_{1}\) con el valor de \(T\) como entrada para obtener de salida la upla \((\vec{y},\vec{\beta})\).

Etapa 3

Realizar \(\mathbb{P}_{2}\) con el valor de \(T\) como entrada para obtener de salida la upla \((\vec{z},\vec{\gamma})\).

Etapa 4

Si \((\vec{y},\vec{\beta})=(\vec{x},\vec{\alpha})\), entonces detenerse y dar como dato de salida el valor \(1\). Si \((\vec{z},\vec{\gamma})=(\vec{x},\vec{\alpha})\), entonces detenerse y dar como dato de salida el valor \(0.\) Si no suceden ninguna de las dos posibilidades antes mencionadas, aumentar en \(1\) el valor de la variable \(T\) y dirigirse a la Etapa 2.  

Supongamos que \(k,l,n,m\in\omega\) y que \(F:D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega^{n}\times\Sigma^{\ast m}\). Supongamos además que \(n+m\geq1\). Entonces denotaremos con \(F_{(i)}\) a la función \(p_{i}^{n,m}\circ F\). Notar que \[\begin{aligned} F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega\text{, para cada }i=1,...,n\\ F_{(i)} & :D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\Sigma^{\ast}\text{, para cada }i=n+1,...,n+m \end{aligned}\] Por lo cual cada una de las funciones \(F_{(i)}\) son \(\Sigma\)-mixtas. Además nótese que \[F=[F_{(1)},...,F_{(n+m)}]\]

Proof. El caso \(n=m=0\) es fácil y es dejado al lector. Supongamos entonces que \(n+m\geq1\).

(1)\(\Rightarrow\)(2). Supongamos \(S=\emptyset\). Sea \(F=\emptyset\). Es claro que \(F:\emptyset\rightarrow\omega^{n}\times\Sigma^{\ast m}\) y cada \(F_{(i)}=\emptyset\), por lo cual es \(\Sigma\)-efectivamente computable. Además \(I_{F}=\emptyset\) por lo cual se cumple (2). Cuando \(S\) es no vacío, la definición de conjunto \(\Sigma\)-efectivamente enumerable nos dice que se cumple (2) (con \(k=1\) y \(l=0\)).

(2)\(\Rightarrow\)(3). Para \(i=1,...,n+m\), sea \(\mathbb{P}_{i}\) un procedimiento el cual computa a \(F_{(i)}\) y sea \(\mathbb{P}\) un procedimiento el cual enumere a \(\omega\times\omega^{k}\times\Sigma^{\ast l}.\) El siguiente procedimiento computa la función \(f:I_{F}\rightarrow\{1\}\):

Etapa 1

Darle a la variable \(T\) el valor 0.

Etapa 2

Hacer correr \(\mathbb{P}\) con dato de entrada \(T\) y obtener \((t,z_{1},...,z_{k},\gamma_{1},...,\gamma_{l})\) como dato de salida.

Etapa 3

Para cada \(i=1,...,n+m\), hacer correr \(\mathbb{P}_{i}\) durante \(t\) pasos, con dato de entrada \((z_{1},...,z_{k},\gamma_{1},...,\gamma_{l}).\) Si cada procedimiento \(\mathbb{P}_{i}\) al cabo de los \(t\) pasos término y dio como resultado el valor \(o_{i}\), entonces comparar \((\vec{x},\vec{\alpha})\) con \((o_{1},...,o_{n+m})\) y en caso de que sean iguales detenerse y dar como dato de salida el valor \(1\). En el caso en que no son iguales, aumentar en \(1\) el valor de la variable \(T\) y dirigirse a la Etapa 2. Si algún procedimiento \(\mathbb{P}_{i}\) al cabo de los \(t\) pasos no terminó, entonces aumentar en \(1\) el valor de la variable \(T\) y dirigirse a la Etapa 2.

(3)\(\Rightarrow\)(1). Supongamos \(S\neq\emptyset\). Sea \((\vec{z},\vec{\gamma})\) un elemento fijo de \(S\). Sea \(\mathbb{P}\) un procedimiento el cual compute a \(f\). Sea \(\mathbb{P}_{1}\) un procedimiento el cual enumere a \(\omega\times\omega^{n}\times\Sigma^{\ast m}.\) Dejamos al lector el diseño de un procedimiento efectivo el cual enumere \(D_{f}\).  

Dejamos como ejercicio la prueba de los dos siguientes lemas.

1.3.4 Algunos constructores que preservan la computabilidad efectiva

Hay muchos procesos constructivos que nos sirven para definir o construir una función en términos de otras funciones dadas. Un ejemplo de esto es la composición de funciones, la cual dadas dos funciones \(f,g\) nos permite construir su composición, a saber \(f\circ g\). Otro ejemplo es el constructor 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 define la nueva función \(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}\] Veremos a continuación que estos constructores preservan la computabilidad efectiva en el sentido que si las funciones iniciales son \(\Sigma\)-efectivamente computables, entonces la construida también lo es.

1.3.4.1 Operaciones logicas entre predicados

1.3.4.2 Composición

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

Proof. Nótese que \(f\neq\emptyset\) y \([f_{1},...,f_{r}]\neq\emptyset\) (por que?). Ya que \(f\neq\emptyset\) tenemos que hay únicos \(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}}\) deberán 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 últimas observaciones del lema son directas de las definiciones de \([f_{1},...,f_{n+m}]\) y de composición de funciones  

Ahora sí podemos probar fácilmente 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 fácil definir un procedimiento efectivo el cual compute a \(f\circ[f_{1},...,f_{n+m}]\).  

1.3.4.3 Lema de división 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 función \[\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 función \(f_{1}\cup f_{2}\).  

1.3.5 Independencia del alfabeto

Una observación importante es que los conceptos de función \(\Sigma\)-efectivamente computable, de conjunto \(\Sigma\)-efectivamente computable y de conjunto \(\Sigma\)-efectivamente enumerable, no dependen del alfabeto \(\Sigma\). Esto lo establecemos formalmente en los dos siguientes lemas.

Dejamos al lector los detalles de las rutinarias pruebas de estos dos lemas.