本を探す

本のタイトル検索キーワードを入力してください。

スペースキーで開閉します。

書名・副題書名・副題

書名・副題のキーワードを入力してください。

ISBNコード、JANコード ISBNコード、JANコード

ISBNコード、JANコードを入力してください。

シリーズ名・レーベル名シリーズ名・レーベル名

シリーズ名・レーベル名を入力してください。

著者名著者名

著者名を入力してください。

出版社名出版社名

出版社名を入力してください。

発行(予定)年月

発行年数開始年

開始年を西暦で入力してください。

年開始月

開始月を入力してください。

月～終了年

終了年を西暦で入力してください。

年終了月

終了月を入力してください。

月

出版社を探す

計算理論の基礎　[原著第3版] 2.計算可能性の理論

著：Michael Sipser
監：田中圭介
監：藤岡淳

紙版

出版社サイト。異版（Different Edition）電子版。

内容紹介

　Michael Sipser教授による “Theory of Computation” の講義はMIT屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。
　定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。
　第3版では、「決定性文脈自由言語」に関する節が新たに加えられたほか（第2巻）、問題や解答が追加されるとともに、いくつかの話題に関して、第2版刊行後の研究の進展について説明を加えた。

第3章　Church–Turingの提唱
　3.1　Turing機械
　3.2　Turing機械の変型
　3.3　アルゴリズムの定義
　
第4章　判定可能性
　4.1　判定可能な言語
　4.2　判定不可能性

第5章　帰着可能性
　5.1　言語理論における判定不可能問題
　5.2　単純な判定不可能問題
　5.3　写像帰着可能性

第6章　計算可能性の理論における先進的な話題
　6.1　再帰定理
　6.2　数理論理における判定可能性
　6.3　Turing帰着可能性
　6.4　情報の定義