2002年11月16日 作成 | 計算可能関数 | >> 目次 (テーマ ごと) |
2008年 1月 1日 補遺 |
(1) 「存在定理」 の証明法 「存在定理」 については──理論の 「整合性」 および 「完全性」 を検証するために──、不動点定理や カテゴリー を使うやりかたが導入された (これらのやりかたについては、拙著 「論理 データベース 論考」 136ページ を参照されたい)。 ゲーデル は、不完全性定理の証明のなかで、原始帰納的関数を導入したが──ゲーデル の論文では、40数個ほど定義されているが──、以後、原始帰納的関数を一般化した計算可能関数が (以下のように) いくつか提示された。
(1) チャーチ の λ-定義可能関数 (λ-definable) [ 1935年 ] 以上のいずれの考えかたも、以下の点を定義としている。 「計算可能関数とは、アルゴリズム が存在する関数のことである。」 (ゲーデル、1933年)
以上の関数のすべては同値であることが証明されている。 「計算可能関数とは一般帰納的関数のことであり、決定可能述語とは一般帰納的述語のことである。」 次回は、「チューリング・マシン」 を概説する──というよりも、小生は システム・エンジニア なので、「チューリング・マシン」 を記述するために、前回、不完全性定理を提示して、今回、「計算可能性」 を扱った、という次第です。また、「哲学的文学青年」 の性質が強い小生は、(数学的な) 「存在定理」 および (哲学的な) 「存在論」 にも多大な関心を抱いています。□ |
[ 補遺 ] (2008年 1月 1日)
私は、数学の専門家ではないので、本 エッセー のなかに示した いくつかの計算可能関数を詳しく研究した訳ではないことを断っておきます。帰納的関数を学習するには、以下の書物を読んで下さい。
(1) 「帰納的関数」、廣瀬 健、共立出版、1989年。 いずれの書物も 「本格的な」 入門書です──「数学基礎論」 を専門的に志すひと向けの書物でしょうね。私は、いずれも、途中で挫折して読破していないことを正直に告白しておきます。私が習得している知識は、前々回 (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).
もし、g (x1, x2, ... , xn, y) = 0 となる y が存在しなければ、関数 g が全域的であっても、関数 f は定義されないので、関数 f は全域的であるとは限らないでしょうね。 集合 N の部分集合 S が 「帰納的に可算」 であるとは、以下の帰納的関数 f が存在するときです (空集合もふくみます)。 f (N) = { f (0), f (1), ・・・ } = S.
ちなみに、このとき、 f は、S を列挙する (enumerate) と云います。 「任意の (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)」 と云います。
|
<< もどる | ベーシックス | すすむ >> | |
数学基礎論 |