授業科目名：

対象学年：

開講学期：

開講形態：

　前半は、万能な計算機のモデルであるチューリング機械を取 り上げ、計算機で計算することをつきつめるとどうなるかについて 考察する。特に、他のすべての問題の決定不能性の基礎となる、チ ューリング機械の停止問題の決定不能性については詳しく述べる。
　後半は、これらの機械の領域計算量や時間計算量について考察し、 計算量の階層がこれらのモデルや機械とどのようにかかわっている かについての最近の理論を述べる。最後に、多項式時間と多項式領 域、NP完全性などについて述べる。

第1週　復習、チューリング機械
第2--3週　チューリング機械の構成技法
第4--5週　チューリング機械の諸変形
第6--7週　停止問題の決定不能性
第8--9週　Postの対応問題
第10週　Chomsky階層
第11--12週　時間計算量と領域計算量
第13--14週　多項式時間と多項式領域
第15週　NP完全問題

筆記試験

（著者）Ｊ．ホップクロフト、Ｊ．ウルマン （書名）オートマトン 言語理論 計算論 Ｉ （出版社）サイエンス社 （価格）2,900円（1984)

（著者）Ｊ．ホップクロフト、Ｊ．ウルマン （書名）オートマトン 言語理論 計算論 ＩＩ （出版社）サイエンス社 （価格）2,900円（1986)

この講義は２年次に開講される「オートマトンと言語理論」に続く ものとして行われる。その知識を前提とした進め方を行うので、必 ずこの講義を履修しておくこと。

計算機で計算をするということに関する理論的基礎を、計算 機の究極のモデルであるチューリング機械を用いて考察する。

この講義では、計算機を理論的に理解させることを目的とする。 したがって、理論を好まない者には受講を勧めない。 また、この講義で最終単位を取ることのないように。