計算可能同型性

計算可能性理論では、の像をに制限すると に等しくなるような全計算可能かつ全単射な関数が存在する場合、 2 つの自然数集合は計算可能同型または再帰的に同型であるという。 ${\displaystyle A,B}$ ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$${\displaystyle f}$${\displaystyle A\subseteq \mathbb {N} }$${\displaystyle B\subseteq \mathbb {N} }$${\displaystyle f(A)=B}$

さらに、となるような計算可能な一対一が存在する場合、2 つの番号付け と は計算可能同型であると呼ばれます。計算可能同型の番号付けは、集合上の計算可能性の同じ概念を誘導します。 ${\displaystyle \nu}$${\displaystyle \mu}$${\displaystyle f}$${\displaystyle \nu =\mu \circ f}$

マイヒル同型定理によれば、計算可能同型性の関係は相互一対一還元性の関係と一致する。^[1]

• ロジャース、ハートリー・ジュニア（1987）、再帰関数と実効計算可能性の理論（第2版）、ケンブリッジ、マサチューセッツ州：MITプレス、ISBN 0-262-68052-1、MR  0886890。