ナンバリング (計算可能性理論)のソースを表示

{{Otheruses|ナンバリング|鉄道駅に付与されている番号|駅ナンバリング}}'''ナンバリング'''（{{Lang-en-short|''numbering''}}）は[[自然数]]から対象の[[集合]]への対応付けをいう。対象としては例えば関数、[[有理数]]、[[グラフ理論#|グラフ]]、[[形式言語]]などである。ナンバリングは自然数に対して定義された計算可能性や関連する概念を他の種類の対象に一般化する際に用いることができる。

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

== 定義と例 ==
集合 <math>S</math> の'''ナンバリング'''とは <math>\mathbb{N}</math> から <math>S</math> の[[全射|上への]][[部分関数]]をいう（Ershov 1999:477）。ナンバリング &nu; の ''i'' に於ける値は（定義されるなら）しばしば <math>\nu(i)</math> の代わりに &nu;<sub>''i''</sub> と書かれる。

例えば、<math>\mathbb{N}</math> の全ての有限部分集合からなる集合は
:<math>\gamma(\emptyset) = 0</math>
:<math>\gamma(\{a_0, \ldots, a_k\}) = \sum_{i \leq k} 2^{a_i}</math>
なるナンバリングを持つ（Ershov 1999:477）。

2つ目の例として、部分計算可能関数のナンバリング <math>\varphi_i</math> は、 ''W''(''i'') を &phi;<sub>''i''</sub> の[[定義域]]と定めることで[[帰納的可算集合]]のナンバリング ''W'' として利用できる。

== ナンバリングの種類 ==

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

ナンバリング &eta; が'''決定可能'''とは集合 <math>\{ (x,y) : \eta(x) = \eta(y)\}</math> が決定可能であることをいう。

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

== ナンバリングの比較 ==

全てのナンバリングからなる集合には[[半順序集合|半順序付け]]が存在する。 いま
:<math>\nu_1: \subseteq \mathbb{N} \to S_1</math>
と
:<math>\nu_2: \subseteq \mathbb{N} \to S_2</math>
を2つのナンバリングとする。このとき <math>\nu_1</math> が <math>\nu_2</math> に'''還元可能''' <math>\nu_1 \le \nu_2</math> とは、
:<math>\exists f \in \mathbf{P}^{(1)} \, \forall i \in \mathrm{Domain}(\nu_1) : \nu_1(i) = \nu_2 \circ f(i)</math>
が成り立つときをいう。

もし <math>\nu_1 \le \nu_2</math> かつ <math>\nu_1 \ge \nu_2</math> ならば  <math>\nu_1</math> は <math>\nu_2</math> と'''同値'''といい、これを <math>\nu_1 \equiv \nu_2</math> と書く。

== 計算可能なナンバリング ==

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

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

== 関連項目 ==
* [[ゲーデル数]]
* [[コンプリート・ナンバリング]]
* [[フリードバーグ・ナンバリング]]

==参考文献==
* Y.L. Ershov (1999), "Theory of numberings", ''Handbook of Computability Theory'', Elsevier, pp.&nbsp;473&ndash;506.
* V.A. Uspenskiĭ, A.L. Semenov (1993), ''Algorithms: Main Ideas and Applications'', Springer.

{{DEFAULTSORT:なんはりんく}}
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]