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

 class Stack < Struct.new(:contents)
   def push(character)
     Stack.new([character] + contents)
   end

   def pop
     Stack.new(contents.drop(1))
   end

   def top
     contents.first
   end

   def inspect
     "#<Stack (#{top})#{contents.drop(1).join}>"
   end
 end

 # usage on IRB
 >> stack = Stack.new(['a', 'b', 'c', 'd', 'e'])
 => #<Stack (a)bcde>
 >> stack.top
 => "a"
 >> stack.pop.pop.top
 => "c"
 >> stack.push('x').push('y').top
 => "y"
 >> stack.push('x').push('y').pop.top
 => "x"

 >> rulebook = DTMRulebook.new([
      # 状態1: aを探して右にスキャンする
      TMRule.new(1, 'X', 1, 'X', :right), # Xをスキップする
      TMRule.new(1, 'a', 2, 'X', :right), # aを消して、状態2に進む
      TMRule.new(1, '_', 6, '_', :left),  # 空白を見つけて、状態6（受理状態）に進む

      # 状態2: bを探して右にスキャンする
      TMRule.new(2, 'a', 2, 'a', :right), # aをスキップする
      TMRule.new(2, 'X', 2, 'X', :right), # Xをスキップする
      TMRule.new(2, 'b', 3, 'X', :right), # bを消して、状態3に進む

      # 状態3: cを探して右にスキャンする
      TMRule.new(3, 'b', 3, 'b', :right), # bをスキップする
      TMRule.new(3, 'X', 3, 'X', :right), # Xをスキップする
      TMRule.new(3, 'c', 4, 'X', :right), # cを消して、状態4に進む

      # 状態4: 文字列の末尾を探して右にスキャンする
      TMRule.new(4, 'c', 4, 'c', :right), # cをスキップする
      TMRule.new(4, '_', 5, '_', :left),  # 空白を見つけて、状態5に進む

      # 状態5: 文字列の先頭を探して左にスキャンする
      TMRule.new(5, 'a', 5, 'a', :left), # aをスキップする
      TMRule.new(5, 'b', 5, 'b', :left), # bをスキップする
      TMRule.new(5, 'c', 5, 'c', :left), # cをスキップする
      TMRule.new(5, 'X', 5, 'X', :left), # Xをスキップする
      TMRule.new(5, '_', 1, '_', :right) # 空白を見つけて、状態1に進む
    ])
 => #<struct DTMRulebook rules=[...]>
 >> tape = Tape.new([], 'a', ['a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'], '_')
 => #<Tape (a)aabbbccc>
 >> dtm = DTM.new(TMConfiguration.new(1, tape), [6], rulebook)
 => #<struct DTM ...>
 >> 10.times { dtm.step }; dtm.current_configuration
 => #<struct TMConfiguration state=5, tape=#<Tape XaaXbbXc(c)_>>
 >> 25.times { dtm.step }; dtm.current_configuration
 => #<struct TMConfiguration state=5, tape=#<Tape _XXa(X)XbXXc_>>
 >> dtm.run; dtm.current_configuration
 => #<struct TMConfiguration state=6, tape=#<Tape _XXXXXXXX(X)_>>

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

 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　応用

 あとがき
 監訳者あとがき
 索引