コンプリート・ナンバリング

コンプリート・ナンバリングとは

計算可能性理論において、コンプリート・ナンバリングは、集合の要素に番号を割り当てる方法（ナンバリング）の一種です。この概念は、アクセプタブル・ナンバリングという既存のナンバリングの概念をさらに一般化したもので、1963年にアナトリー・マルツェフによって導入されました。

背景

アクセプタブル・ナンバリングは、計算可能関数の集合に対して定義されるナンバリングであり、クリーネの再帰定理やライスの定理などの重要な定理がこのナンバリングを持つ集合で成立することが知られています。コンプリート・ナンバリングは、これらの定理がより広い範囲の集合で成立するように、アクセプタブル・ナンバリングを一般化したものとして導入されました。

定義

集合 \(A\) のナンバリング \(
u\) がコンプリートであるとは、以下の条件を満たすことです。

任意の部分計算可能関数 \(f\) に対して、ある全域計算可能関数 \(h\) が存在し、すべての \(i\) に対して次の条件が成り立つ。

\(
u \circ h(i) = \begin{cases}
u \circ f(i) & \text{if } i \in \text{dom}(f) \\ a & \text{otherwise} \end{cases}\)

ここで \(\text{dom}(f)\) は、部分計算可能関数 \(f\) の定義域を表し、\(a\) は集合 \(A\) の任意の要素です。

この定義は、\(f\) が定義されている入力に対しては、\(f\) の計算結果（\(
u\) を適用したもの）が \(h\) の計算結果と一致し、\(f\) が定義されていない入力に対しては、\(h\) の計算結果が任意の値 \(a\) になることを意味します。


また、ナンバリング \(
u\) がプリコンプリートであるとは、次の条件を満たすことを言います。

\(
u \circ f(i) =
u \circ h(i) \quad i \in \text{dom}(f)\)

これは、関数\(f\)が定義されている入力に対しては、\(f\)の計算結果（\(
u\)を適用したもの）が\(h\)の計算結果と一致することを意味します。

例

シングルトン集合のナンバリング: 任意の要素が一つだけの集合（シングルトン集合）に対するナンバリングは常にコンプリートになります。これは、集合が一つしか要素を持たないため、\(a\) の値に関わらず条件が満たされるためです。
自然数上の恒等関数: 自然数をそのまま返す恒等関数は、コンプリートなナンバリングではありません。なぜなら、恒等関数は、任意の入力に対して定義されている必要があり、定義されていない場合を扱うことができないからです。
アクセプタブル・ナンバリング: アクセプタブル・ナンバリングは、プリコンプリートなナンバリングの一種です。これは、アクセプタブル・ナンバリングが持つ性質として、部分計算可能関数に対して、全域計算可能関数が対応する形で存在することが挙げられるからです。

重要なポイント

コンプリート・ナンバリングの重要な点は、アクセプタブル・ナンバリングが持っていた性質を、より広い範囲の集合に拡張できるという点です。これにより、計算可能性に関する様々な定理が、より一般的な形で適用できるようになりました。例えば、クリーネの再帰定理やライスの定理などは、元々はアクセプタブル・ナンバリングを持つ計算可能関数の集合に対して証明されたものですが、コンプリート・ナンバリングを持つ任意の集合でも成立することが示されています。

まとめ

コンプリート・ナンバリングは、計算可能性理論において重要な役割を果たす概念であり、様々な定理の一般化に貢献しています。その定義は、部分計算可能関数と全域計算可能関数との関係性を明確に示しており、計算可能性理論の理解を深める上で欠かせない概念です。

参考文献

A.I. Mal'tsev, Sets with complete numberings. Algebra i Logika, 1963, vol. 2, no. 2, 4-29 (Russian)

関連項目

ナンバリング
フリードバーグ・ナンバリング

もう一度検索