next up previous contents
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

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

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=fP.

Guillermo Morales-Luna
2000-07-10