Siguiente: Problema de la parada Un nivel arriba: Decidibilidad Anterior: Conjuntos decidibles

Proyecciones

Veremos en esta sección que la clase de conjuntos decidibles no necesariamente es cerrada bajo proyecciones. Esto dará en consecuencia que existen funciones no-computables que pueden ser formuladas, sin embargo, en el contexto de nociones de computabilidad. Si $A\in\mbox{\it Recur}_n$ y $m\leq n$ la proyección de A en las primeras m coordenadas es

$$\Pi_m(A)=\{\mbox{\bf x}\in N^m\vert\exists \mbox{\bf y}\in N^{n-m}:(\mbox{\bf x},\mbox{\bf y})\in A\}.$$

Observación 3.3   Toda proyección de un conjunto decidibles es un conjunto semidecidible, es decir

$$A\in\mbox{\it Recur}_n\;\Rightarrow\;\Pi_m(A)\in\mbox{\it RecEn}_m.$$

En efecto, se tiene por definición $\left[\chi_{\Pi_m(A)}(\mbox{\bf x})=1 \Leftrightarrow \exists \mbox{\bf y}\in N^{n-m}:\chi_A(\mbox{\bf x},\mbox{\bf y})=1\right],$ luego $\Pi_m(A)$ coincide con el dominio de la función programable $\mbox{\bf x}\mapsto \mathop{\rm Min}\{\mbox{\bf y}\vert\chi_A(\mbox{\bf x},\mbox{\bf y})-1 = 0\},$ donde el mínimo se toma según alguna enumeración (computable) de $I\!\!N^{n-m}$.


Esta última observación implica a su vez las siguientes dos relaciones ya demostradas:

$$\begin{array}{rcl} A\in\mbox{\it Recur}_n &\Rightarrow & A\i... ...}_n &\Leftrightarrow & A,A^c\in\mbox{\it RecEn}_n. \end{array}$$