駆け足で読む『計算理論の基礎』第２巻：計算可能性の理論

• 第１巻より大幅に簡略して読む(勝手な都合)
• 3 Church-Turing の提唱
  • 3.1 Turing 機械
    • 無限のメモリ・無限長のテープ
    • それでも解けない問題もある
  • 3.2 Turing 機械の変型
  • 3.3 アルゴリズムの定義
• 4 判定可能性
  • 4.1 判定可能な言語
    • 言語クラス
      • 正規
      • 文脈自由
      • 判定可能
      • Turing 認識可能
  • 4.2 停止問題
• 5 帰着可能性
  • 5.1 言語理論における判定不可能問題
  • 5.2 単純な判定不可能問題
  • 5.3 写像帰着可能性
• 6 計算可能性の理論における先進的な話題
  • 6.1 再帰定理
  • 6.2 数理論理における判定可能性
  • 6.3 Turing 帰着可能性
  • 6.4 情報の定義