PA-examen

Inom det matematiska området beräkningsteori är en PA-examen en Turing-examen som beräknar en fullständig förlängning av Peano-aritmetik (Jockusch 1987). Dessa grader är nära besläktade med fixpunktsfria (DNR) funktioner och har undersökts grundligt i rekursionsteorin.

Bakgrund

I rekursionsteorin betecknar ${\displaystyle \phi _{e}} den$ beräkningsbara funktionen med index (program) e i viss standardnumrering av beräkningsbara funktioner, och $\phi _{e}^{B }$ betecknar den e: te beräkningsbara funktionen som använder en uppsättning B av naturliga tal som ett orakel.

En mängd A med naturliga tal är Turing-reducerbar till en mängd B om det finns en beräkningsbar funktion som, givet ett orakel för mängd B , beräknar den karakteristiska funktionen χ _A för mängden A . Det vill säga, det finns ett e så att $\chi _{A}=\phi _{e}^{B}$ . Detta förhållande betecknas A ≤ _TB ; relationen ≤ _T är en förbeställning .

Två uppsättningar naturliga tal är Turing-ekvivalenter om var och en är Turing-reducerbar till den andra. Notationen A ≡ _T B indikerar att A och B är Turingekvivalenta. Relationen ≡ _T är en ekvivalensrelation som kallas Turing-ekvivalens. En Turing-grad är en samling av naturliga tal, så att alla två uppsättningar i samlingen är Turing-ekvivalenta. På motsvarande sätt är en Turing-grad en ekvivalensklass för relationen ≡ _T .

Turinggraderna är delvis ordnade efter Turing-reducerbarhet. Notationen a ≤ _T b indikerar att det finns en mängd i grad b som beräknar en mängd i grad a . På motsvarande sätt gäller a ≤ _T b om och endast om varje mängd i b beräknar varje mängd i a .

En funktion f från de naturliga talen till de naturliga talen sägs vara diagonalt icke-rekursiv (DNR) om, för alla n , $f(n)\not =\phi _{ n}(n)$ (här gäller olikhet per definition om $\phi _{n}(n)$ är odefinierad). Om intervallet för f är uppsättningen {0,1} så är f en DNR ₂ -funktion. Det är känt att det finns DNR-funktioner som inte beräknar någon DNR ₂ -funktion.

Slutföranden av Peano-arithmetik

En komplettering av Peano-aritmetik är en uppsättning formler på språket för Peano-aritmetik, så att mängden är konsekvent i första ordningens logik och så att, för varje formel, antingen den formeln eller dess negation ingår i mängden. När en Gödel-numrering av formlerna på PA-språket har fixerats är det möjligt att identifiera kompletteringar av PA med uppsättningar av naturliga tal, och därmed tala om beräkningsbarheten för dessa kompletteringar.

0 En Turing-grad definieras som en PA-grad om det finns en uppsättning naturliga tal i graden som beräknar ett slutförande av Peano Aritmetik. (Detta motsvarar påståendet att varje uppsättning i graden beräknar en komplettering av PA.) Eftersom det inte finns några beräkningsbara slutföranden av PA, är graden som består av de beräkningsbara uppsättningarna av naturliga tal inte en PA-grad.

Eftersom PA är en effektiv teori av första ordningen, kan avslutningarna av PA karakteriseras som de oändliga vägarna genom ett särskilt beräkningsbart underträd på 2 < ^ω . Således är PA-graderna exakt de grader som beräknar en oändlig väg genom detta träd.

Egenskaper

PA-graderna är stängda uppåt i Turing-graderna: om a är en PA-grad och a ≤ _T b är b en PA-grad.

000 Turinggraden , som är graden av stoppproblemet , är en PA-grad. Det finns också PA-grader som inte är över '. Till exempel lågbassatsen att det finns en låg PA-grad. Å andra sidan Antonín Kučera bevisat att det finns en grad mindre än ' som beräknar en DNR-funktion men inte är en PA-grad (Jockusch 1989:197).

Carl Jockusch och Robert Soare (1972) bevisade att PA-graderna är exakt graderna för DNR ₂ -funktioner.

Per definition är en examen PA om och bara om den beräknar en väg genom trädet av avslutningar av Peano-arithmetik. En starkare egenskap gäller: en grad a är en PA-grad om och endast om a beräknar en väg genom varje oändligt beräkningsbart underträd på 2 ^<ω (Simpson 1977).

Arslanovs fullständighetskriterium

MM Arslanov gav en karaktärisering av vilka ce-mängder som är kompletta (dvs Turing motsvarar ${\displaystyle \varnothing '} )$ . För en ce set $A\subseteq \mathbb {N}$ , $A\equiv _{\mathrm {T} }\varnothing '$ om och endast om ${\ displaystyle A}$ beräknar en DNR-funktion. I synnerhet är varje PA-grad DNR ₂ och därmed DNR, så $\varnothing '$ är den enda ce PA-graden.

Se även

Carl Jockusch (1987), "Degrees of functions with no fix points", Logic Colloquium '87 , Fenstad, Frolov och Hilpinen, red., North-Holland, ISBN 0-444-88022-4
⁰ Carl Jockusch och Robert Soare (1972), "Π ₁ classes and degrees of theories", Transactions of the American Mathematical Society , v. 173, s. 33–56.
Stephen G. Simpson (1977), "Degrees of unsolvability: a survey of results", Handbook of Mathematical Logic , Barwise (red.), North-Holland, s. 631–652. ISBN 0-444-86388-5