Siguiente: Teoremas de jerarquía Un nivel arriba: Clasificación de problemas irresolubles Anterior: Computaciones con oráculos

  
Enumerabilidad recursiva relativa a oráculos

En esta parte introduciremos algunas nociones básicas que presentaremos (Cfr 7.1.1) más adelante. Veremos aquí que los problemas irresolubles mediante funciones computables son heredados por clases de funciones que extienden a las computables mediante oráculos. Dados dos conjuntos A,B, $B\not=\emptyset$, diremos que

• A es recursivo-B si $\chi_A\in\mbox{\it Rec}(\chi_B)$. En este caso, escribiremos $A\preceq_r B$.
• A es reducible múltiplemente a B si existe una función computable f tal que A=f^-1(B), es decir, si
  
  $$\forall x:\ x\in A\;\Leftrightarrow\;f(x)\in B.$$
  
  
  En este caso, escribiremos $A\preceq_{m} B$.
• A es reducible mónicamente a B si existe una función computable e inyectiva f tal que A=f^-1(B), en este caso, escribiremos $A\preceq_{1} B$.

De manera natural se tiene que las siguientes proposiciones son válidas:

Proposición 5.3   La relación ``$\preceq_r$'' es reflexiva y transitiva.

En efecto, es reflexiva porque la función identidad es computable. Es transitiva, porque la clase de funciones computables es cerrada bajo composición de funciones.

Proposición 5.4   `` $\preceq_{1}$'' es un refinamiento de `` $\preceq_{m}$'' y `` $\preceq_{m}$'' es un refinamiento de ``$\preceq_r$'', es decir

$$\begin{array}{rcl@{\hspace{4em};\hspace{4em}}rcl} A \preceq_... ...} B & A \preceq_{m} B &\Rightarrow& A \preceq_r B \end{array}$$

En efecto, la condición que define a `` $\preceq_{1}$'' es más fuerte que la de `` $\preceq_{m}$'', pues aquella exige que la función f tal que A=f^-1(B) sea inyectiva. por otro lado, si A=f^-1(B), donde f es computable, entonces $\chi_A=\chi_B\circ f$, es decir $\chi_A$ es recursiva respecto a $\chi_B$.

Proposición 5.5   Las relaciones `` $\preceq_{1}$'' y `` $\preceq_{m}$'' son reflexivas y transitivas.

En efecto, la función identidad es computable y la composición de computables es computable.


Toda relación entre conjuntos que sea reflexiva y transitiva se dice ser una reducibilidad. Sea ${\cal C}$ una clase de conjuntos y ``$\preceq$'' una reducibilidad.

• La clase ${\cal C}$ es cerrada respecto a la reducibilidad ``$\preceq$'' si $\forall A,B:\ (B\in {\cal C})\& (A\preceq B)\;\Rightarrow\;(A\in {\cal C}).$
• Un conjunto B es difícil para la clase ${\cal C}$ si $\forall A:\ (A\in {\cal C}) \;\Rightarrow\;(A\preceq B).$
• Un conjunto B es completo para la clase ${\cal C}$ (completo-${\cal C}$) si además de ser difícil para la clase ${\cal C}$ está también en la clase ${\cal C}$.
• ${\cal C}$ es cerrada-m o cerrada-1 si es cerrada respecto a la reducibilidad $\preceq_{m}$ o $\preceq_{1}$ respectivamente.

Sea G una función total. $B\subset N$ es recursivamente enumerable-G, r.e.-G, si es el dominio de una función recursiva-G. Como en el caso sin oráculos se tiene las propiedades siguientes:

Proposición 5.6   Si B es recursivo-G entonces B es r.e.-G.

Proposición 5.7   B es recursivo-G si y sólo si ambos B y B^c son r.e.-G.

Proposición 5.8   La clase de conjuntos r.e.-G es cerrada bajo las operaciones conjuntistas de unión e intersección.

Proposición 5.9   Los conjuntos r.e.-G son las proyecciones de las relaciones recursivas-G.

Proposición 5.10   Sea $\left\{f_n^G\right\}_n$ una enumeración de las funciones recursivas-G. Sean

$$\begin{eqnarray*}\mbox{\it PP}^G &=& \{(n,m)\vert f_n^G(m)\downarrow\}, \\ \mbox{\it DP}^G &=& \{n\vert(n,n)\in\mbox{\it PP}^G\}. \end{eqnarray*}$$

Entonces ambos conjuntos $\mbox{\it PP}^G,\mbox{\it DP}^G$ son r.e.-G mas no son recursivos-G.

Proposición 5.11   Para cada conjunto $A\subset N$, las siguientes condiciones son equivalentes a pares:

1.

A es r.e.-G.

2.

$A\preceq_1 \mbox{\it DP}^G$.

3.

$A\preceq_m \mbox{\it DP}^G$.

Proposición 5.12   Para cada función total G, las sucesiones de conjuntos $\left\{D_n^G\right\}_n$ y de funciones $\left\{F_n^G\right\}_n$ definidas simultáneamente de manera recursiva:

$$\begin{array}{rclcrcl} F_0^G &=& G & &D_0^G &=& \mbox{\it DP... ...\right. & & D_{n+1}^G &=& \mbox{\it DP}^{F_{n+1}} \end{array}$$

definen una jerarquía de ``irresolubilidades''.

Siguiente: Teoremas de jerarquía Un nivel arriba: Clasificación de problemas irresolubles Anterior: Computaciones con oráculos