【授業の目的】
機械的手計算の数理モデルであるチューリングマシン、およびその等価な定式化である部分帰納的関数における計算可能性の理論を学ぶ。
現在の計算機についての数理モデルであるチューリングマシン、およびその等価な定式化である部分帰納的関数といった概念を用いて、「機械的計算」とは何か、「機械的に計算できない」問題は存在するか？という、情報科学分野における本質的で重要な問いを解明する。
【授業の到達目標】
「機械的計算」の数学的モデル化であるチューリングマシンの概念を中心にして、「機械的に手計算が出来る（アルゴリズムが存在する）問題」を特徴づけるための方法論（いわゆる「計算可能性」の理論）について、深く学ぶ。
【授業概要（キーワード）】
チューリングマシン，計算可能性，非決定性チューリングマシン，帰納的加算言語，ゲーデル数化，対角線言語，帰納的言語，万能言語，決定不能性，還元，ライスの定理，ポストの対応問題
【科目の位置付け】
システム情報学コース専門教育科目（専門科目）
【授業計画】
・授業の方法
主として講義形式で行うが、一部に、演習形式を採り入れる。
・日程
第１回：コンピュータで解けない問題は存在するか？（「計算可能性」の理論とはなにか）
第２回：チューリングマシン入門その１（記法・時点表示・遷移図）
第３回：チューリングマシン入門その２（受理言語と停止性）
第４回：チューリングマシンのプログラム技法
第５回：様々なチューリングマシンの等価性
第６回：非決定性チューリングマシン
第７回：チューリングマシンとコンピュータ
第８回：帰納的加算言語とは
第９回：チューリングマシンのゲーデル数化
第１０回：対角線言語の非帰納的加算性
第１１回：帰納的言語とは
第１２回：万能言語の決定不能性
第１３回：チューリング機会の決定不能性その１（還元）
第１４回：チューリング機会の決定不能性その２（ライスの定理）
第１５回：ポストの対応問題
【学習の方法】
・受講のあり方
基本的に講義形式なので、理解出来ないところを残さないようにする。
授業中の質問についても、進行の著しい妨げにならない程度であれば、行って頂いて構わない。
・授業時間外学習へのアドバイス
授業中に提示する参考書などで予習するとよい。
分からないことをそのままにしない。
【成績の評価】
・基準
期末試験と授業中に実施する演習の得点を合算して評価得点を算出し，それをもとに評価を決定します．
・方法
期末試験 60％
授業中に実施する演習 40%
【テキスト・参考書】
授業の初日と、その後の進展に沿って数種類の本を紹介する。
参考書：J.ホップクロフト,R.モトワニ,J.ウルマン 著「オートマトン 言語理論 計算論II(第２版)」サイエンス社
参考書：マイケル・シプサ 著『計算理論の基礎』、渡辺 治 他訳、共立出版
参考書：松原・大島・藤田 他著「IT Text 離散数学」オーム社 など
【その他】
・オフィス・アワー
前期 木曜日 14時40分以降
後期 水曜日 16時20分以降
|