情報数学セミナーチャーチの提唱の周辺亀山幸義 [email protected] http://www.is.tsukuba.ac.jp/~kam １学期補足資料「計算可能性の話」  N→N – 自然数を１つ引数に取り、自然数を１つ返す関数の全体（集合）  理想化されたプログラム言語 – たとえば、いくらでも大きな自然数を取り扱えるように拡張されたC言語  対角線論法 – N→N の要素（つまり関数）すべてが、この言語のプログラムとして記述できると仮定すると矛盾 – プログラムとしては記述できない関数が存在する当然起きる疑問この話は「理想化されたプログラム言語」として何をとるかに依存するのではないか？  つまり、｢計算可能関数」という(一般的な）概念には何の関係もないのではないか？  単に、「C言語で記述可能なプログラム（関数）の範囲がどうか」という話ではないか？  計算機科学の最も基本的な問い 計算とは何か？答えはもちろん１つではない計算機科学の永遠のテーマ計算モデル  「計算」はいろいろな意味をもち、様々な形で定義される – 現代的な（フォンノイマン型）コンピュータでの計算 – 数学的な関数による計算、λ計算体系による計算 – 定理証明手続き – 最近の話題 • 量子計算 • DNA計算、自然計算自然な問いさまざまな「計算」の定義の間の関係を知りたい  どの計算モデルが強力か？  より強力な計算モデルにするのはどうしたらよいか？  計算機科学の創始者たち  １９６０年代のチャーチ、クリーニら – 当時提案された様々な計算モデルは、外見上全く違うにもかかわらず全て同等な表現力をもっていることがわかった – これは偶然ではなく、非常に安定した概念がそこにあることを示すのだろう、と考えられた – もっとも、「原始帰納的関数」など、弱すぎる計算モデルを考えて恥をかいた研究者もいた – それぞれの計算モデルをどんどん強くしていってこれ以上は本質的に強くならない（広い範囲の関数を定義できない）というポイントに来たとき、それは実はどの計算モデルでも同等だった、ということチャーチの提唱 Church’s Thesis  計算可能関数とは、以下の同等な定義のいずれか１つで与えられるものであると定義しよう – 帰納的関数 – λ定義可能性 – Turing機械による計算可能性（現代のプログラム言語を理想化したものを全部カバー） – マルコフ過程による計算可能性  注意 – これは「定理」ではない – 「定義をしようという呼びかけ」に過ぎない λ定義可能性  λ計算(型なしλ計算） – λ式の構成は３つの規則 • 変数 x • 適用 MN • λ抽象 λx.M – 計算規則 (ベータ簡約）： (λx.M）N⇒M[x:=N]  たったこれだけで、N→Nのものすごくたくさんの関数を表現できてしまう(驚き！） λ定義可能性  ある種のλ式を、自然数０，１，2，と見なす – ０ = λxy. x – １ = λxy. yx – ２ = λxy. y(yx)  自然数上のいろいろな演算を定義する – 1を足す s = λa.λｘ.λy.y(axy) – 足し算＋ = λa.λb. ab s – 再帰呼び出しだって何だってλ式として書けてしまう！ Turing機械１本の無限に長いテープ(読み書き可能）  ヘッド(テープのどこか１か所を指す）  状態は有限個  非常に原始的なコンピュータ  実は、Turing機械をいくら拡張して現代のコンピュータに近づけても、記述できる関数の範囲は広がらない  – テープを複数本にしたり、両方向無限長にしたり、ヘッドを増やしたり、ランダムアクセスにしても変わらない – RAM： Random Access Machine – もちろん、理想化したC言語で記述できるプログラムの範囲もこれと同等帰納的関数 recursive function N×。。。×N → N (引数として自然数を０個以上何個か取る関数）  この集合の中で、以下の定義により、ある部分集合を定める。それが帰納的関数の集合  最初に「たね」になる関数たち  – いつでも「０」を返す関数 – １を足す関数 – ｎ個の引数をもらい、そのj番目を返す関数  関数を組み合わせる仕組み – 関数合成 – 原始帰納法 – 最小化討論  原理的な論点 – 「計算」とは何か？ – 計算モデルとしてもっと強力なものはないのか？ • 人間や神が介在する計算？  現実的な論点 – 計算モデルを考えることに何の意味があるか？ • 現実のコンピュータとはほど遠い数学的モデルをいじっているのでは？ • 現代のコンピュータは「自然数から自然数への関数」を計算するだけでなく、様々な情報処理を行っている。その能力を反映したモデルを作るべきではないか？