低い（計算可能性）

計算可能性理論では、チューリングジャンプ[ X ′] が 0′の場合、チューリング次数[ X ] は低くなります。集合が低いとは、次数が低いことです。すべての集合はそのジャンプから計算可能であるため、低い集合はどれも 0′ で計算可能ですが、0′ で計算可能な集合のジャンプは、0′で再帰的に列挙可能な次数に制限を設けることができます(Schoenfield ジャンプ反転) 。Xが低いということは、そのジャンプX ′ が、集合のジャンプの チューリング還元可能性に関して、可能な限り最小の次数であることを意味します。

低度数に関連するさまざまな特性があります。

• 次数がn番目に0からn番目にジャンプする場合、その次数は低_n^{である。 [1] [2]}
• 集合X は、 X ′ ≡ _T X + 0′を満たす場合、つまり、そのジャンプの次数が可能な限り低い場合、低一般化されます。
• 次数dが一般化低 n であるとは、その n 番目のジャンプがdと 0′の結合の (n-1) 番目のジャンプである場合です。

より一般的には、集合が計算的に弱いことを表す特性（チューリングオラクルとして使用される場合）は、包括的な用語として「低さ特性」と呼ばれます。

Jockusch と Soare のLow 基底定理により、 の空でないクラスには低次数の集合が含まれます。これは、低集合は計算的には弱いものの、ペアノ算術の完成を計算するなどの偉業を達成できることを意味します。実際には、これにより、再帰理論的構築に必要なオブジェクトの計算能力に制限が課せられます。たとえば、Ramsey の定理の証明理論的強度を分析する際に使用されるオブジェクトなどです。 ${\displaystyle \Pi _{1}^{0}}$${\displaystyle 2^{\omega}}$

• 高い（計算可能性）
• 低基底定理

• Soare, Robert I. (1987)。再帰的に列挙可能な集合と次数。計算可能関数と計算可能生成集合の研究。数理論理学の展望。ベルリン: Springer- Verlag。ISBN 3-540-15299-7.ZBL0667.03030  。​
• ニース、アンドレ (2009)。計算可能性とランダム性。オックスフォードロジックガイド。第51巻。オックスフォード：オックスフォード大学出版局。ISBN 978-0-19-923076-1.ZBL1169.03034  。​