No estoy seguro de por qué las funciones computables están en$\Delta_{1}^0$. ¿Alguien puede explicar esto?
Respuesta
¿Demasiados anuncios?
Supongamos que $S$ es un conjunto de enteros positivos, o elementos que pueden ser codificados como enteros positivos. Una definición de $\Sigma_1^0$ es que: es el conjunto de todos los conjuntos de $S$ que se puede expresar en la forma $$S=\{x\mid (\exists y_1)\cdots (\exists y_r)P(x,y_1,\ldots,y_r)\}, \qquad P \text{ primitive recursive.}$$ Un conjunto $S$ $\Pi_1^0$ fib de su complemento, $S^C$$\Sigma_1^0$, e $\Delta_1^0=\Sigma_1^0 \cap \Pi_1^0$. Así, un conjunto $S$ $\Delta_1^0$ fib tanto $S$$S^C$$\Sigma_1^0$.
Si la membresía en $S$ es decidable, entonces hay una máquina de Turing $M$, la que decide en un número finito de pasos si existe o no un determinado$x$$S$. Entonces $$S=\{x\mid (\exists y)P_M(x,y)\},$$ donde $y$ de los registros de un posible cálculo de $M$, e $P_M$ comprueba si $y$ es un registro legal de cálculo de $M$ que se inicia desde la entrada de la $x$ y termina en la aceptación de un estado. Desde la comprobación para ver si algo registros legal máquina de Turing de computación o no es simple, $P_M$ es primitiva recursiva. Por eso, $S\in \Sigma_1^0$. Sin embargo, también, $$S^C=\{x\mid (\exists y)P'_M(x,y)\},$$ donde $P'_M$ ahora comprueba si $y$ es un registro legal de cálculo de $M$, que comienza a $x$ y termina en un rechazo de estado. $P'_M$ es primitiva recursiva por la misma razón que $P_M$, lo $S^C\in \Sigma_1^0$. Por lo tanto,$S\in \Delta_1^0$.
Usted también puede demostrar que si $S\in \Delta_1^0$, $S$ es decidable, por tanto, ser $\Delta_1^0$ es equivalente a ser decidable. Para ver esto, supongamos que $S\in \Delta_1^0=\Sigma_1^0\cap \Pi_1^0$. Entonces $$ S=\{x\mid (\existe y_1)\cdots (\existe y_r) P(x,y_1,\ldots,y_r)\} $$ y $$ S^C=\{x\mid (\existe y_1)\cdots (\existe y_s) Q(x,y_1,\ldots,y_s)\} $$ para algunos $r$ $s$ y primitiva recursiva $P$$Q$. Para construir una máquina de Turing $M$ decidir si o no $x$$S$, vamos a $M$ sucesivamente construir cada posible secuencia $(y_1,\ldots,y_{\max(r,s)})$ y, a continuación, la prueba de $(x,y_1,\ldots,y_r)$$P$, detener y aceptar en el éxito, y $(x,y_1,\ldots,y_s)$$Q$, detener y rechazar en caso de éxito. Desde una de estas pruebas debe eventualmente tener éxito, $M$ siempre va a detener.
Si $S$ es la gráfica de una función computable, entonces la membresía en $S$ es decidable como se dio ninguna de las $(x,y)$, se puede calcular el $f(x)$ y, a continuación, acepte $(x,y)$ si $y=f(x)$ y rechazar lo contrario. Por eso, $S\in \Delta_1^0$ en este caso.
Demostrando que una decidable set $S$ $\Delta_1^0$ dependía del hecho de que $M$ siempre estaba garantizada para detener independientemente de si $x\in S$ o no. Si $M$ sólo se detenía cuando aceptó, y de lo contrario se puede correr para siempre, usted sólo tiene $S\in \Sigma_1^0$. Sólo como decidable caracteriza la $\Delta_1^0$ conjuntos, la propiedad de ser semi-decidable de esta manera caracteriza a la $\Sigma_1^0$ conjuntos, que también son llamados "recursivamente enumerable".
