« TC: Funciones Recursi… « || Inicio || » NetLogo: Conceptos Bá… »

TC: Conjuntos Recursivamente Enumerables. Indecidibilidad

Última modificación: 9 de Noviembre de 2017, y ha tenido 6 vistas

Etiquetas utilizadas: || || ||

El Problema de la Parada

Proposición: Sea $HALT(x,y)=\begin{cases} 1 & \mbox{si } \varphi_y(x)\downarrow\\ 0 & \mbox{caso contrario}\end{cases}$. Entonces, $HALT:{\Bbb N}^2\to {\Bbb N}$ no es computable.

Demostración: Si $HALT\in \mathcal{P}$, entonces podemos definir el programa $P$:
$$[A]\ IF\ HALT(x,x)\ GOTO\ A$$

Sea $f\simeq \psi_p^{(1)}$. entonces:
$$f(x)=\begin{cases}
\uparrow & \mbox{si } HALT(x,x)=1\\
0 & \mbox{si } HALT(x,x)=0
\end{cases}$$

Sea $e\in{\Bbb N}$ tal que $\varphi_e=f$, se tiene que:

$$f(e)=0\Leftrightarrow \varphi_e(e)=0 \Leftrightarrow HALT(e,e)=0 \Leftrightarrow \varphi_e(e) \uparrow$$

Lo que es absurdo. Por tanto $HALT \notin \mathcal{P}$.

Como consecuencia, el conjunto $K=\{n:\ \varphi_n(n)\downarrow\}$ no es recursivo (y, por tanto, no es GOTO-computable).

Nota: El conjunto $K$ se denomina el conjunto de la parada.

Conjuntos Eecursivamente Enumerables

Definición: Diremos que $A\subseteq {\Bbb N}^n$ es recursivamente enumerable si existe $f\in \mathcal{P}$ tal que $A=dom(f)$.

Proposición: Si $A\in \mathcal{R}_*$ entonces $A$ es r.e.

Demostración: Si $A$ es un conjunto recursivo, entonces $\chi_A \in \mathcal{R}$. Sea $h$ la función calculada por el programa siguiente: $$[B]\ IF\ \chi_A(\vec{x})=0\ GOTO\ B$$
Entonces $dom( h )=A$, ya que $h(\vec{x})=\begin{cases} 0& \mbox{si } \vec{x} \in A\\ \uparrow & \mbox{si } \vec{x} \notin A\end{cases}$

Teorema del Complemento: $A\in \mathcal{R}_* \Leftrightarrow A \ y\ {\Bbb N}^n-A$ son r.e.

Demostración: 

  • $\Rightarrow$: $A\in \mathcal{R}_* \Rightarrow A,\ {\Bbb N}^n-A \in \mathcal{R}_* \Rightarrow A,\ {\Bbb N}^n-A$ r.e.
  • $\Leftarrow$: Si $A,\ {\Bbb N}^n-A$ son r.e. entonces existen $f,g \in rec$ tales que: $A=dom(f),\ {\Bbb N}^n-A=dom(g)$. Sea $P$ el siguiente programa: (donde $f=\varphi_p,\ g=\varphi_q$) $$\begin{array}{ll} [A] & IF\ STP^{(n)}(X_1,...,X_n,p,Z)\ GOTO\ B\\ & IF\ STP^{(n)}(X_1,...,X_n,q,Z)\ GOTO\ E\\ & Z\leftarrow Z+1\\ & GOTO\ A\\ [B] & Y \leftarrow Y + 1\\ \end{array}$$ Entonces $\psi_P^{(n)}=\chi_A$.

Proposición: Sean $B,C\subseteq {\Bbb N}^n$. Entonces: $$B,C\ r.e.\Rightarrow B\cup C,\ B\cap C\ r.e.$$

Demostración: Sean $B=dom(f)$, y $C=dom(g)$ para ciertas $f,g\in \mathcal{P}$. Sea $P$ el programa:
$$\begin{array}{l}
Y\leftarrow f(X_1,...,X_n)\\
Y\leftarrow g(X_1,...,X_n)
\end{array}$$
entonces $B\cap C=dom(\psi_p^{(n)})$, y por tanto, es r.e. Si $f=\varphi_p,\ g=\varphi_q$, sea $Q$ el programa:
$$\begin{array}{ll}
[A] & IF\ STP^{(n)}(X_1,...,X_n,p,Z)\ GOTO\ E\\
& IF\ STP^{(n)}(X_1,...,X_n,q,Z)\ GOTO\ E\\
& Z \leftarrow Z +1 \\
& GOTO\ A
\end{array}$$
entonces $B\cup C=dom(\psi_Q^{(n)})$.

