3.2 Conjuntos $\Sigma$-efectivamente computables

Un conjunto $S\subseteq {\omega }^n\times {\Sigma }^{\ast m}$ sera llamado $\Sigma$-efectivamente computable cuando la funcion ${\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 $P$, el cual computa ${\chi }_S^{{\omega }^n\times {\Sigma }^{\ast m}}$, es decir:

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

2. - Dado $(\overrightarrow{x},\overrightarrow{\alpha })\in {\omega }^n\times {\Sigma }^{\ast m}$, $P$ da como salida al numero $1$ si $(\overrightarrow{x},\overrightarrow{\alpha })\in S$ y al numero $0$ si $(\overrightarrow{x},\overrightarrow{\alpha })\notin S$.

Notese que esta definicion para el caso $S=\varnothing$ tiene a priori cierta ambiguedad ya que cualesquiera sean $n,m\in \omega$ tenemos que $\varnothing \subseteq {\omega }^n\times {\Sigma }^{\ast m}$. De todas maneras, cualesquiera sean los $n,m$ elejidos, siempre hay un procedimiento efectivo que computa a ${\chi }_{\varnothing }^{{\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 $\varnothing$ es $\Sigma$-efectivamente computable cualesquiera sea el alfabeto $\Sigma$. Cabe destacar que para el caso de un conjunto $S\ne \varnothing$, nuestra definicion es inambigua ya que hay unicos $n,m\in \omega$ tales que $S\subseteq {\omega }^n\times {\Sigma }^{\ast m}$.

Si $P$ es un procedimiento efectivo el cual computa a ${\chi }_S^{{\omega }^n\times {\Sigma }^{\ast m}}$, diremos que $P$ decide la pertenecia a $S$, con respecto al conjunto ${\omega }^n\times {\Sigma }^{\ast m}$.

Dejamos al lector la facil prueba del siguiente resultado.

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

Proof. Notese que si $n=m=0$, entonces $S_1\times ...\times S_n\times L_1\times ...\times L_m=\left\{◊\right\}$ el cual es $\Sigma$-efectivamente computable por lo cual el lema se cumple. Vemos entonces el caso $n+m\ge 1$. Para hacer mas lejible la prueba haremos el caso $n=m=1$. La prueba general es completamente analoga.

($\Rightarrow$) Ya que $S_1$ y $L_1$ son conjuntos no vacios, 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. Notese 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$$ Por lo tanto, es facil 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 facil, 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 }}$.