Siguiente: Esquema de composición Un nivel arriba: Conceptos básicos Anterior: Tesis de Church

Propiedades de cerradura de funciones computables

En la sección anterior introdujimos a las funciones computables como aquellas que son calculables por programas-while . En esta sección presentaremos algunas propiedades de cerradura de las funciones computables, vale decir, presentaremos algunos esquemas de composición de funciones tales que actuando sobre funciones computables dan, también, funciones computables. Veremos también que, aunque la clase de funciones computables es muy grande, es numerable. Esto, con un simple argumento de cardinalidad de conjuntos, implica que hay una gran cantidad de funciones de los naturales en los naturales que no son computables.


Si A y B son dos conjuntos, escribiremos

$$B^A=\{f:A\rightarrow B\vert f\mbox{\rm es una funci\'on}\}$$

para denotar a las funciones con dominio en A y contradominio en B.