再帰理論 Recursion Theory


|| 計算できるかどうかとか、効率的かどうかとか

『人間に扱えるか』についてのあれこれを調べます。

その「人間に扱えるか」の指標として、

これは「小さな自然数」と密接に関係してます。

スポンサーリンク





目次


計算可能性「答えが出せるかどうか」

   チャーチ=チューリングのテーゼ「計算可能性の定義」

   計算可能関数「計算可能性を定義するもの」

   帰納的・再帰関数「計算可能性の定義に使われる関数」




チューリングマシン「一番いろんなものを計算できる機械」

   神託機械「マシンの停止問題を解消するための機械」




主要な性質

   実効性「証明の妥当性を確認する方法があるという性質」

   決定可能性「論理式がその元の理論のものか確認できる性質」


   決定問題「あらゆるものの是非を決めるために作られる」



計算複雑性「主にどれくらいの時間で計算できるかとか」

   チューリング次数「計算の複雑さを表す指標」




再帰定理「全部自分でいけるよ、みたいな感じ」








なんじゃこれはと自分も思いましたが、これは非常に重要です。

なにせ、いわば「形式言語」(プログラミングなど)は、

これを基軸として作られています。




というのも、例えば「無限」に処理が続いてしまって、

「答えが出ない」ものに価値はありません。



なにか「明確な価値」あるものは、

すべて「有限」の処理で「答えが出る」ものに限られるわけです。

それも『人が生きている間に』っていう時間制限付きで。




この「有限性」についての考察が、

『再帰理論』の本質になります。




ですから「計算可能性」やら「計算複雑性」やら、

主にそんなのを扱うわけですね。






というわけで、さっそく見ていきましょう。







計算可能性理論 Computability Theory


|| 計算できるってどういうことなの?

そのまま「計算できる」ってなに? という感じの理論です。

この疑問に沿って色々調べてます。



「再帰理論」っていうよりこっちで呼んだ方が意味は分かり易いです。

こっちで呼ぶべきだって人は一定数いるみたいですね。




主要な研究対象は「計算可能関数」と、

「計算可能」な「クラスが持つ構造」についてです。

後者は「クラス」と「構造」が分からんと意味不明ですね。




これは「計算機科学」にそのまま流用される理論です。

「これ答え出せるんかいな?」っていうのを調べるわけですから。




そしてここが重要ですが、

計算可能性」は「定義」です。

「定理」として「証明されたもの」ではありません。




これは↓の「提案」によって採用されました。

いわば『妥当性が認められた人間のルール』です。






チャーチ=チューリングのテーゼ Church’s Thesis


「計算できる関数」と「帰納的関数」は同じだよ、という主張。



実際、この「定義」が『再帰理論』の核になってます。

「非形式」を「形式化」した、かなり重要な一例です。




それと「実際に計算できるか」ってことも重要なので、

それも『実際に計算する方法』で定義してます。




言っちゃえば「実現方法の有無」の話です。

『計算機』の機能から「計算できる」を定義してます。

最有力なのは「チューリングマシン」ですね。



この「チューリングマシン」という仮想機械から、

それが「計算可能」であるかを判定できます。

この計算機で計算できないものは「計算可能」ではありません。






計算可能関数 Computable Function


|| 意味は分かっても中身が分からん

これはそのまま「答えが出る」関数のことですね。

「答えが出せるアルゴリズムが存在する」って言っても良いです。



まあ、そんなわけですから、

逆に「アルゴリズムがある」関数は、全て「計算可能」になります。




元は「帰納的関数」「再帰関数」などと呼ばれてました。

なので、定義に関してはこれと同じです。

「チューリングのテーゼ」以来、そう定義されているので。






帰納的・再帰関数 Recursive Function


|| 計算できるやつとして名指しされたやつ

『有限』個の「自然数」から『1つの自然数』を得る関数です。

全域を含んだ部分関数になります。

(部分写像の考え方を参考に)




形式的には↓みたいな感じ(出てくる変数は全部「自然数」)



f(n_1,n_2,...,n_p)=n_c



やってることはみなさんがいつもやってることです。

5+3=8,\,\,\,2*3=6 」とか、こういうのなので。






