チューリング次数
X ⊕ Y {\displaystyle X\oplus Y} のチューリング次数は X {\displaystyle X} と Y {\displaystyle Y} の次数の上限である。従って D {\displaystyle {\mathcal {D}}} は結びを持つ半束である。 次数 a と b の上限を a ∪ b と書く。下限を持たない次数の対が存在するので、 D {\displaystyle {\mathcal {D}}} は束ではないことが知られている。
集合 X {\displaystyle X} について、 X {\displaystyle X} をオラクルに持つときに停止する神託機械を指すインデクスの集合を X ′ {\displaystyle X'} と書く。集合 X ′ {\displaystyle X'} は X {\displaystyle X} のチューリングジャンプと呼ばれる。次数 [ X ] {\displaystyle [X]} のチューリングジャンプは次数 [ X ′ ] {\displaystyle [X']} であると定義される。これは X ≡ T Y {\displaystyle X\equiv _{T}Y} であれば必ず X ′ ≡ T Y ′ {\displaystyle X'\equiv _{T}Y'} ことからも妥当な定義である。一つの重要な例として 0′があるが、これは停止問題の次数である。