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 \(\mathbb{P}\), el cual computa \(\chi_{S}^{\omega^{n}\times\Sigma^{\ast m}}\), es decir:
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\}\).
adhocprefix-adhocsufix Dado \((\vec{x},\vec{\alpha})\in\omega^{n}\times\Sigma^{\ast m}\), \(\mathbb{P}\) da como salida al numero \(1\) si \((\vec{x},\vec{\alpha})\in S\) y al numero \(0\) si \((\vec{x},\vec{\alpha})\notin S\).
Notese que esta definicion para el caso \(S=\emptyset\) tiene a priori cierta ambiguedad 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\) elejidos, 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 definicion es inambigua ya que hay unicos \(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 pertenecia a \(S\), con respecto al conjunto \(\omega^{n}\times\Sigma^{\ast m}\).
Dejamos al lector la facil prueba del siguiente resultado.
3.5. Sean \(S_{1},S_{2}\subseteq\omega^{n}\times\Sigma^{\ast m}\) conjuntos \(\Sigma\)-efectivamente computables. Entonces \(S_{1}\cup S_{2},S_{1}\cap S_{2}\) y \((\omega^{n}\times\Sigma^{\ast m})-S_{1}\) son \(\Sigma\)-efectivamente computables.
El siguiente lema caracteriza cuando un conjunto rectangular es \(\Sigma\)-efectivamente computable
3.6. 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 computable sii \(S_{1},...,S_{n},L_{1},...,L_{m}\) son \(\Sigma\)-efectivamente computables
Proof. Notese que si \(n=m=0\), entonces \(S_{1}\times...\times S_{n}\times L_{1}\times...\times L_{m}=\{\Diamond\}\) el cual es \(\Sigma\)-efectivamente computable por lo cual el lema se cumple. Vemos entonces el caso \(n+m\geq1\). 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\text{ }\] 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}}\).