Siguiente: Enumerabilidad recursiva relativa a Un nivel arriba: Clasificación de problemas irresolubles Anterior: Clasificación de problemas irresolubles

Computaciones con oráculos

Sea $G:N \rightarrow N$ una función. Los programas-G-while se construyen como los programas-while considerando como primitiva a la instrucción

$$<\mbox{\it Variable}>:=G(<\mbox{\it Variable}>),$$

la que se dice ser un oráculo para la función G. Una función $f:N\rightarrow N$ es computable-G si es calculable por un programa-G-while . La clase de funciones recursivas relativas al oráculo G se define como

$$\mbox{\it Rec}(G)=\{f:N\rightarrow N\vert f\mbox{\rm es computable-$G$}\}.$$

Proposición 5.1   Las siguientes propiedades se cumplen (evidentemente):

1.

Si f es recursiva entonces $f\in\mbox{\it Rec}(\mbox{\it Id})$, donde $\mbox{\it Id}$ es la función identidad.

2.

Si f es recursiva y G es cualquier función total entonces $f\in\mbox{\it Rec}(G)$. En otras palabras, las funciones computables lo son también relativas a cualquier otra función total.

3.

Si G es total entonces $G\in\mbox{\it Rec}(G)$.

4.

Si $F\in\mbox{\it Rec}(G)$ y $G\in\mbox{\it Rec}(H)$ entonces $F\in\mbox{\it Rec}(H)$.

5.

$G\in\mbox{\it Rec}\ \Leftrightarrow \ \mbox{\it Rec}=\mbox{\it Rec}(G).$

Proposición 5.2   Las clases siguientes son efectivamente numerables:

1.

La clase de programas-G-while .

2.

La clase $\mbox{\it Rec}(G)$ de funciones computables-G.

De aquí resulta el

Teorema 5.1 (de Universalidad Relativizada)   Sea $\left\{f_{G,n}\right\}_{n\geq 0}$ una enumeración de las funciones computables-G. Si G es total entonces la función $U_G:(n,m)\mapsto f_{G,n}(m)$ es universal para $\mbox{\it Rec}(G)$, y está en la misma clase $\mbox{\it Rec}(G)$.

Naturalmente, se tiene el Problema de la Palabra Relativizado: Sea $\left\{f_{G,n}\right\}_{n\geq 0}$ una enumeración de las funciones computables-G. Definamos

$$\begin{eqnarray*}P_G:N^2 &\rightarrow& N \\ (n,m) &\mapsto& \left\{\begin{arra... ...w$ , } \\ 0 &\mbox{\rm en otros casos. } \end{array}\right. \end{eqnarray*}$$

Entonces $P_G\not\in\mbox{\it Rec}(G)$.
Siguiente: Enumerabilidad recursiva relativa a Un nivel arriba: Clasificación de problemas irresolubles Anterior: Clasificación de problemas irresolubles