Siguiente: Proyecciones Un nivel arriba: Decidibilidad Anterior: Decidibilidad

Conjuntos decidibles

Dado un conjunto $A\subset N^m$ su función característica es

$$\chi_A:\mbox{\bf x}\mapsto\left\{\begin{array}{ll} 1 &\mbox... ...x}\in A$} \\ 0 &\mbox{\rm en otro caso.} \end{array}\right.$$

• A se dice ser decidible si $\chi_A\in\mbox{\rm\rm Programas-{\bf while }}$.
• A se dice ser semidecidible si $\exists\; g\in\mbox{\rm\rm Programas-{\bf while }}:\;A=\{\mbox{\bf x}\vert g(\mbox{\bf x})\downarrow\},$ es decir, si A es el dominio de alguna función programable.

A los conjuntos decidibles se les suele llamar también recursivos y a los semidecidibles, recursivamente enumerables.

Proposición 3.1   A es decidible si y sólo si ambos A y su complemento A^c=N^m-A son semidecidibles.

En efecto, si A es decidible, entonces A y A^c son los respectivos dominios de las funciones

$$\begin{array}{lcl} g_A:\mbox{\bf x}\mapsto\left\{\begin{arra... ...m si $\chi_A(\mbox{\bf x})=1$} \end{array}\right. \end{array}$$

las cuales son efectivamente programables. Así que A y A^c son semidecidibles. Recíprocamente, si A y A^c son semidecidibles y son los dominios de sendas funciones programables g_A y g_A^c entonces la característica de A coincide con la función

$$G:\mbox{\bf x}\mapsto\left\{\begin{array}{ll} 1 & \mbox{\rm ... ...{\rm si $g_{A^c}(\mbox{\bf x})\downarrow$.} \end{array}\right.$$

la cual, de manera similar a como se hizo en las proposiciones 3.4.4 y 3.4.6, resulta ser programable. Así que A es decidible.


Definamos a las clases de conjuntos decidibles y semidecidibles, en general y también en cada potencia cartesiana de N:

$$\begin{array}{ccc} \begin{array}{lcl} \mbox{\it Recur}&=&\{... ...&=&\mbox{\it RecEn}\cap{\cal P}(N^n) \end{array} \end{array}$$

donde para cualquier conjunto C, ${\cal P}(C)$ denota al conjunto de partes, o de subconjuntos, de C.

Observación 3.1   $\mbox{\it Recur}$ y $\mbox{\it RecEn}$ son a lo sumo numerables.

En efecto, cada conjunto decidible o semidecidible determina a una función computable y éstas, como ya hemos visto, forman un conjunto numerable.

Observación 3.2   $\forall\;n:\;\;\mbox{\it Recur}_n$ forma un álgebra de conjuntos.

Esto resulta de las igualdades

$$\begin{array}{l@{\ ;\ }l@{\ ;\ }l} \chi_{A\cap B}=\chi_A\cdo... ..._A+\chi_B-\chi_A\cdot\chi_B & \chi_{A^c}=1-\chi_A \end{array}$$

y de que las operaciones aritméticas son programables.
Siguiente: Proyecciones Un nivel arriba: Decidibilidad Anterior: Decidibilidad