Extender las funciones recursivas a clases superiores en la jerarquía aritmética

Question

Se trata de un importante teorema que las funciones recursivas son exactamente aquellos que son definibles por $\Delta^0_1$ fórmulas.

Ya hemos terminado la parte acerca de la incompletitud, en un curso que estoy TA ing, y un alumno me ha pedido a la siguiente pregunta, y yo no tenía idea de cómo responder a él adecuadamente. Voy a ligeramente refinar la pregunta.

Sabemos que las funciones recursivas se construyen a partir de las funciones básicas mediante el cierre de ellos bajo los esquemas de composición, la primitiva, la recursividad y la minimización. Sabemos que no es suficiente para describir las funciones que se $\Sigma^0_1$ o $\Pi^0_1$, o incluso más arriba en la jerarquía aritmética.

1. Hay otros esquemas que nos permitan alcanzar niveles superiores de la jerarquía?
2. Podemos controlar qué tan lejos estamos de llegar a la jerarquía?
3. Y son los esquemas que nos permiten definir todos los predicados de la jerarquía?

Answer 1

Un tipo de esquemas que nos permitirá subir en la jerarquía sería "la apelación a un oráculo." La idea es que además de la construcción de las funciones de las funciones básicas por la composición, la primitiva, la recursividad, y $\mu$-recursividad, también permitimos en nuestra construcción de las funciones de la apelación a finito de segmentos inicial de una función especificada $f$, lo que llamamos un "oracle". Aquí, $f$ podría ser cualquier función que nos gusta, así que siempre que solucionar un determinado $f$ antes de nuestra construcción. Por ejemplo, $f$ podría ser la función característica de una$\Sigma_n^0$, o podría ser una función que calcula la detención problema (en un no-recursiva manera). En cualquier caso, si permitimos que apela a este oráculo, y construimos una función de $g$ de esta manera, podemos decir que $g$ es recusrive en $f$o $f$-recursiva. Esta es una manera fácil de controlar su movimiento hacia arriba en la jerarquía. Si su oracle $f$$\Sigma_n^0$, entonces su función de $g$ es en el mejor de los $\Sigma_n^0$.

Incluso puede ascender más alto en la "analítica" de la jerarquía, si usted se permite el uso de la función de los cuantificadores (que requiere de segundo orden de la lógica). Estos residen incluso más altos que cualquiera de las clasificaciones en la aritmética de la jerarquía.