チューリングの考えるキカイ～人工知能の父に学ぶコンピュータ・サイエンスの基礎
チューリングの考えるキカイ ~人工知能の父に学ぶコンピュータ・サイエンスの基礎
技術評論社
著者：阿部彩芽、笠井琢美
はじめに
目次
本書の歩き方
Chapter 1 究極の人工知能とそれを実現する機械
1-1 究極の機械って作れるの？
1-2 究極の人工知能
1-3 人工知能誕生～チューリング機械～
1-4 現在のコンピュータと数学の歴史
1-5 ヒルベルトの第10問題とチューリング停止問題
1-6 アルゴリズムの限界と数学の発展
1-7 言語の分野とコンピュータ・サイエンス
1-8 理論の世界と現実の世界
Chapter 2 自己言及のパラドックスと対角線論法
2-1 矛盾のお話
2-2 「クレタ人は嘘つきだ」
2-3 バカ犬のパラドックス
2-4 帰納法(再帰法)
2-5 村の床屋のパラドックス
Chapter 3 数学帰納法と数
3-1 “数"を正確に定義してみる
3-2 数学的帰納法と自然数の公理
3-3 集合論から数を考える
3-4 集合と命題
3-5 数の定義が数学の土台
Chapter 4 計算モデル
4-1 アルゴリズムと機械
4-2 アルゴリズムと流れ図
4-3 計算機械とプログラム
4-4 計算機械と現在のコンピュータ
Chapter 5 思考をwhileプログラムで書き表してみよう
5-1 機械とプログラム
5-2 プログラムの能力と等価性
5-3 人の思考とプログラムの文法
5-4 whileプログラムの文法
5-5 一般的なプログラムとwhileプログラムの違い(等価性)
5-6 代入文
5-7 手続き
5-8 まとめ
Chapter 6 論理とプログラム
6-1 機械と関数の等価性
6-2 無口な機械
6-3 whileプログラムと部分関数
6-4 論理式とwhileプログラム
6-5 if文とwhileプログラム
6-6 whileプログラムの能力
Chapter 7 配列とデータ型
7-1 数の表現法
7-2 単身表現とd進表現
7-3 文字列の扱い
7-4 対と有限列
7-5 ゲーデル数
Chapter 8 プログラム内蔵方式と万能プログラム
8-1 万能チューリング機械
8-2 機械語
8-3 機械の仕組みを知る
8-4 万能プログラム
8-5 世界で一番簡単なコンパイラの話
8-6 仮想空間としてのコンピュータ
8-7 まとめ
Chapter 9 計算可能性
9-1 計算可能性の能力
9-2 計算可能性とチャーチ＝チューリングの定立
9-3 集合の計算可能性
9-4 自然数以外の場合の計算可能性(性別判定問題)
9-5 whileプログラムの認識問題
9-6 素数判定問題
9-7 「問題」とは自然数の集合
9-8 ラッセルにパラドックス
Chapter 10 計算できない問題
10-1 計算できない問題
10-2 自己診断
10-3 whileプログラムの自己停止問題
10-4 whileプログラムの停止問題
10-5 停止問題を集合として表す
10-6 打ち切り時間停止問題
10-7 不要な変数と不要な文
10-8 まとめ
Chapter 11 チューリング機械と計数機
11-1 自然数論と言語理論
11-2 オートマトン理論とチューリング機械
11-3 多テープ・チューリング機械
11-4 プッシュダウン・オートマトン(プッシュダウン・機械)
11-5 計算機モデルと現在のコンピュータ
Chapter 12 計算可能性をこえて
12-1 自然数と実数
12-2 実数と対角線論法
12-3 計算と受理
12-4 否定について
12-5 まとめ
Chapter 13 実数と計算可能性
13-1 個数と濃度
13-2 2進小数のお話
13-3 チューリングが実際に証明したこと
13-4 楽観主義者と悲観主義者
13-5 数学の論理構造
13-6 数学の論理の仕組み
13-7 全体のまとめ
INDEX 索引
あとがき