帰納的可算集合

帰納的可算集合について

帰納的可算集合（Recursively Enumerable Set）は、計算理論において重要な役割を果たす集合の一種です。これは、あるアルゴリズムによってその要素を枚挙できる、または特定の条件を満たす要素を特定できる集合を指します。この概念は、計算可能性の限界を理解する上で非常に重要です。

定義と様々な表現

自然数の集合 S が帰納的可算であるとは、以下のいずれかの条件が成り立つことを指します。

1. 半決定可能性:
あるアルゴリズム（部分再帰関数）が存在し、そのアルゴリズムに S の要素を入力すると停止し、S の要素でないものを入力すると停止しない（または定義されない）。
具体的には、関数 f(x) が存在し、x が S の要素ならば f(x) = 0 となり、x が S の要素でなければ f(x) は未定義となる。

2. 計算可枚挙性:
S の全ての要素を、アルゴリズムを用いてリストとして生成できる。このアルゴリズムは、必要に応じて無限に動作することができる。
S の要素を s1, s2, s3, ... のように列挙できる。

これらの定義は同値であり、同じ集合の性質を表しています。帰納的可算集合は、その定義から「半決定可能集合」や「計算可枚挙集合」と呼ばれることもあります。略記として「r.e.」または「c.e.」が用いられることもあります。

形式的な定義

形式的には、自然数の集合 S が帰納的可算であるとは、S がある部分再帰関数 f の定義域と一致することを意味します。つまり、f(x) が定義される必要十分条件が、x が S の要素であるということです。

この定義は、可算集合 A にも拡張できます。A の各要素をゲーデル数で表し、対応するゲーデル数の集合が帰納的可算であれば、A の部分集合も帰納的可算となります。

同値な定式化

以下は、自然数の集合 S が帰納的可算であることの、同値な表現です。

部分再帰関数の値域: S はある部分再帰関数の値域である。
全体再帰関数の値域: S はある全体再帰関数の値域であるか、空集合である。S が無限集合の場合、この関数は単射でも良い。
原始再帰関数の値域: S はある原始再帰関数の値域であるか、空集合である。S が無限集合でも単射とは限らない。
ディオファントス方程式: S の要素 x は、ある整数係数多項式 p(x, a, b, c, d, e, f, g, h, i) = 0 を満たす自然数 a, b, c, d, e, f, g, h, i が存在する。

具体例

帰納的集合: 全ての帰納的集合は帰納的可算集合ですが、逆は成り立ちません。
帰納的可算言語: 形式言語における帰納的可算な部分集合。
公理系から導かれる文: 帰納的可算な公理系から導かれる全ての文の集合。
ディオファントス集合: マチャセビッチの定理により、全ての帰納的可算集合はディオファントス集合です（逆も真）。
単純集合: 帰納的可算だが帰納的でない集合の例。
創造的集合: 帰納的可算だが帰納的でない集合の別の例。
停止問題の符号化: あるチューリングマシンが停止する入力パラメータ群。
関数値決定問題の符号化: ある関数値が定まる入力パラメータ群。

性質

閉包性: 帰納的可算集合 A と B に対して、A ∩ B、A ∪ B、A × B も帰納的可算集合となる。
逆像: 部分再帰関数における帰納的可算集合の逆像もまた帰納的可算集合。
算術的階層: 帰納的可算集合は、算術的階層の Σ₁⁰ レベルに属する。
補集合: 集合 T の補集合が帰納的可算である場合、T は co-r.e. (Π₁⁰) と呼ばれる。
帰納的集合との関係: 集合 A が帰納的である必要十分条件は、A とその補集合がともに帰納的可算集合であること。
互いに素な集合: 互いに素な帰納的可算集合の対は、帰納的に分離可能である場合とそうでない場合がある。しかし、任意の互いに素な co-r.e. 集合対は帰納的に分離可能である。
* 直和分解: 任意の帰納的でない帰納的可算集合は、2つの互いに素な帰納的でない帰納的可算集合に直和分解できる。

注意点

チャーチ＝チューリングのテーゼによれば、計算可能な関数は全てチューリングマシンで計算可能であるため、集合が帰納的可算であることは、アルゴリズムによって枚挙可能であることと等価です。ただし、このテーゼは形式的な公理ではないため、帰納的可算集合の形式的な定義としては用いることはできません。

また、近年の文献では、帰納的可算集合を部分関数の「定義域」として定義することが一般的になっています。これは、より一般化された再帰理論において、この定義の方が自然であるためです。

まとめ

帰納的可算集合は、計算理論において非常に重要な概念であり、計算可能性の限界を理解する上で不可欠です。様々な表現や性質を持つこの集合は、理論計算機科学の様々な分野で活用されています。この概念を理解することで、計算の本質についてより深く洞察することができるでしょう。

もう一度検索