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

ナンバリングとは

ナンバリング（numbering）は、数学と計算理論における重要な概念であり、自然数の集合から特定の対象の集合への対応付けを指します。この対応付けは、単に数を与えるだけでなく、計算可能性や関連する概念を、関数、有理数、グラフ、形式言語など、さまざまな種類の対象に一般化する強力な手段となります。

定義と例

集合Sのナンバリングとは、自然数NからSへの部分関数です。ナンバリングνにおけるiの値は、ν(i)と表記される代わりに、しばしばνiと書かれます。例えば、自然数Nの有限部分集合の集合は、次のようなナンバリングを持ちます。

γ(∅) = 0
γ({a₀,...,ak}) = ∑(i≤k) 2^(ai)


別の例として、部分計算可能関数のナンバリングφiは、W(i)をφiの定義域とすることで、帰納的可算集合のナンバリングWとして利用できます。

ナンバリングの種類

ナンバリングには、いくつかの重要な種類があります。

全域的ナンバリング: これは、ナンバリングが全域関数である場合を指します。もしナンバリングの定義域が帰納的可算ならば、同値な全域的ナンバリングが存在します。
決定可能なナンバリング: ナンバリングηが決定可能であるとは、集合{(x,y):η(x)=η(y)}が決定可能であることを言います。
一価ナンバリング: ナンバリングηが一価であるとは、η(x)=η(y)がx=yと同値である場合を指します。言い換えれば、ηが単射である場合です。部分計算可能関数の一価ナンバリングは、フリードバーグ・ナンバリングと呼ばれます。

ナンバリングの比較

ナンバリングの集合には、半順序付けが存在します。2つのナンバリングν₁:⊆N→S₁とν₂:⊆N→S₂があるとき、ν₁がν₂に還元可能（ν₁ ≤ ν₂）であるとは、ある部分計算可能関数fが存在し、すべてのi∈Domain(ν₁)に対して、ν₁(i) = ν₂(f(i))が成り立つことを言います。もしν₁ ≤ ν₂かつν₁ ≥ ν₂ならば、ν₁とν₂は同値であり（ν₁ ≡ ν₂）、この関係はナンバリングの比較に重要な役割を果たします。

計算可能なナンバリング

対象が十分に「構成的」である場合、実効的にデコードできるナンバリングに着目するのが一般的です。例えば、Sが帰納的可算集合からなる場合、ナンバリングηが計算可能であるとは、y∈η(x)なる対(x,y)の集合が帰納的可算であることを意味します。同様に、部分関数gのナンバリングが計算可能とは、関係R(x,y,z) = "g(x)(y) = z"が帰納的可算であることを指します。

計算可能なナンバリングがprincipalであるとは、任意の計算可能なナンバリングをそれに還元できる場合を言います。例えば、自然数Nの全ての帰納的可算部分集合の集合や、全ての部分計算可能関数の集合などは、principalナンバリングを持ちます。後者の場合、アクセプタブル・ナンバリングと呼ばれることもあります。

まとめ

ナンバリングは、自然数と他の数学的対象との間の橋渡しをする概念であり、計算可能性理論において中心的な役割を果たします。さまざまな種類のナンバリングやその比較を通じて、計算理論における対象の構造や性質を深く理解することができます。特に、計算可能なナンバリングは、計算機科学におけるアルゴリズムやプログラミングの基礎となる重要な概念です。

関連項目

ゲーデル数
コンプリート・ナンバリング
フリードバーグ・ナンバリング

参考文献

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.

もう一度検索