Wysoka (obliczalność)
W teorii obliczalności stopień Turinga [ X ] jest wysoki, jeśli można go obliczyć w 0′, a skok Turinga [ X ′] wynosi 0′′, co jest największym możliwym stopniem pod względem redukowalności Turinga dla skoku zbioru który jest obliczalny w 0′.
Podobnie, stopień jest wysoki n , jeśli jego n-ty skok jest (n+1) skokiem 0. Jeszcze bardziej ogólnie, stopień d jest uogólnionym wysokim n , jeśli jego n-ty skok jest n-tym skokiem połączenie d z 0 ′.
Zobacz też
Kategorie: