|| 計算できるかどうかとか、効率的かどうかとか
『人間に扱えるか』についてのあれこれを調べます。
スポンサーリンク
その「人間に扱えるか」の指標として、
これは「小さな自然数」と密接に関係してます。
目次
・計算可能性「答えが出せるかどうか」
チャーチ=チューリングのテーゼ「計算可能性の定義」
計算可能関数「計算可能性を定義するもの」
帰納的・再帰関数「計算可能性の定義に使われる関数」
・チューリングマシン「一番いろんなものを計算できる機械」
神託機械「マシンの停止問題を解消するための機械」
・主要な性質
実効性「証明の妥当性を確認する方法があるという性質」
決定可能性「論理式がその元の理論のものか確認できる性質」
決定問題「あらゆるものの是非を決めるために作られる」
・計算複雑性「主にどれくらいの時間で計算できるかとか」
チューリング次数「計算の複雑さを表す指標」
・再帰定理「全部自分でいけるよ、みたいな感じ」
なんじゃこれはと自分も思いましたが、これは非常に重要です。
なにせ、いわば「形式言語」（プログラミングなど）は、
これを基軸として作られています。
というのも、例えば「無限」に処理が続いてしまって、
「答えが出ない」ものに価値はありません。
なにか「明確な価値」あるものは、
すべて「有限」の処理で「答えが出る」ものに限られるわけです。
それも『人が生きている間に』っていう時間制限付きで。
この「有限性」についての考察が、
『再帰理論』の本質になります。
ですから「計算可能性」やら「計算複雑性」やら、
主にそんなのを扱うわけですね。
というわけで、さっそく見ていきましょう。
計算可能性理論 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
|| 自己完結してる感じ
「計算可能関数」は自分で自分を記述できるよ。
というような主張のことです。
「クリーネの再帰定理」とも言われます。
これも簡単に説明すると↑みたいになりますし、
更に言えば説明すると長くなるんで別の記事で扱います。
以上が「再帰定理」の感じです。
何回か言った通り、人間に扱えるかが主軸になります。
なので、わりと皆さんこの考え方使ってるんですよね。