Niska (obliczalność)
W teorii obliczalności stopień Turinga [ X ] jest niski , jeśli skok Turinga [ X ′] wynosi 0′. Zbiór jest niski, jeśli ma niski stopień. Ponieważ każdy zbiór jest obliczalny od jego skoku, każdy niski zbiór jest obliczalny w 0 ′, ale skok zbiorów obliczalnych w 0 ′ może ograniczać dowolny stopień re w 0 ′ (inwersja skoku Schoenfielda). Niski poziom X mówi, że jego skok X ′ ma najmniejszy możliwy stopień pod względem redukowalności Turinga dla skoku zbioru.
Istnieją różne powiązane właściwości z niskimi stopniami:
- Stopień jest niski , jeśli jego n-ty skok jest n-tym skokiem z 0.
- Zbiór X jest uogólniony nisko , jeśli spełnia X ′ ≡ T X + 0′, to znaczy: jeśli jego skok ma najniższy możliwy stopień.
- Stopień d jest uogólnionym niskim n , jeśli jego n-ty skok jest (n-1) skokiem połączenia d z 0′.
Mówiąc bardziej ogólnie, właściwości zbiorów, które opisują ich słabość obliczeniową (gdy są używane jako wyrocznia Turinga), są określane pod ogólnym terminem właściwości niskości .
Zgodnie z twierdzeniem Jockuscha i Soare'a o niskiej podstawie, każda niepusta ω \ zawiera zbiór niskiego stopnia. Oznacza to, że chociaż niskie zestawy są słabe obliczeniowo, nadal mogą dokonywać takich wyczynów, jak obliczenie zakończenia Peano Arithmetic . W praktyce pozwala to na ograniczenie mocy obliczeniowej obiektów potrzebnych do konstrukcji teorii rekurencji: np . Twierdzenie Ramseya .
Zobacz też
- Soare, Robert I. (1987). Rekurencyjnie przeliczalne zbiory i stopnie. Badanie funkcji obliczalnych i zbiorów generowanych obliczeniowo . Perspektywy w logice matematycznej . Berlin: Springer-Verlag . ISBN 3-540-15299-7 . Zbl 0667.03030 .
- Nies, André (2009). Obliczalność i losowość . Oxford Logic Guides. Tom. 51. Oksford: Oxford University Press. ISBN 978-0-19-923076-1 . Zbl 1169.03034 .