Siguiente: Tiempos y espacios Un nivel arriba: Complejidades de tiempo y Anterior: Complejidades de tiempo y

Dispositivos de cómputo

Consideraremos una clase ${\cal C}$ de dispositivos de cómputo, los cuales pueden ser

• máquinas de Turing,
• programas de alto nivel, digamos ``C'',
• funciones recursivas,
• máquinas RAM,
• etc.

Como cada dispositivo de cómputo es un programa, es decir, es una cadena de longitud finita sobre un alfabeto finito, tenemos que ${\cal C}$ es numerable ${\cal C}=\left(M_i\right)_{i\in N}.$ Por otro lado, las entradas posibles a los dispositivos en ${\cal C}$ son cadenas de longitud finita sobre un alfabeto de entrada (usualmente Dos={0,1}). Por tanto las entradas también son numerables. Para un dispositivo M y una entrada $\mbox{\bf x}$ hacemos

$$M(\mbox{\bf x})=\left\{\begin{array}{ll} \mbox{\bf y} & \mbo... ...se para con $\mbox{\bf x}$.\end{minipage}} \end{array}\right.$$

Supondremos además que la clase ${\cal C}$ posee un dispositivo universal, es decir, que hay un $M_0\in {\cal C}$ tal que

$$M_0(\lceil M \rceil\cdot\mbox{\bf x}) = M(\mbox{\bf x}),\;\;\;\forall M,\mbox{\bf x},$$

donde $M\mapsto \lceil M \rceil$ es una codificación de dispositivos en la clase ${\cal C}$. Una función $f:N^m\rightarrow N^n$ es computable-${\cal C}$ si $\exists M_f\in {\cal C}\ \forall \mbox{\bf x}\in N^m:\;M_f(\mbox{\bf x})=f(\mbox{\bf x}).$