授業のテーマと目的： 数学が発展してきた過程では、自然科学、 社会科学などの種々の学問分野で提起される問題を解決するために、 既存の数学の枠組みにとらわれない、 新しい数理科学的な方法や理論が導入されてきた。 また、逆に、そのような新しい流れが、 数学の核心的な理論へと発展した例も数知れず存在する。 このような数学と数理解析の展開の諸相について、第一線の研究者が、 自身の研究を踏まえた入門的・解説的な講義を行う。 数学・数理解析の研究の面白さ・深さを、 感性豊かな学生諸君に味わってもらうことを意図して講義し、 原則として予備知識は仮定しない。
第１０回
日時：	２０２１年６月１１日（金） 　　　　　　１６：４５−１８：１５
場所：	オンライン https://panda.ecs.kyoto-u.ac.jp/portal/site/2021-888-N114-001
講師：	照井 一成 准教授
題目：	集合の計算論的複雑さと不完全性定理
要約：	自然数nが与えられたとき, nが偶数かどうかは簡単に判定できるし, 素数かどうかも多項式時間で判定できる. 一方でどんな文字列も自然数で 表せるので、次のような問題を考えることができる. 1. nは初等数論の真な命題を表すか? 2. nは初等数論の公理系から証明できる命題を表すか? これらの判定は, 偶数や素数の場合に比べてはるかに複雑である. さらにいえば, 一見類似しているものの1と2の間には計算論的に大きな差がある. つまり「真であること」と「証明できること」は大きく異なる. このことを突き詰めていくと自然にたどりつくのが, 数理論理学における ゲーデルの不完全性定理である. 本講義では, 不完全性定理のエッセンスについて 簡単に解説する. 参考文献： 田中一之(編著), 数学基礎論講義──不完全性定理とその発展, 日本評論社, 1997. 照井一成, コンピュータは数学者になれるのか？──数学基礎論から証明とプログラムの 理論へ, 青土社, 2015.
"http://www.kurims.kyoto-u.ac.jp/ja/special-02.html"