Recursión primitiva y $\Delta^0_0$

Question

Hasta hace poco yo asumía que la primitiva recursiva relaciones son exactamente $\Delta^0_0$ (es decir, encuadernadas), pero he aprendido que son diferentes (el primero es una superclase de la última).

Tengo una duda con respecto a la diferencia entre los dos:

1. Tengo cierta intuición acerca de las funciones recursivas primitivas. Por ejemplo, una función es primitiva recursiva si su algoritmo se describe por medio de "sólo para bucles, no mientras bucles". Cómo la intuición para $\Delta^0_0$ relaciones son diferentes de los que para el primitivo recursivo?

2. Lo sintáctico de la condición primitiva de la recursividad, corresponden, si no en todos? Más precisamente, si $R$ es una primitiva recursiva relación, ¿cuál es el sintáctico condición necesaria y suficiente para $\phi$ si $\bar n \in R \Leftrightarrow \mathbb N \models \phi(\bar n)$?

Answer 1

1. Deje $\Sigma =\left \{0,1 \right \}$, entonces es fácil comprobar que para cada $\phi({\bf x})\in \Delta_0^0$ existe una Máquina de Turing $M$ $\Sigma$ alfabeto tal que:

   • $L(M)$ está en la clase de Primaria,

   • $\forall n\in\mathbb{N}(|n|\in L(M) \leftrightarrow \phi(n))$ , $|n|$ es la representación binaria de $n$$\Sigma$.

   Pero por el Momento jerarquía teorema tenemos $Elementary \subsetneq PR$, de modo que existe un lenguaje de $L\in PR$$L\not\in Elementary$, por lo $L$ no $\Delta_0^0$ definibles.

2. Deje $\Sigma = \left \{ \forall, \exists, \rightarrow, \neg, \wedge, \vee, <, =, +, \cdot, 0, 1 \right \}$. Deje $A$ ser el conjunto de todos los $r.e.$ idiomas en este alfabeto. podemos mostrar la información de cada Máquina de Turing por un $\Sigma_1$ fórmula $\psi$ en este alfabeto, (Ver esta ). Definir $M=\left \{L\in A |L\subseteq \left \{0,1 \right \}^* \wedge L\in PR \right \}$, $M$ es nonetrivial subconjunto de $A$, de modo que por el Teorema de Arroz, $L=\left \{x\in \Sigma^*|(x\: is\:a\:formula)\wedge L(x)\in M \right \}$ es indecidible. Por lo tanto, no existe ningún tipo sintáctico condición necesaria y suficiente para decidir primitiva recursiva de los predicados.