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

ナンバリング（英: numbering）は自然数から対象の集合への対応付けをいう。対象としては例えば関数、有理数、グラフ、形式言語などである。ナンバリングは自然数に対して定義された計算可能性や関連する概念を他の種類の対象に一般化する際に用いることができる。

よく知られた例としては一階述語論理のゲーデル数化や部分計算可能関数のアクセプタブル・ナンバリングがある。

定義と例

集合 $S$ のナンバリングとは $\mathbb {N}$ から $S$ の上への部分関数をいう（Ershov 1999:477）。ナンバリング ν の i に於ける値は（定義されるなら）しばしば $\nu (i)$ の代わりに ν_i と書かれる。

例えば、 $\mathbb {N}$ の全ての有限部分集合からなる集合は

\gamma (\emptyset )=0

\gamma (\{a_{0},\ldots ,a_{k}\})=\sum _{i\leq k}2^{a_{i}}

なるナンバリングを持つ（Ershov 1999:477）。

2つ目の例として、部分計算可能関数のナンバリング $\varphi _{i}$ は、 W(i) を φ_i の定義域と定めることで帰納的可算集合のナンバリング W として利用できる。

ナンバリングの種類

ナンバリングが全域的とはそれが全域関数であることをいう。もしナンバリングの定義域が帰納的可算ならば、同値な全域的ナンバリングが存在する（ナンバリングの同値性は後で定義される）。

ナンバリング η が決定可能とは集合 $\{(x,y):\eta (x)=\eta (y)\}$ が決定可能であることをいう。

ナンバリング η が一価とは η(x) = η(y) と x=y が同値であるときにいう。換言すれば η が単射であるときにいう。部分計算可能関数の一価ナンバリングはフリードバーグ・ナンバリングと呼ばれる。

ナンバリングの比較

全てのナンバリングからなる集合には半順序付けが存在する。いま

\nu _{1}:\subseteq \mathbb {N} \to S_{1}

と

\nu _{2}:\subseteq \mathbb {N} \to S_{2}

を2つのナンバリングとする。このとき $\nu _{1}$ が $\nu _{2}$ に還元可能 $\nu _{1}\leq \nu _{2}$ とは、

\exists f\in \mathbf {P} ^{(1)}\,\forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i)

が成り立つときをいう。

もし $\nu _{1}\leq \nu _{2}$ かつ $\nu _{1}\geq \nu _{2}$ ならば $\nu _{1}$ は $\nu _{2}$ と同値といい、これを $\nu _{1}\equiv \nu _{2}$ と書く。

計算可能なナンバリング

集合 S の対象が十分に"構成的"であるとき、ナンバリングは実効的にデコードできるものに注目するのが一般的である（Ershov 1999:486）。例えば S が帰納的可算集合からなるとき、ナンバリング η が計算可能とは y∈η(x) なる対 (x,y) の集合が帰納的可算であることをいう。同様に部分関数のナンバリング g が計算可能とは関係 R(x,y,z) = g(x)(y) = z" が帰納的可算であることをいう（Ershov 1999:487）。

計算可能なナンバリングがprincipalとは任意の計算可能なナンバリングをそれに還元できるときにいう。例えば $\mathbb {N}$ の全てのr.e.部分集合の集合や全ての部分計算可能関数の集合などはprincipalナンバリングを持つ（Ershov 1999:487）。後者についてはしばしばアクセプタブル・ナンバリングと呼ばれる。

参考文献

Y.L. Ershov (1999), "Theory of numberings", Handbook of Computability Theory, Elsevier, pp. 473–506.
V.A. Uspenskiĭ, A.L. Semenov (1993), Algorithms: Main Ideas and Applications, Springer.