Siguiente: Problema de la correspondencia Un nivel arriba: Irresolubilidad Anterior: Irresolubilidad

Teorema de Rice

Consideremos la clase de funciones recursivas con un solo argumento. Sea pues $\mbox{\it FRec}^1=\left\{f_k\right\}_{k\geq 0}$ una enumeración efectiva de las funciones computables de una sola variable. Sea ${\cal F}\subset\mbox{\it FRec}^1$ una subclase. El conjunto de índices de ${\cal F}$ es $R_{{\cal F}}=\{i\geq 0\vert f_i\in {\cal F}\}.$ La clase ${\cal F}$ se dice ser recursiva si su conjunto de índices $R_{{\cal F}}$ lo es, es decir, si la función característica de este último conjunto es recursiva.

Disgresión: Supongamos que f es una función computable, calculada por el programa P y que el índice de f es k₀. Sea ${\cal F}=\{f\}$ la mónada que consta únicamente de la función f. Tenemos que $\{k_0\}\subset R_{{\cal F}}$. Pero la inclusión es estricta, pues f puede ser calculada también por una infinidad de otros programas, es decir, f tiene una infinidad de índices. Para determinar que un número cualquiera k está en $R_{{\cal F}}$ será menester que la función f_k coincide con f, la verificación de lo cual es un problema irresoluble, en general, como lo veremos más adelante. La dificultad principal en revisar si acaso una función coincide con otra, estriba en que aún cuando podamos probar uno a uno, y, potencialmente todos, los valores de ambas funciones, ese proceso es interminable pues siempre quedarán más valores pendientes de revisar que los ya revisados.

Teorema 1.1 (Rice)   Ninguna subclase propia no vacía de funciones recursivas ${\cal F}\subset\mbox{\it FRec}^1$ puede ser recursiva. En otras palabras, si existen $f,g\in\mbox{\it FRec}^1$ tales que $f\in{\cal F}$ y $g\not\in{\cal F}$ entonces ${\cal F}$ no puede ser recursiva.

Demostración: Supongamos que ${\cal F}$ sea recursiva y que existen $f,g\in\mbox{\it FRec}^1$ tales que $f\in{\cal F}$ y $g\not\in{\cal F}$. Existe pues una función recursiva $P_{{\cal F}}\in \mbox{\it FRec}^1$ que coincide con la función característica de $R_{{\cal F}}$, es decir, tal que

$$P_{{\cal F}}(i)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $i\... ... F}}$, } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$$

Definamos $h:I\!\!N^2 \rightarrow I\!\!N$ de manera que

$$h(i,x)=\left\{\begin{array}{ll} g(x) &\mbox{\rm si $i\in R_{... ...}$, } \\ f(x) &\mbox{\rm en otro caso. } \end{array}\right.$$

h es recursiva pues se está definiendo por casos utilizando funciones recursivas. Por el Teorema de Parametrización, existe una función recursiva $s:N \rightarrow N$ tal que $\forall i,x:\ f_{s(i)}(x)=h(i,x).$ Por el Teorema de Recursión ha de existir un k₀ tal que f_k0=f_s(k0). Así pues, $\forall x:\ f_{k_0}(x)=h(k_0,x)$, vale decir,

$$\forall x:\ f_{k_0}(x)=\left\{\begin{array}{ll} g(x) &\mbox{... ...}$, } \\ f(x) &\mbox{\rm en otro caso. } \end{array}\right.$$

Ya que $f\in{\cal F}$ pero $g\not\in{\cal F}$ tenemos las equivalencias siguientes:

$$\begin{array}{rcccccc} k_0\in R_{{\cal F}}&\Leftrightarrow& ... ...l F} &\Leftrightarrow& k_0\not\in R_{{\cal F}} \end{array}$$

y esto es una contradicción.


Digamos que una clase de funciones es trivial si bien es vacía, o bien coincide con toda la clase $\mbox{\it FRec}^1$. El Teorema de Rice asevera pues que las únicas clases de funciones que son recursivas son precisamente las triviales.

Corolario 1.1   Las siguientes subclases de $\mbox{\it FRec}^1$ NO son en sí recursivas, es decir, no hay programa alguno para reconocer cuándo una función dada en $\mbox{\it FRec}^1$ cae en una de esas clases.

