Stupeň PA - PA degree

V matematické oblasti teorie vypočítatelnosti, a Stupeň PA je Turingův stupeň který počítá kompletní rozšíření Peano aritmetika (Jockusch 1987). Tyto tituly úzce souvisí s funkcemi DNR (fixed-point-free) a byly důkladně prozkoumány v teorii rekurze.

Pozadí

V teorii rekurze ${displaystyle phi _ {e}}$ označuje vypočítatelná funkce s indexem (program) E v některých standardních číslováních vypočítatelných funkcí a ${displaystyle phi _ {e} ^ {B}}$ označuje Espočítatelná funkce pomocí množiny B přirozených čísel jako věštec.

Sada A přirozených čísel je Turingův redukovatelný do sady B pokud existuje vypočítatelná funkce to, vzhledem k věštbě pro set B, počítá charakteristická funkce χ_A sady A. To znamená, že existuje E takhle ${displaystyle chi _ {A} = phi _ {e} ^ {B}}$ . Tento vztah je označen A ≤_T B; vztah ≤_T je předobjednávka.

Dvě sady přirozených čísel jsou Turingův ekvivalent pokud je každá Turingova redukovatelná na druhou. Zápis A ≡_T B označuje A a B jsou Turingův ekvivalent. Vztah ≡_T je ekvivalenční vztah známý jako Turingova ekvivalence. A Turingův stupeň je kolekce sad přirozených čísel, takže jakékoli dvě sady v kolekci jsou Turingovým ekvivalentem. Ekvivalentně je Turingův stupeň ekvivalenční třídou vztahu ≡_T.

Turingovy stupně jsou částečně objednané Turingovou redukovatelností. Zápis A ≤_T b označuje, že existuje množina stupňů b který počítá množinu stupňů A. Ekvivalentně A ≤_T b platí pouze a jen v případě, že je každý nastaven b spočítá každou sadu A.

Funkce F od přirozených čísel k přirozeným číslům se říká, že jsou úhlopříčně nerekurzivní (DNR) pokud pro všechny n, ${displaystyle f (n) ot = phi _ {n} (n)}$ (zde nerovnost podle definice platí, pokud ${displaystyle phi _ {n} (n)}$ není definováno). Pokud je rozsah F je tedy množina {0,1} F je DNR₂ funkce. Je známo, že existují funkce DNR, které nepočítají žádné DNR₂ funkce.

Dokončení Peano aritmetiky

Dokončení Peano aritmetika je sada vzorců v jazyce Peanoovy aritmetiky, takže sada je konzistentní v logice prvního řádu a taková, že pro každý vzorec je v sadě obsažen buď tento vzorec, nebo jeho negace. Jakmile je opraveno Gödelovo číslování vzorců v jazyce PA, je možné identifikovat doplnění PA se sadami přirozených čísel, a tak hovořit o vypočítatelnosti těchto doplnění.

Turingův stupeň je definován jako a Stupeň PA pokud existuje množina přirozených čísel ve stupni, který počítá dokončení Peano aritmetiky. (To je ekvivalentní s tvrzením, že každá sada ve stupni počítá dokončení PA.) Protože neexistují žádné vypočítatelné dokončení PA, stupeň 0 skládající se z vypočítatelných množin přirozených čísel není stupeň PA.

Protože PA je účinná teorie prvního řádu, lze dokončení PA charakterizovat jako nekonečné cesty konkrétním vypočítatelným podstromem 2^<ω. Stupně PA jsou tedy přesně stupně, které vypočítávají nekonečnou cestu tímto stromem.

Vlastnosti

Stupně PA jsou v Turingových stupních uzavřeny nahoru: pokud A je absolventem PA a A ≤_T b pak b je titul PA.

Turingův stupeň 0„, Což je míra zastavení problému, je titul PA. Existují také stupně PA, které nejsou výše 0„. Například věta o nízké bázi znamená, že existuje nízký stupeň PA. Na druhou stranu, Antonín Kučera prokázal, že existuje stupeň menší než 0„Který počítá funkci DNR, ale nejedná se o stupeň PA (Jockusch 1989: 197).

Carl Jockusch a Robert Soare (1972) prokázali, že stupně PA jsou přesně stupni DNR₂ funkce.

Podle definice je titul PA právě tehdy, když počítá cestu stromem dokončení Peanoovy aritmetiky. Silnější vlastnost platí: titul A je titul PA právě tehdy A vypočítá cestu každý nekonečný vypočítatelný podstrom 2^<ω (Simpson 1977).

Arslanovovo kritérium úplnosti

M. M. Arslanov dal charakteristiku, která např. sady jsou kompletní (tj. Turing odpovídá ${displaystyle varnothing '}$ ). Pro ce soubor ${displaystyle Asubseteq mathbb {N}}$ , ${displaystyle Aequiv _ {mathrm {T}} varnothing '}$ kdyby a jen kdyby ${displaystyle A}$ vypočítá funkci DNR. Každý stupeň PA je zejména DNR₂ a tedy DNR, takže ${displaystyle varnothing '}$ je jediný ce Stupeň PA.

Viz také

Reference

Carl Jockusch (1987), „Stupně funkcí bez pevných bodů“, Logické kolokvium '87, Fenstad, Frolov a Hilpinen, ed., Severní Holandsko, ISBN 0-444-88022-4
Carl Jockusch a Robert Soare (1972), „Π⁰₁ třídy a stupně teorií ", Transakce Americké matematické společnosti, v. 173, s. 33–56.
Stephen G. Simpson (1977), „Stupně neřešitelnosti: průzkum výsledků“, Příručka matematické logiky, Barwise (ed.), Severní Holandsko, str. 631–652. ISBN 0-444-86388-5