Siguiente: Máquinas de Turing Un nivel arriba: Conceptos básicos Anterior: Reglas de transformación

Funciones computables

Las funciones computables son las que se calculan por programas-while . Si P es un programa-while y $[x_1\ldots x_k]$ es la lista de variables en P entonces consideraremos a las primeras variables como variables de entrada y a las últimas como de salida, de manera sólo un poco más precisa, para $n,m\in N$ consideraremos

$$\begin{eqnarray*}\mbox{\bf x}_n={[x_1\ldots x_n]} &:&\mbox{\rm lista de variable... ... x_{k-1}x_k]} &:&\mbox{\rm lista de variables de {\em salida}} \end{eqnarray*}$$

El programa P calcula, o computa, a la función

$$\begin{eqnarray*}f_{P,n,m}:I\!\!N^n &\rightarrow& I\!\!N^m \\ \left.\mbox{\bf ... ...n &\mapsto& P\left(\left.\mbox{\bf x}\right\vert _n\right)^{-m} \end{eqnarray*}$$

donde

$$\left.\mbox{\bf x}\right\vert _n =\left\{\begin{array}{ll} {... ...}(\mbox{\bf x}) &\mbox{\rm en otro caso. } \end{array}\right.$$

En este caso definimos,

$$\begin{eqnarray*}\mbox{\it Dominio de $f$ }\hspace{1cm} \mbox{\rm dom}_n(P) &=&... ...\mbox{\it total} &\Leftrightarrow& \mbox{\rm dom}_n(P)=I\!\!N^n \end{eqnarray*}$$

En adelante omitiremos los subíndices n,m y k.



$f:I\!\!N^n \rightarrow I\!\!N^m$ es computable si existe un programa-while tal que f=f_P.