Siguiente: Máquina Universal de Turing Un nivel arriba: Universalidad Anterior: Numerabilidad de la clase

  
La noción de ``Universalidad''

Para una clase de funciones dada, puede existir una función con un argumento más tal que ese argumento sea un parámetro para seleccionar todas y cada una de las funciones en esa clase. Tal función que parametriza a la clase se dice ser universal. De manera más formal: Sea ${\cal F}=\left\{f_n\right\}_{n\geq 0}$ una clase numerable de funciones $I\!\!N\rightarrow I\!\!N$. La función $U_{{\cal F}}:(n,m)\mapsto f_n(m)$ se dice ser universal para ${\cal F}$. La clase ${\cal F}$ se autorrepresenta si $U_{{\cal F}}\in {\cal F}$. Consideremos la enumeración efectiva de los programas-while $\Phi:n\mapsto P_n$ vista en la sección 3.4.1. La función $U:(n,m)\mapsto \Phi(n)(m)$ es entonces universal para los programas-while .


Veremos que los sistemas que se autorrepresentan son formalmente incompletos, es decir:

• contendrán programas que no den ninguna respuesta en algunos puntos, es decir, que divergen en esos puntos, en otras palabras, hay programas que poseen un dominio incluído propiamente en su contraimagen, y
• dentro de ellos se puede plantear problemas que no son resolubles por ningún programa en tal sistema, es decir, se puede formular problemas irresolubles.

Para concluir la presente sección mostraremos el primer punto. Un programa, y consecuentemente la función que calcula, se dice ser parcial si diverge en algunos puntos. Para esto, observamos que un programa universal en un sistema que se autorrepresenta hace la simulación de programas sobre datos manejando únicamente códigos. El uso de códigos es irrelevante, en el sentido de que es indiferente utilizar códigos o no, según se ve en el siguiente

Lema 4.2 (de Reescritura)   Si $h:I\!\!N\longrightarrow I\!\!N$ se calcula por un programa, entonces

$$\exists\; n_h\in I\!\!N\;\forall n\in I\!\!N:\; \lfloor n_h\rfloor(\lfloor n\rfloor)=h(n).$$ (15)

En efecto, tenemos que las funciones de codificación pueden describirse en el sistema de programas y que éste es cerrado bajo la composición de funciones. Luego, dado el programa $h\in \mbox{\rm\rm Programas-{\bf while }}$, la función $g:m\mapsto h(\lceil m\rceil)$ es programable, por tanto posee un índice en el sistema, es decir $\exists\; n_h\in I\!\!N:\; \lfloor n_h\rfloor=g.$ Tenemos pues que $\forall n\in I\!\!N$ valen las igualdades siguientes: $\lfloor n_h\rfloor(\lfloor n\rfloor)=g(\lfloor n\rfloor)=h(\lceil \lfloor n\rfloor\rceil)=h(n).$ Aquí me permito enfatizar que, mientras que del lado derecho de la ecuación en 3.5, tenemos el valor de h en el valor n, en su lado izquierdo, tenemos al valor de la n_h-ésima función computable aplicada sobre el n-ésimo posible argumento.

Lema 4.3 (de la Diagonal)   En todo sistema que se autorrepresenta existen funciones computables parciales.

En efecto, al ser el sistema autorrepresentable, la función U es computable, luego la función $g:n\mapsto U(n,n)+1$ es programable (obsérvese que U(n,n) es el valor en n del n-ésimo programa). Por el Lema de Reescritura se tiene que $\exists\; n_0\in I\!\!N\;\forall n\in I\!\!N:\; \lfloor n_0\rfloor(\lfloor n\rfloor)=g(n).$ Es decir $\forall n\in I\!\!N:\; \lfloor n_0\rfloor(\lfloor n\rfloor)=\lfloor n\rfloor(\lfloor n\rfloor)+1.$ Así que para n=n₀, se ha de tener $\lfloor n_0\rfloor(\lfloor n_0\rfloor)=\lfloor n_0\rfloor(\lfloor n_0\rfloor)+1.$ Esto obliga a que necesariamente $\lfloor n_0\rfloor(\lfloor n_0\rfloor)\uparrow.$ Así pues la n₀-ésima función es parcial.
Siguiente: Máquina Universal de Turing Un nivel arriba: Universalidad Anterior: Numerabilidad de la clase