3.3 Conjuntos $\Sigma$-efectivamente enumerables

Un conjunto $S\subseteq {\omega }^n\times {\Sigma }^{\ast m}$ sera llamado $\Sigma$-efectivamente enumerable cuando sea vacio o haya una funcion $F:\omega \to {\omega }^n\times {\Sigma }^{\ast m}$ tal que $I_F=S$ y $F_{\left(i\right)}$ sea $\Sigma$-efectivamente computable, para cada $i\in \{1,...,n+m\}$. Notese que para el caso $n=m=0$, la condicion de que $F_{\left(i\right)}$ 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 }^{\ast 0}=\left\{◊\right\}$ sera $\Sigma$-efectivamente enumerable sii es vacio o hay una funcion $\Sigma$-efectivamente computable $F:\omega \to \left\{◊\right\}$, tal que $I_F=S$. Por supuesto, esto nos dice que $\varnothing$ y $\left\{◊\right\}$ son $\Sigma$-efectivamente enumerables.

El siguiente resultado nos permite entender mejor la idea subyacente a esta definicion.

Proof. El caso $n=m=0$ es facil y es dejado al lector. Supongamos entonces que $n+m\ge 1$.

($\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 \to {\omega }^n\times {\Sigma }^{\ast m}$ tal que $I_F=S$ y cada $F_{\left(i\right)}$ es $\Sigma$-efectivamente computable. Para cada $i\in \{1,...,n+m\}$ sea $P_i$ un procedimiento efectivo que compute a $F_{\left(i\right)}$. Notar que cada $P_i$ tiene a $\omega$ como conjunto de datos de entrada y siempre termina. Sea $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 $P_1$ con dato de entrada $x$ y alojar el dato de salida en la variable $X_1$

Etapa 2: Correr $P_2$ con dato de entrada $x$ y alojar el dato de salida en la variable $X_2$

$⋮$

Etapa $n$: Correr $P_n$ con dato de entrada $x$ y alojar el dato de salida en la variable $X_n$

Etapa $n+1$: Correr $P_{n+1}$ con dato de entrada $x$ y alojar el dato de salida en la variable $A_1$

Etapa $n+2$: Correr $P_{n+2}$ con dato de entrada $x$ y alojar el dato de salida en la variable $A_2$

$⋮$

Etapa $n+m$: Correr $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 $P$ es efectivo y cumple las propiedades (1), (2) y (3).

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

Etapa 1: Correr $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 $P$ cumpla (1), (2) y (3) del lema anterior, diremos que $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 $P$ el cual tiene conjunto de datos de entrada $\omega$ y ademas para los sucesivos datos de entrada $0,1,2,3,...$, el procedimiento $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\ne j$.

Algunos ejemplos:

1. E${}_1$ El conjunto $S=\{x\in \omega :x$ es par$\}$ es $\Sigma$-efectivamente enumerable, cualesquiera sea $\Sigma$. El siguiente procedimiento enumera a $S$:

   1. - Calcular $2x$, darlo como dato de salida y terminar.

2. E${}_2$ 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\ne 0$, 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$.

3. E${}_3$ Veamos que ${\omega }^2\times {\Sigma }^{\ast 3}$ es $\Sigma$-efectivamente enumerable cualquiera sea el alfabeto no vacio $\Sigma$. Sea $\le$ un orden total para el alfabeto $\Sigma$. Utilisando el orden $\le$ podemos diseñar el siguiente procedimiento para enumerar ${\omega }^2\times {\Sigma }^{\ast 3}$:

   Etapa 1

   Si $x=0$, dar como salida $(0,0,\epsilon ,\epsilon ,\epsilon )$ y terminar. Si $x\ne 0$, calcular

   $x_1=(x{)}_1$

   $x_2=(x{)}_2$

   ${\alpha }_1={\ast }^{\le }\left(\right(x{)}_3)$

   ${\alpha }_2={\ast }^{\le }\left(\right(x{)}_4)$

   ${\alpha }_3={\ast }^{\le }\left(\right(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 vacio es trivial. Supongamos que ambos conjuntos son no vacios y sean $P_1$ y $P_2$ procedimientos que enumeran a $S_1$ y $S_2$. El siguiente procedimiento enumera al conjunto $S_1\cup S_2$:

1. - Si $x$ es par realizar $P_1$ partiendo de $x/2$ y dar el elemento de $S_1$ obtenido como salida. Si $x$ es impar realizar $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=\varnothing$ 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 $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 $P$ con dato de entrada $x$, para obtener un par $(x_1,x_2)\in \omega \times \omega$.

Etapa 2

Realizar $P_1$ con dato de entrada $x_1$ para obtener un elemento $e_1\in S_1$

Etapa 3

Realizar $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\ne \varnothing$. Sea $(\overrightarrow{z},\gamma )\in S$, fijo. Sea $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 }^{\ast 3}$ es $\Sigma$-efectivamente enumerable. En forma similar se puede ver que ${\omega }^n\times {\Sigma }^{\ast m}$ lo es. Sea $P_1$ un procedimiento efectivo que enumera a ${\omega }^n\times {\Sigma }^{\ast m}$. Entonces el siguiente procedimiento enumera a $S$:

Etapa 1

Realizar $P_1$ con $x$ de entrada para obtener $(\overrightarrow{x},\overrightarrow{\alpha })\in {\omega }^n\times {\Sigma }^{\ast m}$.

Etapa 2

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

Etapa 3

Si $e=1$ dar como dato de salida $(\overrightarrow{x},\overrightarrow{\alpha }).$ Si $e=0$ dar como dato de salida $(\overrightarrow{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:

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=\varnothing$ 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 $P_1$ un procedimiento efectivo que enumere a $S$ y sea $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 $P_1$ con el valor de $T$ como entrada para obtener de salida la upla $(\overrightarrow{y},\overrightarrow{\beta })$.

Etapa 3

Realizar $P_2$ con el valor de $T$ como entrada para obtener de salida la upla $(\overrightarrow{z},\overrightarrow{\gamma })$.

Etapa 4

Si $(\overrightarrow{y},\overrightarrow{\beta })=(\overrightarrow{x},\overrightarrow{\alpha })$, entonces detenerse y dar como dato de salida el valor $1$. Si $(\overrightarrow{z},\overrightarrow{\gamma })=(\overrightarrow{x},\overrightarrow{\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}\to {\omega }^n\times {\Sigma }^{\ast m}$. Supongamos ademas que $n+m\ge 1$. Entonces denotaremos con $F_{\left(i\right)}$ a la funcion $p_i^{n,m}\circ F$. Notar que $$\begin{array}{cc}{F}_{\left(i\right)}& :D_F\subseteq {\omega }^k\times {\Sigma }^{\ast l}\to \omega \text{, para cada}i=1,...,n\\ F_{\left(i\right)}& :D_F\subseteq {\omega }^k\times {\Sigma }^{\ast l}\to {\Sigma }^{\ast }\text{, para cada}i=n+1,...,n+m\end{array}$$ Por lo cual cada una de las funciones $F_{\left(i\right)}$ son $\Sigma$-mixtas. Ademas notese que $$F=[F_{\left(1\right)},...,F_{(n+m)}]$$

Proof. El caso $n=m=0$ es facil y es dejado al lector. Supongamos entonces que $n+m\ge 1$.

(1)$\Rightarrow$(2) es trivial.

(2)$\Rightarrow$(3). Para $i=1,...,n+m$, sea $P_i$ un procedimiento el cual computa a $F_{\left(i\right)}$ y sea $P$ un procedimiento el cual enumere a $\omega \times {\omega }^k\times {\Sigma }^{\ast l}.$ El siguiente procedimiento computa la funcion $f:I_F\to \left\{1\right\}$:

Etapa 1

Darle a la variable $T$ el valor 0.

Etapa 2

Hacer correr $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 $P_i$ durante $t$ pasos, con dato de entrada $(z_1,...,z_k,{\gamma }_1,...,{\gamma }_l).$ Si cada procedimiento $P_i$ al cabo de los $t$ pasos termino y dio como resultado el valor $o_i$, entonces comparar $(\overrightarrow{x},\overrightarrow{\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 $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\ne \varnothing$. Sea $(\overrightarrow{z},\overrightarrow{\gamma })$ un elemento fijo de $S$. Sea $P$ un procedimiento el cual compute a $f$. Sea $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.