『実数じゃない』のは、「機械で扱えないから」です。

自然数を無限個持ってきても、実数を表現しきれませんので。



といっても、これは現状「機械の作られ方」の問題です。

理論上であれば実数を使った計算は行えるわけですから。



というのも、最小の部品が「集積回路( 0,1 のどっちか)」で、

それを『有限個』使って機械はできてます。



そう「有限個」しかないんですね。

しかし最低条件として、実数を表すには「無限個」必要です。

0~1 の範囲でさえ「無限桁のもの」は表せません。






ともあれ、「再帰」の由来はこれになります。

『有限性』の象徴と考えれば、まあ妥当な由来かと。

字面からは分かり難いですけど。




ややこしいですが「帰納的関数」と「再帰関数」は同じものです。

「帰納的」と「再帰的」の英訳は( \mathrm{Recursive} )ですし。




詳細は長くなるので別記事で。

原子再帰関数」辺りからやっていきます。






ラムダ計算 Lambda Calculus


|| ラムダ(意味不明)計算(これは分かる)

要は「計算のやり方」ですね。

「書き方」とか「表し方」と言った方が良いかも。




「計算可能」な「関数」を定義するときに使われます。

これは長くなるので詳細は「ラムダ計算」の別記事で







チューリングマシン Turing Machine


|| ゲームとかで聞くやつ

いわゆる「計算機(コンピュータ)」のことです。(定義の一つ)

『どういう計算ができるか』が重要になります。




これは「計算機」を「数学」的に扱うためのものです。

「仮想機械」とか言われたりもしますね。

数学的に扱いたいんで「単純化」「抽象化」されてます。




「チューリングマシン」は、あらゆる「計算機」の中で、

現在、もっとも「現実的」であり、

かつ「いろいろ計算可能」という意味で「強力」な仮想機械です。



なので、仮想機械といったら大体これが使われます。

他のは「計算できる範囲を増やす」過程で、

「現実的でない」ものになっちゃったりしてます。




これは主要な「計算モデル」(計算するための基準)です。

詳細は長くなるので「チューリングマシン」で。

(再帰理論の核の一つ)






神託機械 Oracle Machine


|| そう、困ったときのなんとやら

これは「チューリングマシン」が元になってます。

そこに、一部の問題を「神託」に任せる感じで作られました。




「神託」ですから、要は神頼みですよ。

「決定不能な問題」になんらかの値を割り当てる感じです。

「チューリングマシンの停止問題」なんかでこれを使うわけです。




詳細は「停止問題」などの別記事で。







実効性 Effective


|| 聞くようで意味はよく分からない単語

辞書的な意味だと「実際」に「効果」がある、みたいな感じ。



より厳密な意味(数学的な意味)だと↓

『「証明(論理式の並び)」が「妥当」かどうか判定できる』性質

(そういう検証できるアルゴリズムが存在する、みたいな意味)




あくまで「答えが出る」ことしか保証しないので、

「計算複雑性理論」で語られる「効率性 Efficient」には関与しません。






決定可能性 Decidable


|| 読んだまま、決められるのかどうか

「決定」するのかどうか、みたいな(そのまま)



厳密な感じだと「実効性」をベースにしたものになります。

「実効性」を理解していないとこっちの意味を理解できません。




これを要約すると、

「帰属関係」が確認できるか、みたいな意味になります。



具体的には↓です。



『その「論理式」がその『理論の中にある』と、

「実効的」に「確認する方法」がある』なら、

それを『決定可能』と言います。




「実効性」は「論理式の正しさ」を確認するのに対して、

「決定可能性」は「論理式がある場所」を確認する感じです。



「実効性」は『正しいかどうか』を確かめて、

「決定可能性」は『正しいかどうか決められるか』を確かめます。






数学的な関連


最も有名な例は「命題論理」がそうです。

これはきちんと「確認ができる」ようになってます。



具体的には、「命題論理」は、その「論理式」が、

「命題論理のものであるか」を確認する方法があります。




その方法は「真理値の確認」です。

これによりその「論理式」が「定理」かどうか確認できるので、

「定理」なら「命題論理」に含まれます。



これで「実効的」に確認ができるわけですね。

「真理値が確認できる」なら、それは「命題論理の論理式」です。

