next up previous contents
Siguiente: Numerabilidad de las funciones Un nivel arriba: Propiedades de cerradura de Anterior: Esquema de recursión acotada

Computabilidad de los esquemas

Proposición 8.1   Si $g,f_1,\ldots,f_k,f,h,c$ son computables, entonces

\begin{displaymath}\begin{array}{lclc} \mbox{\it Comp}(g;f_1,\ldots,f_k)&, & &\... ...cu}(g;h) &\mbox{\rm y } & \mbox{\it ReAc}(g;h;c)&. \end{array}\end{displaymath}

son computables también.

En la Figura 1.7 presentamos un seudocódigo para calcular la composición de funciones. En la Figura 1.8 presentamos sendos seudocódigos para calcular el esquema de minimización (incondicional) y el correspondiente acotado. En la Figura 1.9 presentamos sendos seudocódigos recursivos para calcular el esquema de recursión (incondicional) y el correspondiente acotado, sin embargo no hemos introducido la noción de programa-while recursivo. En la Figura 1.10 presentamos otros seudocódigos para estos mismos esquemas utilizando únicamente macros ya introducidos. A partir de tales ejemplos el lector podrá observar la transformación que se ha de hacer sobre los programas recursivos para obtener programas-while equivalentes.
  
Figure 1.7: Seudocódigo correspondiente al Esquema de Composición.
\fbox{\begin{minipage}[t]{22em} \vspace{2ex} \noindent {\bf Input:} \ \ \... ...pace ;\\ \> $r:=g(y_1,\ldots,y_k)$\space \\ \} \end{tabbing} \end{minipage}}


  
Figure 1.8: Seudocódigos correspondientes a los Esquemas de Minimización.
\fbox{\begin{minipage}[t]{22em} \vspace{2ex} \noindent {\bf Input:} \ \ \ \beg... ...e {\bf do }$y++$\space ; \\ \> $r:=y$\space \} \end{tabbing} \end{minipage}} \fbox{\begin{minipage}[t]{22em} \vspace{2ex} \noindent {\bf Input:} \ \ \ \beg... ...e {\bf do }$y++$\space ; \\ \> $r:=y$\space \} \end{tabbing} \end{minipage}}


  
Figure 1.9: Seudocódigos recursivos correspondientes a los Esquemas de Recursión.
\fbox{\begin{minipage}[t]{22em} \vspace{2ex} \noindent {\bf Input:} \ \ \ \beg... ...>\>$r:=h(\mbox{\bf x},y,w)$\space \\ \>\}\\ \} \end{tabbing} \end{minipage}} \fbox{\begin{minipage}[t]{22em} \vspace{2ex} \noindent {\bf Input:} \ \ \ \beg... ...$\space {\bf then }$r:=r_1$\space \\ \>\}\\ \} \end{tabbing} \end{minipage}}


  
Figure 1.10: Seudoprogramas- while correspondientes a los Esquemas de Recursión.
\fbox{\begin{minipage}[t]{22em} \vspace{2ex} \noindent {\bf Input:} \ \ \ \beg... ...e ; $y_0++$\space \}\\ \> $r:=r_0$\space \\ \} \end{tabbing} \end{minipage}} \fbox{\begin{minipage}[t]{22em} \vspace{2ex} \noindent {\bf Input:} \ \ \ \beg... ...\bf x},y)$\space {\bf then }$r:=r_0$\space \\ \} \end{tabbing} \end{minipage}}

next up previous contents
Siguiente: Numerabilidad de las funciones Un nivel arriba: Propiedades de cerradura de Anterior: Esquema de recursión acotada
Guillermo Morales-Luna
2000-07-10