全学共通科目講義(1回生~4回生対象)
|
現代の数学と数理解析 |
―― 基礎概念とその諸科学への広がり |
| |
日時: | 2013年4月26日(金) 16:30-18:00 |
場所: | 数理解析研究所 420号室 |
講師: | 照井 一成 准教授 |
題目: | 計算よ止まれ! 停止問題と算術の無矛盾性 |
要約: |
与えられた自然数から別の自然数を作り出す操作をfとする。
いまどんな自然数nから出発しても、数列
n, f(n), ff(n), fff(n), ... がいつかは1に到達するとき、便宜上「fは停止する」ということにしよう。 たとえば有名なコラッツの未解決問題は、f(2n) = n、 f(2n+1) = 6n+4 としたときfは停止するか?と述べることができる (ただし本講義ではこの問題には立ち入らない)。 停止性に関わる問題はコンピュータサイエンスの成立と発展の原動力となってきた。 たとえばコンピュータサイエンスの一番の基本定理は次のように述べることができる: 任意のfが与えられたとき、それが停止するかどうかは決定不能である(チューリング) 。 また、停止性は数学基礎論の観点からも重要である。たとえばペアノ算術の 無矛盾性を示すことは、ある種の操作fについて停止性を示すことに帰着する。 このときfは実際に停止する(ペアノ算術の無矛盾性)のだが、 fの停止性はペアノ算術の中では証明できない(第二不完全性)。つまり 「fは停止する」という命題は真なのに証明できない(第一不完全性の具体例)。 本講義ではこのあたりの事情について概観することにより、コンピュータサイエンスと 数学基礎論への導入としたい。 |
"http://www.kurims.kyoto-u.ac.jp/ja/special-02.html" |