ナンバリング (計算可能性理論)

ナンバリング（）は自然数から対象の集合への対応付けをいう。対象としては例えば関数、有理数、グラフ、形式言語などである。ナンバリングは自然数に対して定義された計算可能性や関連する概念を他の種類の対象に一般化する際に用いることができる。
よく知られた例としては一階述語論理のゲーデル数化や部分計算可能関数のアクセプタブル・ナンバリングがある。
定義と例.
集合 formula_1 のナンバリングとは formula_2 から formula_1 の上への部分関数をいう（Ershov 1999:477）。ナンバリング ν の "i" に於ける値は（定義されるなら）しばしば formula_4 の代わりに ν"i" と書かれる。
例えば、formula_2 の全ての有限部分集合からなる集合は
なるナンバリングを持つ（Ershov 1999:477）。
2つ目の例として、部分計算可能関数のナンバリング formula_8 は、 "W"("i") を φ"i" の定義域と定めることで帰納的可算集合のナンバリング "W" として利用できる。
ナンバリングの種類.
ナンバリングが全域的とはそれが全域関数であることをいう。もしナンバリングの定義域が帰納的可算ならば、同値な全域的ナンバリングが存在する（ナンバリングの同値性は後で定義される）。
ナンバリング η が決定可能とは集合 formula_9 が決定可能であることをいう。
ナンバリング η が一価とは η("x") = η("y") と "x"="y" が同値であるときにいう。換言すれば η が単射であるときにいう。部分計算可能関数の一価ナンバリングはフリードバーグ・ナンバリングと呼ばれる。
ナンバリングの比較.
全てのナンバリングからなる集合には半順序付けが存在する。 いま
と
を2つのナンバリングとする。このとき formula_12 が formula_13 に還元可能 formula_14 とは、
が成り立つときをいう。
もし formula_14 かつ formula_17 ならば formula_12 は formula_13 と同値といい、これを formula_20 と書く。
計算可能なナンバリング.
集合 "S" の対象が十分に"構成的"であるとき、ナンバリングは実効的にデコードできるものに注目するのが一般的である（Ershov 1999:486）。例えば "S" が帰納的可算集合からなるとき、 ナンバリング η が計算可能とは "y"∈η("x") なる対 ("x","y") の集合が帰納的可算であることをいう。同様に部分関数のナンバリング "g" が計算可能とは関係 "R"("x","y","z") = "g"("x")("y") = "z"" が帰納的可算であることをいう（Ershov 1999:487）。
計算可能なナンバリングがprincipalとは任意の計算可能なナンバリングをそれに還元できるときにいう。例えば formula_2 の全てのr.e.部分集合の集合や全ての部分計算可能関数の集合などはprincipalナンバリングを持つ（Ershov 1999:487）。後者についてはしばしばアクセプタブル・ナンバリングと呼ばれる。