ポストの定理
算術的階層が自然数の集合の定義可能性の尺度となる一方、チューリング次数は自然数の集合の計算不可能性のレベルの尺度となる。集合 A が集合 B にチューリング還元可能であることを A ≤ T B {\displaystyle A\leq _{T}B} と記述し、B についての神託を与える神託機械によって A の特性関数を計算できることを意味する。集合 A のチューリングジャンプは、A に関連する停止性問題の形式である。集合 A のチューリングジャンプ A ′ {\displaystyle A'} は、A についての神託機械を持ち 0 が入力されたときに停止するチューリング機械のインデックスの集合である。あらゆる集合 A はそのチューリングジャンプにチューリング還元可能であるが、ある集合のチューリングジャンプは決して元の集合にチューリング還元できない。
ポストの定理は有限回反復されたチューリングジャンプを使用する。任意の自然数の集合 A について、 A ( n ) {\displaystyle A^{(n)}} とは A のチューリングジャンプを n 回反復したものを表す。従って、 A ( 0 ) {\displaystyle A^{(0)}} は A そのものであり、 A ( n + 1 ) {\displaystyle A^{(n+1)}} は A ( n ) {\displaystyle A^{(n)}} のチューリングジャンプである。