計算可能性理論

Computability

 

情報工学科  選択  2単位  2年秋学期

 

【授業の目的】「計算の理論」で学んだことをふまえて、「計算とは何か」「計算できるとはどういうことか」を学ぶ。具体的には、等価であることがわかっているいろいろな計算表現を用いて計算できるとは何かを学ぶ。

 

【テキスト】「計算論入門」渡辺治、米崎直樹著、日本評論社

 

【評価の方法】小テストと定期試験。

 

【授業計画】

1.        はじめに

2.        簡易プログラミング言語による計算の表現

3.        簡易プログラミング言語の計算可能性

4.        チューリングマシンによる計算の表現

5.        チューリングマシンによるプログラミング

6.        チューリングマシンによる計算量の問題

7.        チューリングマシンの計算可能性

8.        原始帰納的関数

9.        帰納的関数による計算の表現

10.    計算不可能な関数と決定不能な問題

11.    ラムダ計算入門

12.    ラムダ計算による計算の表現 (1) 有効範囲と引数の評価

13.    ラムダ計算による計算の表現 (2) 簡略化戦略

14.    ラムダ計算とコンビネータ

15.    ラムダ計算の計算可能性

 

【備  考】授業計画は、変更される可能性がある。