Siguiente: Teoremas de recursión Un nivel arriba: Decidibilidad Anterior: Proyecciones

Problema de la parada (otra vez)

Para un conjunto $A\subset N^m$ consideremos el problema de decisión siguiente:


Problema $\Phi_A$:

Instancia: Un punto $\mbox{\bf x}\in N^m$.
Respuesta: $\left\{\begin{array}{ll} \mbox{\rm S\'\i} &\mbox{\rm si $\mbox{\bf x}\in A$ ,} \\ \mbox{\rm No} &\mbox{\rm en otro caso.} \\ \end{array}\right.$




Si A es un conjunto semidecidible el problema anterior es sólo resoluble a medias: Si g_A tiene como dominio a A entonces dado el punto $\mbox{\bf x}$ evaluamos en él a g_A. En el caso de que obtengamos un valor, contestamos que el punto pertenece a A pero en caso de no obtenerlo, no podremos saber si la falla en obtener valor alguno es debida a que efectivamente se carece de él o a que aún no concluye g_A su proceso de cálculo en $\mbox{\bf x}$. El problema de decisión en conjuntos semidecidibles es pues semidecidible. Para un conjunto decidible, su propia función característica es una algoritmo de solución del problema de decisión correspondiente. Así pues es altamente deseable contar con un procedimiento para identificar cuándo un programa ha de pararse para una entrada dada. Tal procedimiento es, sin embargo, inexistente.

Proposición 3.2 (Problema de la Parada)   Existen conjuntos semidecidibles que no son decidibles.

En efecto, sea U un programa universal para la clase de programas. Consideremos el conjunto de parejas correspondientes a programas y entradas en sus dominios de convergencia:

$$\mbox{\it Defin}=\{(k,m)\vert U(k,m)\downarrow\}.$$

Veamos que $\mbox{\it Defin}\in\mbox{\it RecEn}_2$ pero $\mbox{\it Defin}\not\in\mbox{\it Recur}_2.$ Consideremos el conjunto $\mbox{\it Buenos}=\{k\vert(k,k)\in\mbox{\it Defin}\}$ y su complemento $\mbox{\it Malos}=\{k\vert(k,k)\not\in\mbox{\it Defin}\}.$ k es pues bueno si k mismo hace converger al k-ésimo programa. En otro caso es malo. Así pues

$$\begin{array}{lclclcl} (k\in\mbox{\it Buenos}&\Leftrightarro... ...arrow& \lfloor k\rfloor(\lfloor k\rfloor)\uparrow) \end{array}$$

Si acaso se tuviera $\mbox{\it Defin}\in\mbox{\it Recur}_2$ entonces ambos conjuntos introducidos serían semidecidibles, es decir, $\mbox{\it Buenos},\mbox{\it Malos}\in\mbox{\it RecEn}_2.$ Luego $\mbox{\it Malos}$ sería el dominio de una función programable, es decir, $[\exists k_0\forall k: \lfloor k_0\rfloor(\lfloor k\rfloor)\downarrow \;\Leftrightarrow\;k\in \mbox{\it Malos}].$ En particular, para k=k₀ tendremos que ha de regir la equivalencia lógica $[k_0\in \mbox{\it Buenos}\;\Leftrightarrow\;\lfloor k_0\rfloor(\lfloor k_0\rfloor)\downarrow \Leftrightarrow\;k_0\in \mbox{\it Malos}]$ lo cual es, a todas luces, absurdo.


En conclusión: En cualquier sistema formal de cómputo que se autorrepresente podemos plantear el análogo al problema de la parada. Tal problema no podrá ser resuelto a menos de que el sistema en cuestión sea contradictorio, es decir, que haya un programa que ante una misma entrada terminará con una respuesta 0 o con una respuesta 1 indistintamente.
Siguiente: Teoremas de recursión Un nivel arriba: Decidibilidad Anterior: Proyecciones