Un conjunto \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) sera llamado \(\Sigma\)-efectivamente enumerable cuando sea vacio o haya una funcion \(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\}\). Notese que para el caso \(n=m=0\), la condicion de que \(F_{(i)}\) sea \(\Sigma\)-efectivamente computable, para cada \(i\in\{1,...,n+m\}\) se cumple vacuamente y por lo tanto la definicion anterior nos dice que un conjunto \(S\subseteq\omega^{0}\times\Sigma^{\ast0}=\{\Diamond\}\) sera \(\Sigma\)-efectivamente enumerable sii es vacio o hay una funcion \(\Sigma\)-efectivamente computable \(F:\omega\rightarrow\{\Diamond\}\), tal que \(I_{F}=S\). Por supuesto, esto nos dice que \(\emptyset\) y \(\{\Diamond\}\) son \(\Sigma\)-efectivamente enumerables.
El siguiente resultado nos permite entender mejor la idea subyacente a esta definicion.
3.7. Un conjunto no vacio \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es \(\Sigma\)-efectivamente enumerable sii hay un procedimiento efectivo \(\mathbb{P}\) tal que
adhocprefix(1)adhocsufix El conjunto de datos de entrada de \(\mathbb{P}\) es \(\omega\)
adhocprefix(2)adhocsufix \(\mathbb{P}\) se detiene para cada \(x\in\omega\)
adhocprefix(3)adhocsufix El conjunto de datos de salida de \(\mathbb{P}\) es igual a \(S\). (Es decir, siempre que \(\mathbb{P}\) se detiene, da como salida un elemento de \(S\), y para cada elemento \((\vec{x},\vec{\alpha})\in S\), hay un \(x\in\omega\) tal que \(\mathbb{P}\) da como salida a \((\vec{x},\vec{\alpha})\) cuando lo corremos con \(x\) como dato de entrada)
Proof. El caso \(n=m=0\) es facil 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 vacio, por definicion hay una funcion \(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 verificacion 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 funcion \(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\)-esima 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 vacio o hay un procedimiento efectivo el cual enumera a \(S\).
Dicho de otra forma un conjunto no vacio \(S\) es \(\Sigma\)-efectivamente enumerable sii hay un procedimiento efectivo \(\mathbb{P}\) el cual tiene conjunto de datos de entrada \(\omega\) y ademas 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 aqui que puede suceder que \(e_{i}=e_{j}\), para ciertos \(i,j\), con \(i\neq j\).
Algunos ejemplos:
adhocprefixE\(_{1}\)adhocsufix El conjunto \(S=\{x\in\omega:x\) es par\(\}\) es \(\Sigma\)-efectivamente enumerable, cualesquiera sea \(\Sigma\). El siguiente procedimiento enumera a \(S\):
adhocprefix-adhocsufix Calcular \(2x\), darlo como dato de salida y terminar.
adhocprefixE\(_{2}\)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 ademas 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 dara como dato de salida para la entrada \(x=2^{a}3^{b}\).
adhocprefixE\(_{3}\)adhocsufix Veamos que \(\omega^{2}\times\Sigma^{\ast3}\) es \(\Sigma\)-efectivamente enumerable cualquiera sea el alfabeto no vacio \(\Sigma\). Sea \(\leq\) un orden total para el alfabeto \(\Sigma\). Utilisando el orden \(<\) 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})\).
3.8. Sean \(S_{1},S_{2}\subseteq\omega^{n}\times\Sigma^{\ast m}\) conjuntos \(\Sigma\)-efectivamente enumerables. Entonces \(S_{1}\cup S_{2}\) y \(S_{1}\cap S_{2}\) son \(\Sigma\)-efectivamente enumerables.
Proof. El caso en el que alguno de los conjuntos es vacio es trivial. Supongamos que ambos conjuntos son no vacios 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}\):
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 vacio. 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.
3.9. Supongamos \(S_{1},...,S_{n}\subseteq\omega\), \(L_{1},...,L_{m}\subseteq\Sigma^{\ast}\) son conjuntos no vacios. Entonces \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}\) es \(\Sigma\)-efectivamente enumerable sii \(S_{1},...,S_{n},L_{1},...,L_{m}\) son \(\Sigma\)-efectivamente enumerables
3.10. Si \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\) es \(\Sigma\)-efectivamente computable entonces \(S\) es \(\Sigma\)-efectivamente enumerable.
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 en la materia (Proposicion 4.15), hay conjuntos que son \(\Sigma\)-efectivamente enumerables y no \(\Sigma\)-efectivamente computables. Sin envargo tenemos el siguiente interesante resultado:
3.1. Sea \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\). Son equivalentes
adhocprefix(a)adhocsufix \(S\) es \(\Sigma\)-efectivamente computable
adhocprefix(b)adhocsufix \(S\) y \((\omega^{n}\times\Sigma^{\ast m})-S\) son \(\Sigma\)-efectivamente enumerables
Proof. (a)\(\Rightarrow\)(b). Por el lema anterior tenemos que \(S\) es \(\Sigma\)-efectivamente enumerable. Notese ademas que, dado que \(S\) es \(\Sigma\)-efectivamente computable, \((\omega^{n}\times\Sigma^{\ast m})-S\) tambien 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}\) son igual al conjunto vacio. 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 facil 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 mensionadas, aumentar en \(1\) el valor de la variable \(T\) y dirijirse 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 ademas que \(n+m\geq1\). Entonces denotaremos con \(F_{(i)}\) a la funcion \(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. Ademas notese que \[F=[F_{(1)},...,F_{(n+m)}]\]
3.2. Dado \(S\subseteq\omega^{n}\times\Sigma^{\ast m}\), son equivalentes
adhocprefix(1)adhocsufix \(S\) es \(\Sigma\)-efectivamente enumerable
adhocprefix(2)adhocsufix \(S=I_{F}\), para alguna \(F:D_{F}\subseteq\omega^{k}\times\Sigma^{\ast l}\rightarrow\omega^{n}\times\Sigma^{\ast m}\) tal que cada \(F_{(i)}\) es \(\Sigma\)-efectivamente computable.
adhocprefix(3)adhocsufix \(S=D_{f}\), para alguna funcion \(f\) la cual es \(\Sigma\)-efectivamente computable.
Proof. El caso \(n=m=0\) es facil y es dejado al lector. Supongamos entonces que \(n+m\geq1\).
(1)\(\Rightarrow\)(2) es trivial.
(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 funcion \(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 termino 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 dirijirse a la Etapa 2. Si algun procedimiento \(\mathbb{P}_{i}\) al cabo de los \(t\) pasos no termino, entonces aumentar en \(1\) el valor de la variable \(T\) y dirijirse 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.
3.11. Sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Supongamos \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) es \(\Sigma\)-efectivamente computable y \(S\subseteq I_{f}\) es \(\Sigma\)-efectivamente enumerable, entonces \(f^{-1}(S)=\{(\vec{x},\vec{\alpha}):f(\vec{x},\vec{\alpha})\in S\}\) es \(\Sigma\)-efectivamente enumerable
3.12. Sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Supongamos \(f:D_{f}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\) es \(\Sigma\)-efectivamente computable y \(S\subseteq D_{f}\) es \(\Sigma\)-efectivamente enumerable, entonces \(f|_{S}\) es \(\Sigma\)-efectivamente computable