計算可能集合

計算可能性理論において、自然数の集合は、すべての自然数がその集合に属するかどうかを有限回のステップで計算するアルゴリズムが存在する場合、計算可能（または決定可能、再帰的）である。集合が計算不可能（または決定不能）である場合、その集合は計算不可能である。

サブセット${\displaystyle S}$自然数の計算は、全計算関数が存在する場合に可能となる。${\displaystyle f}$すなわち、

${\displaystyle f(x)=1}$もし${\displaystyle x\in S}$

${\displaystyle f(x)=0}$もし${\displaystyle x\notin S}$。

言い換えれば、集合は${\displaystyle S}$指標関数が計算可能であるのは、$\displaystyle \mathbb {1} _{S}}$計算可能です。

• すべての再帰言語は計算可能である。
• 自然数の 有限部分集合または余有限部分集合はすべて計算可能である。
  • 空集合は計算可能である。
  • 自然数の全体は計算可能である。
  • すべての自然数は計算可能である。^{[注1 ]}
• 素数の部分集合は計算可能である。
• ゲーデル数の集合は計算可能である。^{[注2 ]}

AとBはどちらもこのセクションにおける集合です。

• Aが計算可能であれば、Aの補集合も計算可能である。
• AとBが計算 可能であれば、次のことが成り立つ。
  • A ∩ Bは計算可能である。
  • A ∪ Bは計算可能である。
  • カントール対合関数によるA × Bの像は計算可能である。

一般に、計算可能な集合を計算可能な関数で処理した像は、計算可能列挙可能であるが、計算可能ではない可能性がある。

• A が計算可能であるのは、 AとAの補集合が両方とも計算可能列挙可能 (ce) である場合に限る 。
• 計算可能な集合の、全計算可能な関数による逆像は計算可能である。
• 計算可能な集合に対する全計算可能な全単射による像は計算可能である。

Aが計算可能であるのは、それがレベルにある場合に限る。${\displaystyle \Delta _{1}^{0}}$算術階層の。

Aが計算可能であるのは、Aが非減少全計算可能関数の像（または値域）であるか、または空集合である場合に限る。

• 計算可能列挙可能
• 決定可能性（論理学）
• 再帰的に列挙可能な言語
• 再帰言語
• 再帰

• カットランド、N. 『計算可能性』ケンブリッジ大学出版局、ケンブリッジ・ニューヨーク、1980年。ISBN 0-521-22384-9; ISBN 0-521-29465-7
• ロジャース、H. 『再帰関数と有効計算可能性の理論』 MIT Press。ISBN 0-262-68052-1; ISBN 0-07-053522-1
• Soare, R.再帰的に列挙可能な集合と次数。数理論理学の展望。Springer-Verlag、ベルリン、1987年。ISBN 3-540-15299-7

• サハロフ、アレックス。「再帰的集合」。MathWorld 。