Hay muchos procesos constructivos que nos sirven para definir o construir una función en términos de otras funciones dadas. Un ejemplo de esto es la composición de funciones, la cual dadas dos funciones \(f,g\) nos permite construir su composición, a saber \(f\circ g\). Otro ejemplo es el constructor de predicados que dados dos predicados \(\Sigma\)-mixtos \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\{0,1\}\), con el mismo dominio, nos define el predicado \[\begin{array}{rll} (P\vee Q):S & \rightarrow & \omega\\ (\vec{x},\vec{\alpha}) & \rightarrow & \left\{ \begin{array}{lll} 1 & & \text{si }P(\vec{x},\vec{\alpha})=1\text{ o }Q(\vec{x},\vec{\alpha})=1\\ 0 & & \text{caso contrario} \end{array}\right. \end{array}\] Otro constructor muy importante que utilizaremos mucho es aquel que a partir de funciones \(f_{i}:D_{f_{i}}\rightarrow O\), \(i=1,...,k\), tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\), nos define la nueva función \(f_{1}\cup...\cup f_{k}\), la cual cumple \[\begin{array}{rll} D_{f_{1}}\cup...\cup D_{f_{k}} & \rightarrow & O\\ e & \rightarrow & \left\{ \begin{array}{clc} f_{1}(e) & & \text{si }e\in D_{f_{1}}\\ \vdots & & \vdots\\ f_{k}(e) & & \text{si }e\in D_{f_{k}} \end{array}\right. \end{array}\] Veremos a continuación que estos constructores preservan la computabilidad efectiva en el sentido que si las funciones iniciales son \(\Sigma\)-efectivamente computables, entonces la construida también lo es.
3.9. Si \(P:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) y \(Q:S\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow\omega\) son predicados \(\Sigma\)-efectivamente computables, entonces \((P\vee Q)\), \((P\wedge Q)\) y \(\lnot P\) lo son también.
Dadas funciones \(\Sigma\)-mixtas \(f,f_{1},...,f_{r}\), con \(r\geq1\), diremos que la función \(f\circ[f_{1},...,f_{r}]\) es obtenida por composición a partir de las funciones \(f,f_{1},...,f_{r}\). Para probar que la composición preserva la computabilidad efectiva necesitaremos el siguiente lema.
3.10. Supongamos que \(f,f_{1},...,f_{r}\) son funciones \(\Sigma\)-mixtas, con \(r\geq1\). Supongamos además que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\). Entonces hay \(n,m,k,l\in\omega\) y \(s\in\{\#,\ast\}\) tales que
adhocprefix-adhocsufix \(r=n+m\)
adhocprefix-adhocsufix \(f\) es de tipo \((n,m,s)\)
adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\)
adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\)
Mas aun, en tal caso la función \(f\circ[f_{1},...,f_{n+m}]\) es de tipo \((k,l,s)\) y: \[\begin{aligned} D_{f\circ[f_{1},...,f_{n+m}]} & =\left\{ (\vec{x},\vec{\alpha})\in\bigcap_{i=1}^{n+m}D_{f_{i}}:(f_{1}(\vec{x},\vec{\alpha}),...,f_{n+m}(\vec{x},\vec{\alpha}))\in D_{f}\right\} \\ f\circ[f_{1},...,f_{n+m}](\vec{x},\vec{\alpha}) & =f(f_{1}(\vec{x},\vec{\alpha}),...,f_{n+m}(\vec{x},\vec{\alpha})). \end{aligned}\]
Proof. Nótese que \(f\neq\emptyset\) y \([f_{1},...,f_{r}]\neq\emptyset\) (por que?). Ya que \(f\neq\emptyset\) tenemos que hay únicos \(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}]\neq\emptyset\) y \(I_{[f_{1},...,f_{r}]}\subseteq I_{f_{1}}\times...\times I_{f_{r}}\), tenemos que
adhocprefix-adhocsufix \(r=n+m\)
adhocprefix-adhocsufix \(I_{f_{i}}\subseteq\omega\), para cada \(i=1,...,n\)
adhocprefix-adhocsufix \(I_{f_{i}}\subseteq\Sigma^{\ast}\), para cada \(i=n+1,...,n+m\)
Ya que \([f_{1},...,f_{r}]\neq\emptyset\) tenemos que \(D_{[f_{1},...,f_{r}]}=\bigcap_{i=1}^{r}D_{f_{i}}\neq\emptyset\), por lo cual los conjuntos \(D_{f_{1}},...,D_{f_{n+m}}\) deberán 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 últimas observaciones del lema son directas de las definiciones de \([f_{1},...,f_{n+m}]\) y de composición de funciones
Ahora sí podemos probar fácilmente que se preserva la computabilidad efectiva cuando componemos
3.11. Si \(f,f_{1},...,f_{r}\), con \(r\geq1\), son \(\Sigma\)-efectivamente computables, entonces \(f\circ[f_{1},...,f_{r}]\) lo es.
Proof. Si \(f\circ[f_{1},...,f_{r}]=\emptyset\), entonces claramente es \(\Sigma\)-efectivamente computable. Supongamos entonces que \(f\circ[f_{1},...,f_{r}]\neq\emptyset\). Por el lema anterior hay \(n,m,k,l\in\omega\) y \(s\in\{\#,\ast\}\) tales que
adhocprefix-adhocsufix \(r=n+m\)
adhocprefix-adhocsufix \(f\) es de tipo \((n,m,s)\)
adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\#)\), para cada \(i=1,...,n\)
adhocprefix-adhocsufix \(f_{i}\) es de tipo \((k,l,\ast)\), para cada \(i=n+1,...,n+m\)
Sean \(\mathbb{P},\mathbb{P}_{1},...,\mathbb{P}_{n+m}\) procedimientos efectivos los cuales computen las funciones \(f,f_{1},...,f_{n+m}\), respectivamente. Usando estos procedimientos es fácil definir un procedimiento efectivo el cual compute a \(f\circ[f_{1},...,f_{n+m}]\).
Recordemos que si \(f_{i}:D_{f_{i}}\rightarrow O\), \(i=1,...,k\), son funciones tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\), entonces \(f_{1}\cup...\cup f_{k}\) es la función \[\begin{array}{rll} D_{f_{1}}\cup...\cup D_{f_{k}} & \rightarrow & O\\ e & \rightarrow & \left\{ \begin{array}{clc} f_{1}(e) & & \text{si }e\in D_{f_{1}}\\ \vdots & & \vdots\\ f_{k}(e) & & \text{si }e\in D_{f_{k}} \end{array}\right. \end{array}\]
3.12. Sean \(n,m\in\omega\) y \(O\in\{\omega,\Sigma^{\ast}\}\). Supongamos \(f_{i}:D_{f_{i}}\subseteq\omega^{n}\times\Sigma^{\ast m}\rightarrow O\), \(i=1,...,k\), son funciones \(\Sigma\)-efectivamente computables tales que \(D_{f_{i}}\cap D_{f_{j}}=\emptyset\) para \(i\neq j\). Entonces \(f_{1}\cup...\cup f_{k}\) es \(\Sigma\)-efectivamente computable.
Proof. Haremos el caso \(O=\Sigma^{\ast}\) y \(k=2\). Sean \(\mathbb{P}_{1}\) y \(\mathbb{P}_{2}\) procedimientos efectivos que computen a \(f_{1}\) y \(f_{2}\), respectivamente. Sea \(\mathbb{P}\) el procedimiento efectivo siguiente:
- Conjunto de datos de entrada de \(\mathbb{P}\) igual a \(\omega^{n}\times\Sigma^{\ast m}\)
- Conjunto de datos de salida de \(\mathbb{P}\) contenido en \(\Sigma^{\ast}\)
- Funcionamiento:
Etapa 1
Hacer \(T=1\)
Etapa 2
Correr el procedimiento \(\mathbb{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 \(\mathbb{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 \(\mathbb{P}\) computa a la función \(f_{1}\cup f_{2}\).