$$\begin{array}{lclclcl} \mbox{\it RP} &=&\left\{f\vert f\mbox... ...=&\left\{f\vert f\mbox{\rm es biyectiva.}\right\} \end{array}$$

El corolario se sigue de inmediato del teorema de Rice pues cada una de las subclases enlistadas es un subconjunto propio no-vacío de $\mbox{\it FRec}^1$.

Teorema 1.2 (Rice: Versión vectorial)   Sea ${\cal F}^m\subset\left(\mbox{\it FRec}^1\right)^m$ una familia de m-tuplas cuyas componentes son funciones recursivas. Sea $R_{{\cal F}^m}=\left\{(i_1,\ldots,i_m)\vert(f_{i_1},\ldots,f_{i_m})\in {\cal F}^m\right\}.$ Entonces $R_{{\cal F}^m}$ no puede ser recursivo a menos de que $R_{{\cal F}^m}$ sea trivial, es decir, $R_{{\cal F}^m}=\emptyset$ o $R_{{\cal F}^m}=I\!\!N^m$

Demostración: Sea $a_m:I\!\!N^m\rightarrow I\!\!N$ una biyección computable. Dado ${\cal F}^m$, definimos

$$S=\{i\in I\!\!N\vert\exists\mbox{\bf f}=(f_{i_1},\ldots,f_{i_m})\in {\cal F}^m:i=a_m(i_1,\ldots,i_m)\}.$$

Se tiene que $R_{{\cal F}^m}$ es recursivo si y sólo si S lo es, y S no es trivial si y sólo si $R_{{\cal F}^m}$ no lo es. Del Teorema de Rice se sigue que S no es recursivo.

Corolario 1.2   Las siguientes clases de funciones NO son recursivas.

$$\begin{array}{lclclcl} \mbox{\it Ig} &=&\left\{(f,g)\vert f=... ...\it OB} &=&\left\{(f,g,h)\vert h=g\oplus f\right\} \end{array}$$

donde $\oplus$ es, por ejemplo, una operación binaria computable.

El corolario se sigue de que las clases enlistadas no son triviales.

Se dice que una función g es una extensión de la función f, o que f es una restricción de g, si se cumple

$$\forall x:\ f(x)\downarrow\ \Rightarrow\ \left[g(x)\downarrow\ \land\ \left[g(x)=f(x)\right]\right].$$

g extiende propiamente a f si existe x₀ tal que $g(x_0)\downarrow$ pero $f(x_0)\uparrow$.

Teorema 1.3 (Primera extensión del Teorema de Rice)   Sea ${\cal F}\subset\mbox{\it FRec}^1$ una familia de funciones recursivas tal que existe una función $f\in{\cal F}$ con una extensión propia recursiva g que NO está en ${\cal F}$. Entonces el conjunto de índices $R_{{\cal F}}=\{i\geq 0\vert f_i\in {\cal F}\}$ no puede ser recursivamente enumerable.

Demostración: Sean f y g como en el enunciado del teorema. Sea $\left(f_i\right)_i$ una enumeración efectiva de las funciones recursivas. Consideremos la función $h:I\!\!N^2 \rightarrow I\!\!N$ tal que

$$h(i,x)=\left\{\begin{array}{ll} f(x) &\mbox{\rm si $f_i(i)\u... ...w$, } \\ g(x) &\mbox{\rm en otro caso. } \end{array}\right.$$

La función $i\mapsto f_i(i)$ es claramente computable, pues es la diagonal de una función universal. Sea P un programa que la calcule. Como f y g son recursivas, existen sendos programas Q₁,Q₂ que las calculan. La función h puede calcularse como sigue: Dado (i,n),

1.

calculamos P(i) y Q₁(x) en ``tiempo compartido'', como si se calculara $P(i)\land Q_1(x)$ según el procedimiento descrito en 3.4.6,

2.

si el cálculo de Q₁(x) termina primero, se da su valor como salida,

3.

si el cálculo de P(i) termina primero, se pasa a calcular Q₂(x) y se da su valor como salida.

Puesto que g es una extensión de f el procedimiento anterior calcula h(i,x). Por tanto, h es recursiva. Por el Teorema de Parametrización existe una función computable s tal que $\forall i,x:\ f_{s(i)}(x)=h(i,x).$ Así pues, $\forall i:[s(i)\in R_{{\cal F}}\Leftrightarrow f_i(i)\uparrow]$. Ahora bien, el conjunto $K=\{i\vert f_i(i)\downarrow\}$ bien que es recursivamente enumerable no es recursivo (éste aparece de manera esencial en el Problema de la Parada). Se tiene además que $\forall i:[s(i)\in R_{{\cal F}}\Leftrightarrow i\not\in K].$ Consecuentemente, si $R_{{\cal F}}$ fuera recursivamente enumerable entonces también lo sería el complemento de K y esto obligaría a que K fuera recursivo, lo cual no es posible.

Corolario 1.3   Las siguientes clases de funciones NO son recursivamente enumerables, es decir, no hay programa alguno para generar uno a uno a todos los elementos en una de esas clases.

$$\begin{array}{lclclcl} \mbox{\it To}^c &=&\left\{f\vert f\mb... ...vert f\mbox{\rm no es biyectiva.}\right\} &\ \ &\ \end{array}$$

En efecto, para cada una de esas clases se puede dar un ejemplo particular de una función f en la clase con una extensión fuera de ella.
Siguiente: Problema de la correspondencia Un nivel arriba: Irresolubilidad Anterior: Irresolubilidad