Siguiente: Decidibilidad Un nivel arriba: Teoría de la recursividad Anterior: Funciones recursivas

  
Problema de la parada

Teorema 2.1   No existe una función recursiva h tal que $\forall (k,m):$

$$h(k,m)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $f_k(m)\down... ...} \\ 0 &\mbox{\rm si $f_k(m)\uparrow$. } \end{array}\right.$$

Tal función h permitiría reconocer cuándo una función recursiva ha de converger para una instancia dada. Demostración: Supongamos que la función h fuera recursiva. Podemos definir a partir de ella una función recursiva h₁ tal que

$$h_1(k,m)=\left\{\begin{array}{ll} \perp &\mbox{\rm si $f_k(m... ...} \\ 0 &\mbox{\rm si $f_k(m)\uparrow$. } \end{array}\right.$$

Entonces $\forall (k,m):\ \left[h_1(k,m)\downarrow\ \Leftrightarrow\ f_k(m)\uparrow\right].$ Su función diagonal $h_2:k\mapsto h_1(k,k)$ es también recursiva. Para ella, $\forall k:\ \left[h_2(k)\downarrow\ \Leftrightarrow\ f_k(k)\uparrow\right].$ Al ser h₂ recursiva posee un índice, digamos k_h2. Entonces, $\forall k:\ \left[f_{k_{h_2}}(k)\downarrow\ \Leftrightarrow\ f_k(k)\uparrow\right]$. En particular, al considerar k=k_h2 hemos de tener $\left[f_{k_{h_2}}(k_{h_2})\downarrow\ \Leftrightarrow\ f_{k_{h_2}}(k_{h_2})\uparrow\right],$ lo que es claramente contradictorio.