近代数学講座 10 計算論 (復刊)

廣瀬 健(著)

廣瀬 健(著)

定価 3,850 円(本体 3,500 円+税)

A5判/204ページ
刊行日:2004年03月15日
ISBN:978-4-254-11660-1 C3341

ネット書店で購入する amazon e-hon 紀伊國屋書店 honto Honya Club Rakutenブックス

書店の店頭在庫を確認する 紀伊國屋書店 旭屋倶楽部

内容紹介

帰納的関数と広い意味での「アルゴリズムの理論」を考え方から始め,できるだけやさしく解説した〔内容〕アルゴリズム/テューリング機械/帰納的関数/形式的体系と算術化/T-術語の性質/決定問題/帰納的可算集合/アルゴリズム評価/他。初版1975年1月25日刊。

編集部から

目次

第1章 アルゴリズム
 1. “アルゴリズム”とは何か
 2. チャーチの提唱――アルゴリズムの数学的定義をめぐって
 3. アルゴリズムの理論
 4. 準備と規約
第2章 テューリング機械
 5. テューリング機械の概念
 6. テューリング機械と計算可能な関数
 7. テューリング機械の構成
 8. 各種のテューリング磯械
 9. 万能テューリング機械
 10.テューリング機械について
第3章 帰納的関数
 11. 原始帰納的関数と原始帰納的述語
 12. k重帰納的関数
 13. 帰納的関数と帰納的述語
 14. “計算可能な実数”について
 15. 帰納的関数の計算可能性
第4章 形式的体系とその算術化
 16. 形式的体系
 17. 形式的体系の算術化
 18. テューリング機械の算術化
 19. 計算可能な関数と帰納的関数の同等性
第15章 T-述語の性質
 20. クリーニの標準形定理
 21. 枚挙可能定理
 22. 帰納的でない述語
 23. 述語あるいは関数の階層
第6章 決定間題
 24. 決定問題
 25. 決定問題の例
 26. 語の問題
 27. 準シュー・システムとシュー・システム
第7章 帰納的部分関数
 28. 自然数上の部分関数
 29. 帰納的部分関数の基本的性質
 30. Sm n-定理と帰納定理
 31. 部分関数の拡大と部分述語の完備化
第8章 帰納的可算集合
 32. 帰納的可算封集合,帰納的可算述語および帰納的集合
 33. 帰納的集合と帰納的可算集合
 34. 完備な述語
 35. 帰納的可算述語に開するいくつかの性質と階層についての注意
第9章 アルゴリズムの評価および複雑さによる分類
 36. アルゴリズムの評価
 37. 具体的な問題に対する“手間のかからないアルゴリズム”
の例と計算時間あるいはメモリの使用量による分類
 38. オートマトンと数理言語
第10章 帰納的関数および帰納的述語の相対化――可解でない決定問題の分類
 39. 相対化
 40. 決定問題の還元可能性と決定不可能次数
 41. “ポストの問題”とフリードバーグームチニクの定理
第11章 “計算”のモデルとしての流れ図
 42. 流れ図
 43. プログラム
 44. プログラムによって計算可能な関数
 45. 流れ図,あるいはプログラムの停止性および同等性など
 46. ループを含まないプログラム
 47. 流れ図の標準形
参考文献
索 引
人名索引
事項索引

執筆者紹介

関連情報

ジャンル一覧

ジャンル一覧

  • Facebook
  • Twitter
  • 「愛読者の声」 ご投稿はこちら 「愛読者の声」 ご投稿はこちら
  • EBSCO eBooks
  • eBook Library