アンダースタンディング コンピュテーション 単純な機械から不可能なプログラムまで

詳細目次

目次

日本語版まえがき
はじめに

1章　Rubyひとめぐり
1.1　対話型 Rubyシェル
1.2　値
1.2.1　基本データ
1.2.2　データ構造
1.2.3　Proc
1.3　制御フロー
1.4　オブジェクトとメソッド
1.5　クラスとモジュール
1.6　その他の機能
1.6.1　ローカル変数と代入
1.6.2　文字列の式展開
1.6.3　オブジェクトのインスペクト
1.6.4　文字列のプリント
1.6.5　可変長引数のメソッド
1.6.6　ブロック
1.6.7　Enumerable
1.6.8　Struct
1.6.9　モンキーパッチング
1.6.10　定数の定義
1.6.11　定数の削除

第I部　プログラムと機械
2章　プログラムの意味
2.1　「意味」の意味
2.2　構文
2.3　操作的意味論
2.3.1　スモールステップ意味論
2.3.2　ビッグステップ意味論
2.4　表示的意味論
2.4.1　式
2.4.2　文
2.4.3　応用
2.5　実際の形式意味論
2.5.1　形式
2.5.2　意味の理解
2.5.3　その他のスタイル
2.6　パーサの実装

3章　最も単純なコンピュータ
3.1　決定性有限オートマトン
3.1.1　状態、規則、入力
3.1.2　出力
3.1.3　決定性
3.1.4　シミュレーション
3.2　非決定性有限オートマトン
3.2.1　非決定性
3.2.2　自由移動
3.3　正規表現
3.3.1　構文
3.3.2　意味論
3.3.3　パース
3.4　等価性

4章　能力を高める
4.1　決定性プッシュダウン・オートマトン
4.1.1　ストレージ
4.1.2　規則
4.1.3　決定性
4.1.4　シミュレーション
4.2　非決定性プッシュダウン・オートマトン
4.2.1　シミュレーション
4.2.2　非等価性
4.3　プッシュダウン・オートマトンによるパース
4.3.1　字句解析
4.3.2　構文解析
4.3.3　実用性
4.4　どれだけ能力があるか

5章　究極の機械
5.1　決定性チューリングマシン
5.1.1　ストレージ
5.1.2　規則
5.1.3　決定性
5.1.4　シミュレーション
5.2　非決定性チューリングマシン
5.3　最大の能力
5.3.1　内部ストレージ
5.3.2　サブルーチン
5.3.3　複数のテープ
5.3.4　多次元のテープ
5.4　汎用機械
5.4.1　エンコード
5.4.2　シミュレーション

第II部　計算と計算可能性
6章 無からのプログラミング
6.1　ラムダ計算をまねる
6.1.1　Procの利用
6.1.2　問題
6.1.3　数
6.1.4　ブール値
6.1.5　述語
6.1.6　ペア
6.1.7　数値演算
6.1.8　リスト
6.1.9　文字列
6.1.10　解答
6.1.11　高度なプログラミングテクニック
6.2　ラムダ計算の実装
6.2.1　構文
6.2.2　意味論
6.2.3　パース

7章　至るところにある万能性
7.1　ラムダ計算
7.2　部分再帰関数
7.3　SKIコンビネータ計算
7.4　Iota
7.5　タグシステム
7.6　循環タグシステム
7.7　コンウェイのライフゲーム
7.8　ルール 110
7.9　ウルフラムの 2,3チューリングマシン

8章　不可能なプログラム
8.1　厳然たる事実
8.1.1　万能システムはアルゴリズムを実行できる
8.1.2　プログラムはチューリングマシンの代わりになる
8.1.3　コードはデータである
8.1.4　万能システムは永久にループできる
8.1.5　プログラムは自己参照できる
8.2　決定可能性
8.3　停止性問題
8.3.1　停止性チェッカーの構築
8.3.2　決してうまくいかない
8.4　その他の決定不能な問題
8.5　残念なこと
8.6　なぜ起こるのか
8.7　計算不能性に対処する

9章　おもちゃの国のプログラミング
9.1　抽象解釈
9.1.1　ルート計画
9.1.2　抽象化：符号の掛け算
9.1.3　安全と近似：符号の足し算
9.2　静的意味論
9.2.1　実装
9.2.2　利点と制限
9.3　応用

あとがき
監訳者あとがき