ナンバリング (計算可能性理論)
集合 S の対象が十分に"構成的"であるとき、ナンバリングは実効的にデコードできるものに注目するのが一般的である(Ershov 1999:486)。例えば S が帰納的可算集合からなるとき、 ナンバリング η が計算可能とは y∈η(x) なる対 (x,y) の集合が帰納的可算であることをいう。同様に部分関数のナンバリング g が計算可能とは関係 R(x,y,z) = g(x)(y) = z" が帰納的可算であることをいう(Ershov 1999:487)。
計算可能なナンバリングがprincipalとは任意の計算可能なナンバリングをそれに還元できるときにいう。例えば N {\displaystyle \mathbb {N} } の全てのr.e.部分集合の集合や全ての部分計算可能関数の集合などはprincipalナンバリングを持つ(Ershov 1999:487)。後者についてはしばしばアクセプタブル・ナンバリングと呼ばれる。
ナンバリング(英: numbering)は自然数から対象の集合への対応付けをいう。対象としては例えば関数、有理数、グラフ、形式言語などである。ナンバリングは自然数に対して定義された計算可能性や関連する概念を他の種類の対象に一般化する際に用いることができる。
よく知られた例としては一階述語論理のゲーデル数化や部分計算可能関数のアクセプタブル・ナンバリングがある。