Vysoká (vypočítatelnost) - High (computability) - Wikipedia

v teorie vypočítatelnosti, a Turingův stupeň [X] je vysoká, pokud je vypočítatelná v 0 ', a Turingův skok [X′] Je 0 ′ ′, což je největší možný stupeň z hlediska Turingova redukovatelnost pro skok sady, kterou lze vypočítat v 0 '(Soare 1987: 71).

Podobně je titul vysoká n pokud je jeho n-tý skok (n + 1), první skok 0. Ještě obecněji, stupeň d je generalizovaná vysoká n pokud jeho n-tý skok je n-tým skokem spojení d s 0 '.

Viz také

Nízká (vypočítatelnost)

Reference

Soare, R. Rekurzivně vyčíslitelné množiny a stupně. Perspektivy v matematické logice. Springer-Verlag, Berlín, 1987. ISBN  3-540-15299-7