ポストの定理

3行要約

1. 算術的階層における集合の複雑さと、チューリング次数の関係を記述する定理。
2. 再帰的列挙集合の概念を一般化し、計算不可能性の度合いを分類する。
3. 数理論理学および計算理論における中心的な成果の一つ。