計算理論#

• 第1章 可計算性的起源
  • 1.1-1931哥德爾不完備定理與判定問題
  • 1.2-1936圖靈機與可計算函數
  • 1.3-λ演算、遞迴函數與Church-Turing論題
• 第2章 自動機與正則語言
  • 2.1-1943有限狀態機從神經模型到自動機
  • 2.2-1956Kleene定理正則表達式與自動機的等價性
  • 2.3-泵引理與Myhill-Nerode定理
• 第3章 文法與上下文無關語言
  • 3.1-1956Chomsky階層語言文法與機器的對應
  • 3.2-下推自動機與ALGOL 60的語法革命
  • 3.3-CYK、Earley與LR分析的編譯器理論
• 第4章 不可判定性
  • 4.1-停機問題與對角線法
  • 4.2-1946Post對應問題與歸約技術
  • 4.3-1951Rice定理與不可判定問題全景
• 第5章 複雜性理論
  • 5.1-1965Hartmanis-Stearns時間階層定理
  • 5.2-1971Cook-Levin定理與NP完全
  • 5.3-隨機性互動與P vs NP的現代進展