Teorema: Dado $A\neq \emptyset$, son equivalentes:

  1. $A$ es r.e.
  2. Existe $f \in \mathcal{PR}$ tal que $A=rang(f)$.
  3. Existe $g \in \mathcal{R}$ tal que $A=rang(g)$.
  4. Existe $h \in \mathcal{P}$ tal que $A=rang( h )$.

Demostración:

  • $1\Rightarrow 2$: Si $A$ es r.e., existe $e\in {\Bbb N},\ A=dom(\varphi_e)$. Sea $x_0\in A$ fijo, definimos: $$f(n)=\begin{cases} l(n) & \mbox{si }STP(l(n),e,r(n))\\ x_0 & \mbox{en otro caso} \end{cases}$$ entonces $f\in \mathcal{PR}$. Obviamente $rang(f)\subseteq A$; además, si $x\in A$, entonces existe $t\in {\Bbb N},\ STP(x,e,t)$, luego $f(<x,t>)=x$.
  • $2\Rightarrow 3\Rightarrow 4$: Triviales.
  • $4\Rightarrow 1$: Sea $h=\varphi_e,\ A=rang( h )$, y $P$ el siguiente programa: $$\begin{array}{ll} [A] & $ IF\ \neg STP(Z_1,e,Z_2)\ GOTO\ B\\ & Z_3\leftarrow h(Z_1)\\ & IF\ Z_3=X\ GOTO\ E\\ [B] & Z_1 \leftarrow Z_1 + 1\\ & IF\ Z_1\leq Z_2\ GOTO\ A\\ & Z_2 \leftarrow Z_2 + 1\\ & Z_1\leftarrow 0\\ & GOTO\ A \end{array}$$ entonces, $dom(\psi_P)=A$. (Este último resultado se conoce como Teorema del rango). 

Definición: Sea $A\subseteq {\Bbb N}^n$. La función $\chi_A^*:{\Bbb N}^n - \to {\Bbb N}$ definida por
$$\chi_A^*(\vec{x})=\begin{cases}
1& \mbox{si }\vec{x} \in A\\
\uparrow & \mbox{si }\vec{x} \notin A\\
\end{cases}$$
se denomina función característica parcial de $A$.

Proposición: $A\ r.e. \Leftrightarrow \chi_A^*\in \mathcal{P}$.

Demostración:

  • $\Rightarrow$: $A$ r.e., entonces existe $f\in \mathcal{P},\ A=dom(f)$, entonces $\chi_A^*(\vec{x})=sg(f(\vec{x}))$.
  • $\Rightarrow$: Si $\chi_A^*\in \mathcal{P}$, entonces $A$ es r.e., pues $dom(\chi_A^*)=A$.

Nota: Si $A$ es recursivo, tenemos un procedimiento de decisión para $\vec{x}\in A$; si $A$ es r.e., tenemos un procedimiento de semidecisión para $\vec{x}\in A$.

Definición: Sea $K=\{n:\ \varphi_n(n)\downarrow\}$

Teorema: $K$ es r.e., pero no es recursivo.

Demostración: Ya hemos probado que $K$ no es recursivo. Para probar que es r.e. basta observar que $K=dom(f)$, siendo $f(x)=\varphi_x(x)=U_1(x,x)$.

Proposición: $TOT=\{x:\ \varphi_x\mbox{ es total}\}=\{x:\ \mbox{dom}(\varphi_x)={\Bbb N}\}$ no es r.e.

Demostración:
Si $TOT$ fuera r.e., entonces existiría una función $f\in \mathcal{R}$, tal que $TOT=rang(f)$. Sea $g:{\Bbb N} \to {\Bbb N}$, definida por $g(x)=\varphi_{f(x)}(x)+1$, que es recursiva, luego existiría $n\in {\Bbb N},\ g=\varphi_{f(n)}$, pero entonces: $g(n)=\varphi_{f(n)}(n)+1=g(n)+1$, lo que es una contradicción.

Teorema de Rice: Si $\emptyset\subset\Gamma\subset\mathcal{P}$ entonces $R_\Gamma=\{e\in {\Bbb N}:\ \varphi_e \in \Gamma\} \notin \mathcal{R}_*$

Corolario: Los siguientes conjuntos no son recursivos:
$$\{e:\ \varphi_e \in \mathcal{PR}\},\ \{e:\ \varphi \in \mathcal{R}\},\ \{e:\ \mbox{dom}(\varphi_e)=\emptyset\}$$
$$ \{e:\ \mbox{dom}(\varphi_e) \mbox{ finito}\},\ \{e:\ \mbox{dom}(\varphi_e)\mbox{ cofinito}\}$$

« TC: Funciones Recursi… « || Inicio || » NetLogo: Conceptos Bá… »