3.4 Algunos constructores que preservan computabilidad efectiva

Hay muchos procesos constructivos que nos sirven para definir o construir una funcion en terminos de otras funciones dadas. Un ejemplo de esto es la composicion de funciones, la cual dadas dos funciones $f,g$ nos permite construir su composicion, a saber $f\circ g$. Otro ejemplo es el contructor de predicados que dados dos predicados $\Sigma$-mixtos $P:S\subseteq {\omega }^n\times {\Sigma }^{\ast m}\to \{0,1\}$ y $Q:S\subseteq {\omega }^n\times {\Sigma }^{\ast m}\to \{0,1\}$, con el mismo dominio, nos define el predicado $$\begin{array}{ccc}(P\vee Q):S& \to & \omega \\ (\overrightarrow{x},\overrightarrow{\alpha })& \to & \{\begin{array}{ccc}1& & \text{si}P(\overrightarrow{x},\overrightarrow{\alpha })=1\text{o}Q(\overrightarrow{x},\overrightarrow{\alpha })=1\\ 0& & \text{caso contrario}\end{array}\end{array}$$ Otro constructor muy importante que utilizaremos mucho es aquel que a partir de funciones $f_i:D_{f_i}\to O$, $i=1,...,k$, tales que $D_{f_i}\cap D_{f_j}=\varnothing$ para $i\ne j$, nos define la nueva funcion $f_1\cup ...\cup f_k$, la cual cumple $$\begin{array}{ccc}{D}_{f_1}\cup ...\cup D_{f_k}& \to & O\\ e& \to & \{\begin{array}{ccc}{f}_1\left(e\right)& & \text{si}e\in D_{f_1}\\ ⋮& & ⋮\\ f_k\left(e\right)& & \text{si}e\in D_{f_k}\end{array}\end{array}$$ Veremos a continuacion que estos constructores preservan la computabilidad efectiva en el sentido que si las funciones iniciales son $\Sigma$-efectivamente computables, entonces la construida tambien lo es.

3.4.1 Composicion

Dadas funciones $\Sigma$-mixtas $f,f_1,...,f_r$, con $r\ge 1$, diremos que la funcion $f\circ [f_1,...,f_r]$ es obtenida por composicion a partir de las funciones $f,f_1,...,f_r$. Para probar que la composicion preserva la computabilidad efectiva necesitaremos el siguiente lema.

Proof. Notese que $f\ne \varnothing$ y $[f_1,...,f_r]\ne \varnothing$ (por que?). Ya que $f\ne \varnothing$ tenemos que hay unicos $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]\ne \varnothing$ y $I_{[f_1,...,f_r]}\subseteq I_{f_1}\times ...\times I_{f_r}$, tenemos que

1. - $r=n+m$

2. - $I_{f_i}\subseteq \omega$, para cada $i=1,...,n$

3. - $I_{f_i}\subseteq {\Sigma }^{\ast }$, para cada $i=n+1,...,n+m$

Ya que $[f_1,...,f_r]\ne \varnothing$ tenemos que $D_{[f_1,...,f_r]}={\bigcap }_{i=1}^r{D}_{f_i}\ne \varnothing$, por lo cual los conjuntos $D_{f_1},...,D_{f_{n+m}}$ deberan 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 ultimas observaciones del lema son directas de las definiciones de $[f_1,...,f_{n+m}]$ y de composicion de funciones  

Ahora si podemos probar facilmente que se preserva la computabilidad efectiva cuando componemos

Proof. Si $f\circ [f_1,...,f_r]=\varnothing$, entonces claramente es $\Sigma$-efectivamente computable. Supongamos entonces que $f\circ [f_1,...,f_r]\ne \varnothing$. Por el lema anterior hay $n,m,k,l\in \omega$ y $s\in \{\#,\ast \}$ tales que

1. - $r=n+m$

2. - $f$ es de tipo $(n,m,s)$

3. - $f_i$ es de tipo $(k,l,\#)$, para cada $i=1,...,n$

4. - $f_i$ es de tipo $(k,l,\ast )$, para cada $i=n+1,...,n+m$

Sean $P,P_1,...,P_{n+m}$ procedimientos efectivos los cuales computen las funciones $f,f_1,...,f_{n+m}$, respectivamente. Usando estos procedimientos es facil definir un procedimiento efectivo el cual compute a $f\circ [f_1,...,f_{n+m}]$.  

3.4.2 Lema de division por casos para funciones $\Sigma$-efectivamente computables

Recordemos que si $f_i:D_{f_i}\to O$, $i=1,...,k$, son funciones tales que $D_{f_i}\cap D_{f_j}=\varnothing$ para $i\ne j$, entonces $f_1\cup ...\cup f_k$ es la funcion $$\begin{array}{ccc}{D}_{f_1}\cup ...\cup D_{f_k}& \to & O\\ e& \to & \{\begin{array}{ccc}{f}_1\left(e\right)& & \text{si}e\in D_{f_1}\\ ⋮& & ⋮\\ f_k\left(e\right)& & \text{si}e\in D_{f_k}\end{array}\end{array}$$

Proof. Haremos el caso $O={\Sigma }^{\ast }$ y $k=2$. Sean $P_1$ y $P_2$ procedimientos efectivos que computen a $f_1$ y $f_2$, respectivamente. Sea $P$ el procedimiento efectivo siguiente:

- Conjunto de datos de entrada de $P$ igual a ${\omega }^n\times {\Sigma }^{\ast m}$

- Conjunto de datos de salida de $P$ contenido en ${\Sigma }^{\ast }$

- Funcionamiento:

Etapa 1

Hacer $T=1$

Etapa 2

Correr el procedimiento $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 $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 $P$ computa a la funcion $f_1\cup f_2$.