2002年11月16日 作成 計算可能関数 >> 目次 (作成日順)
2008年 1月 1日 補遺  


 
 今回は、「計算可能性」 について述べる。

 
 ゲーデル が不完全性定理を証明して以後、以下の 2つが注目を浴びるようになった。

  (1) 「存在定理」 の証明法
  (2) 「計算可能関数」 の定義

 「存在定理」 については──理論の 「整合性」 および 「完全性」 を検証するために──、不動点定理カテゴリー を使うやりかたが導入された (これらのやりかたについては、拙著 「論理 データベース 論考」 136ページ を参照されたい)。

 ゲーデル は、不完全性定理の証明のなかで、原始帰納的関数を導入したが──ゲーデル の論文では、40数個ほど定義されているが──、以後、原始帰納的関数を一般化した計算可能関数が (以下のように) いくつか提示された。

  (1) チャーチ の λ-定義可能関数 (λ-definable) [ 1935年 ]
  (2) クリーニ の一般帰納的関数 (general recursive) [ 1936年 ]
  (3) チューリング の計算可能関数 (computable) [ 1936年 ]
  (4) ゲーデル の算定可能関数 (reckonable) [ 1936年 ]

 以上のいずれの考えかたも、以下の点を定義としている。

 「計算可能関数とは、アルゴリズム が存在する関数のことである。」 (ゲーデル、1933年)

 以上の関数のすべては同値であることが証明されている。
 上述した関数が一般帰納的関数と同値であったので、チャーチ は、以下の仮説を提唱した (1936年)。それを 「チャーチ の提唱」という。

 「計算可能関数とは一般帰納的関数のことであり、決定可能述語とは一般帰納的述語のことである。

 
 さて、チューリング は、計算可能性を定式化するために、概念的な計算機械を考えた。
 いわゆる 「チューリング・マシン」 である。コンピュータ の起点となった (概念的な) 計算機械である。

 次回は、「チューリング・マシン」 を概説する──というよりも、小生は システム・エンジニア なので、「チューリング・マシン」 を記述するために、前回、不完全性定理を提示して、今回、「計算可能性」 を扱った、という次第です。また、「哲学的文学青年」 の性質が強い小生は、(数学的な) 「存在定理」 および (哲学的な) 「存在論」 にも多大な関心を抱いています。□

 



