Nízká (vypočítatelnost) - Low (computability)

v teorie vypočítatelnosti, a Turingův stupeň [X] je nízký pokud Turingův skok [X′] Je 0 ′. Sada je nízká, pokud má nízký stupeň. Vzhledem k tomu, že každá sada je vypočítatelná z jejího skoku, je každá nízká sada vypočítatelná v 0 ', ale skok sad vypočítatelných v 0' může vázat jakýkoli stupeň r.e. v 0 '(Schoenfield Jump Inversion). X být nízký říká, že jeho skok X′ Má nejmenší možný stupeň, pokud jde o Turingova redukovatelnost pro skok sady.

Titul je nízké n pokud jeho n-tý skok je n-tým skokem o 0. Sada X je generalizovaná nízká pokud to vyhovuje X′ ≡T X + 0 ', to znamená: pokud má jeho skok nejnižší možný stupeň. A titul d je generalizované nízké n pokud jeho n-tý skok je (n-1) první skok spojení d s 0 '. Obecněji jsou vlastnosti množin, které popisují, že jsou výpočetně slabé (pokud jsou použity jako Turingův věštec), označovány jako zastřešující termín nízké vlastnosti.

Podle Věta o nízké bázi Jockusch a Soare, jakékoli neprázdné třída v obsahuje sadu nízkého stupně. To znamená, že i když jsou nízké sady výpočetně slabé, stále mohou dosáhnout takových výkonů jako výpočet dokončení Peano aritmetiky. V praxi to umožňuje omezení výpočetní síly objektů potřebných pro teoretické konstrukce rekurze: například ty, které se používají při analýze důkazní teoretická síla z Ramseyova věta.

Viz také

Reference

  • Soare, Robert I. (1987). Rekurzivně vyčíslitelné množiny a stupně. Studie vypočítatelných funkcí a vypočítatelně generovaných množin. Perspektivy v matematické logice. Berlín: Springer-Verlag. ISBN  3-540-15299-7. Zbl  0667.03030.
  • Nies, André (2009). Vyčíslitelnost a náhodnost. Oxford Logic Guides. 51. Oxford: Oxford University Press. ISBN  978-0-19-923076-1. Zbl  1169.03034.