En el campo matemático de la teoría de la computabilidad , un título de PA es un título de Turing que calcula una extensión completa de la aritmética de Peano (Jockusch 1987). Estos grados están estrechamente relacionados con las funciones de punto fijo libre (DNR) y han sido investigados a fondo en la teoría de la recursividad.
En teoría de la recursividad, denota la función computable con índice (programa) e en alguna numeración estándar de funciones computables, y denota la e -ésima función computable usando un conjunto B de números naturales como oráculo.
Un conjunto A de números naturales es reducible por Turing a un conjunto B si existe una función computable que, dado un oráculo para el conjunto B , calcula la función característica χ A del conjunto A. Es decir, existe una e tal que . Esta relación se denota A ≤ T B ; la relación ≤ T es un preorden .
Dos conjuntos de números naturales son equivalentes de Turing si cada uno es reducible por Turing al otro. La notación A ≡ T B indica que A y B son equivalentes de Turing. La relación ≡ T es una relación de equivalencia conocida como equivalencia de Turing. Un grado de Turing es una colección de conjuntos de números naturales, de modo que dos conjuntos cualesquiera de la colección son equivalentes de Turing. De manera equivalente, un grado de Turing es una clase de equivalencia de la relación ≡ T.
Los grados de Turing están parcialmente ordenados por la reducibilidad de Turing. La notación a ≤ T b indica que hay un conjunto en grado b que calcula un conjunto en grado a . De manera equivalente, a ≤ T b se cumple si y solo si cada conjunto en b calcula cada conjunto en a .
Se dice que una función f de los números naturales a los números naturales es diagonalmente no recursiva (DNR) si, para todo n , (aquí la desigualdad se cumple por definición si no está definida). Si el rango de f es el conjunto {0,1} entonces f es una función DNR 2 . Se sabe que existen funciones DNR que no calculan ninguna función DNR 2 .
Una finalización de la aritmética de Peano es un conjunto de fórmulas en el lenguaje de la aritmética de Peano, de modo que el conjunto sea consistente en lógica de primer orden y que, para cada fórmula, esa fórmula o su negación se incluya en el conjunto. Una vez fijada una numeración de Gödel de las fórmulas en el lenguaje de PA, es posible identificar completaciones de PA con conjuntos de números naturales, y así hablar de la computabilidad de estas terminaciones.
Un título de Turing se define como un título de PA si hay un conjunto de números naturales en el grado que calcula la finalización de la Aritmética de Peano. (Esto es equivalente a la proposición de que cada conjunto del grado calcula una terminación de PA). Debido a que no hay terminaciones computables de PA, el grado 0 que consta de conjuntos computables de números naturales no es un grado de PA.
Debido a que PA es una teoría efectiva de primer orden, las terminaciones de PA se pueden caracterizar como caminos infinitos a través de un subárbol computable particular de 2 <ω . Por tanto, los grados PA son exactamente los grados que calculan un camino infinito a través de este árbol.
Los grados PA están cerrados hacia arriba en los grados de Turing: si a es un grado PA y a ≤ T b entonces b es un grado PA.
El grado de Turing 0 ', que es el grado del problema de detención , es un grado PA. También existen grados de PA que no superan los 0 '. Por ejemplo, el teorema de la base baja implica que existe un grado bajo de PA. Por otro lado, Antonín Kučera ha demostrado que existe un grado menor que 0 ' que calcula una función DNR pero no es un grado PA (Jockusch 1989:197).
Carl Jockusch y Robert Soare (1972) demostraron que los grados PA son exactamente los grados de las funciones DNR 2 .
Por definición, un grado es PA si y sólo si calcula un camino a través del árbol de terminaciones de la aritmética de Peano. Se cumple una propiedad más fuerte: un grado a es un grado PA si y sólo si a calcula un camino a través de cada subárbol computable infinito de 2 <ω (Simpson 1977).
MM Arslanov dio una caracterización de qué conjuntos ce están completos (es decir, el equivalente de Turing a ). Para un conjunto ce , si y solo si calcula una función DNR. En particular, cada título de PA es DNR 2 y, por lo tanto, DNR, por lo que es el único título de PA ce.