[ 補遺 ] (2008年 1月 1日)

 私は、数学の専門家ではないので、本 エッセー のなかに示した いくつかの計算可能関数を詳しく研究した訳ではないことを断っておきます。帰納的関数を学習するには、以下の書物を読んで下さい。

 (1) 「帰納的関数」、廣瀬 健、共立出版、1989年。
 (2) 「帰納的関数と述語」、篠田寿一、河合文化教育研究所、1997年。

 いずれの書物も 「本格的な」 入門書です──「数学基礎論」 を専門的に志すひと向けの書物でしょうね。私は、いずれも、途中で挫折して読破していないことを正直に告白しておきます。私が習得している知識は、前々回 (160ページ 参照) に記述した 「原始帰納的関数」 (と 「帰納的に可算」の概念) 程度です。そして、本 エッセー で述べた いくつかの計算可能関数を丁寧に学習しないまま、 「計算可能関数 = アルゴリズム」 として覚えて──数学の専門家たちが それを証明しているので、ただただ、信んじて──、それを前提にして、チューリング・マシーン を やや丁寧に学習した、という次第です。数学者に怒られるかもしれないのですが、数学を専門にしていない エンジニア は、本 エッセー で示した計算可能関数のすべてを丁寧に学習しなくてもいいでしょう。

 N を自然数の全体として、集合 S ⊆ Nn に対して、(x1, x2, ... , xn) ∈ S のとき 0 、そうでないとき 1 を対応させる関数 Cp (x1, x2, ... , xn) を S の 「特徴関数 (characteristic function)」 と云い、Cp が 「原始帰納的」 なら、P を 「原始帰納的述語」 と云います。
 原始帰納的関数は、ほとんどの関数をふくんでいて、コンピュータ で扱う関数のほとんどが原始帰納的関数であるといっても良いそうです。ただし、原始帰納的関数は計算可能な すべての関数をふくんでいる訳ではないそうです──たとえば、アッケルマン 関数は原始帰納的関数ではないとのこと。

 さて、P を n + 1 変数述語として、(x1, x2, ... , xn) に対して、P (x1, x2, ... , xn, y) を真にする最小の y を考えて、y が存在しないときには、無定義 (undefined) である n 変数関数を μyP (x1, x2, ... , xn, y) とします。なお、μy を μ-operator と云います。

 「帰納的部分関数」 とは、原始帰納的関数の初期関数からはじめて、原始帰納的関数を作る操作を適用して、さらに、以下の関数 f を作る操作を有限回適用して得られる関数を云います。なお、「無定義・部分関数・全域関数」 の定義については、本 ホームページ 144 ページ を参照して下さい。

    g (x1, x2, ... , xn, y).
    f (x1, x2, ... , xn) = μy (g (x1, x2, ... , xn, y) = 0).

 もし、g (x1, x2, ... , xn, y) = 0 となる y が存在しなければ、関数 g が全域的であっても、関数 f は定義されないので、関数 f は全域的であるとは限らないでしょうね。
 さて、任意の (x1, x2, ... , xn) ∈ Nn に対して、g (x1, x2, ... , xn, y) = 0 となる y が、つねに、存在するとき、関数 g を 「正則 (regular)」 であると云います。そして、μ-operator を正則関数に対して適用して得られる帰納的部分関数を 「帰納的関数」 または 「一般帰納的関数」 と云います。集合や述語が 「帰納的」 であるという意味は、その特徴関数が帰納的であるということです。

 集合 N の部分集合 S が 「帰納的に可算」 であるとは、以下の帰納的関数 f が存在するときです (空集合もふくみます)。

    f (N) = { f (0), f (1), ・・・ } = S.

 ちなみに、このとき、 f は、S を列挙する (enumerate) と云います。
 さて、帰納的集合 S ⊆ N は帰納的に可算ですが、その逆は真ではない。すなわち、「帰納的に可算な集合」 と 「帰納的集合」 は、ちがう、という点に注意して下さい。「帰納的に可算な集合」 A において、x ∈ A であるかどうかは、列挙していけば、x が、いずれ、現れるかもしれないのですが、もし、列挙が 「無限」 に続くのであれば、¬ (x ∈ A) を判断できないかもしれない。「帰納的集合」 であれば、その特徴関数 CSが計算可能であるので、x ∈ S であるか、¬ (x ∈ S) であるかを判断できます。
 なお、S ⊆ N が帰納的に可算であって、かつ、その補集合 Sc = N − S が帰納的に可算であれば、S は帰納的です。

 「任意の (x1, x2, ... , xn) ∈ Nn に対して、P (x1, x2, ... , xn) が成立するかどうかを決定する」 アルゴリズム の作成を 「決定問題 (decision problem)」 と云います。もし、このような アルゴリズム を作ることができるなら、P は帰納的 (計算可能) であるということです。同じように、集合 S ⊆ Nn についても、「任意の (x1, x2, ... , xn) ∈ Nn に対して、(x1, x2, ... , xn) ∈ S が成立するかどうかを決定する」 アルゴリズム の作成も 「決定問題」 と云います。ちなみに、もし、自然数以外の集合 (あるいは、述語) であれば、ゲーデル 数を使って、自然数の対応することができます。そして、決定できる アルゴリズム を作ることができれば 「決定可能 (decidable、あるいは solvable)」 と云い、そうでなければ 「決定不能 (undecidable、あるいは unsolvable)」 と云います。




  << もどる HOME すすむ >>
  ベーシックス