「命題論理の論理式」なら、真偽を「決定可能」になります。






ただし『一階述語論理』では、

論理記号」になにを採用するかで『決定可能』かが決まります。

いわゆる「一般的(なんでも)」な場合は「決定可能」じゃないです。



「決定可能」である条件は、調べた結果↓だからだそうです。



採用する『非論理記号』が、

「等号」以外には、「アリティ 1 」の記号だけ。

この場合だけ『一階述語論理』は「決定可能」です。






決定問題 Decision Problem


|| 名前のわりに大事なもの

要は「はい」か「いいえ」を返す『問題』のこと。

ものすごく当たり前な感じの問題です。




大事な理由はなんとなくわかると思いますが、

要は2択にできるからです。(「真偽」で判定可能)




ブール代数」もしくは『集合論』的に表すと↓みたいになります。

まずものすごく当たり前のことを確認していきましょうか。




なんらかの「文字列」を「 \{0,1\}^n 」と表します。

例えば「あ」を「 0010001000100100 」とかに。

(↑は n bit のデータです)



いわゆるバイナリ( 0,1 のデータ)に変換しただけです。

それに「直積」という操作を行って、並べたことを表した感じ。

要は全部→みたいになります「 001001110101010…




これを「直積」で「集合」にしたものが、

(\{0\},\{0\},\{1\},\{0\},…) 」です。



そしてこれを具体的な値を決めてない状態にしたものが、

\{0,1\},\{0,1\},\{0,1\},\{0,1\},\{0,1\},\{0,1\},... 」になります。

要はPCのデータですよ。



こうすると、上で定義された「文字列」の部分集合から、

『決定問題』が↓の『写像』として定義できます。



f:\{0,1\}^n→\{0,1\}




これを見て分かる通り、

人は『集合論』を元にして、2択問題を解いてるわけですね。



こういう感じに「決定問題」になるように問題を設定することで、

あらゆる「問題」を数学的に扱えるわけです。







計算複雑性 Computational Complexity


|| 複雑な計算ってなんで複雑なんでしょ

いわゆる「最適化」だったり「効率化」だったりを扱う分野です。

「計算量」やら「計算の複雑さ」なんかが主な指標になります。




なので問題となるのは主に、

「計算」に必要な「時間」や「記憶領域」の量です。

まさにコンピューターの分野に当たります。




この辺りのことを調べるのは、数学の中でも当然重要です。

なにせ「時間」は「無限」にあるわけではありませんし、

当然「記憶領域(メモリ)」も「無限」ではないわけで。




もし仮に「ほぼ無限」に資源が必要になるなら、

例えば「計算可能」だけど、1000兆年くらい掛かるよ、

みたいな感じで時間が掛かり過ぎるなら(将棋の最善手とか)



これは「事実上、答えが出ない」ということになります。

これでは意味がありません。答え、欲しいんで。




じゃあ「ほどほどの資源」で「答えを出す」には?

もっと言えば「最小の資源」で「答えを出す」には?

はて、いったいどういう条件が必要なんでしょう?




とまあ、こんな感じのことを調べるのがこの分野になります。

代表的な奴だと「 P=NP 問題」とか




ともかく、詳しくやると長くなるのでこの辺りに。

詳細は別の記事『計算複雑性理論』で。






チューリング次数 Turing Degree


|| 複雑さを表す数値が欲しい

いわば「複雑さ」を示す「値」のことです。



条件もいくつかありますが、

基本は「自然数」ベースと思っておけば良いです。

要約すれば「自然数」の値かどうか、みたいな感じなので。




厳密な意味ですが、

決定可能性」を理解しとかないと、

さすがにこれちょっと意味わかんないです。




これも長くなるんで別記事で。







再帰定理 Recursion Theorem


|| 自己完結してる感じ

「計算可能関数」は自分で自分を記述できるよ。

というような主張のことです。



「クリーネの再帰定理」とも言われます。




これも簡単に説明すると↑みたいになりますし、

更に言えば説明すると長くなるんで別の記事で扱います。






以上が「再帰定理」の感じです。

何回か言った通り、人間に扱えるかが主軸になります。

なので、わりと皆さんこの考え方使ってるんですよね。