可計算性與計算復雜性導引

第一章  程序設(shè)計語言和可計算函數(shù)
  1.1 預備知識
  1.2 程序設(shè)計語言
  1.3 可計算函數(shù)
  1.4 宏指令
  習題
第二章  原始遞歸函數(shù)
  2.1 原始遞歸函數(shù)
  2.2 原始遞歸謂詞
  2.3 迭代運算、有界量詞和極小化
  2.4 配對函數(shù)和Godel數(shù)
  2.5 原始遞歸運算
  2.6 Ackermann函數(shù)
  習題
第三章  通用程序
  3.1 程序的代碼
  3.2 停機問題
  3.3 通用程序
  3.4 參數(shù)定理
  3.5 遞歸定理
  習題
第四章  字符串計算
  4.1 字符串的數(shù)字表示
  4.2 程序設(shè)計語言
  4.3 Post-Turing語言
  4.4 用模擬
  4.5 用模擬
  習題
第五章  遞歸可枚舉集
  5.1 遞歸集和遞歸可枚舉集
  5.2 遞歸語言和遞歸枚舉語言
  5.3 非遞歸集和非遞歸可枚舉集
  習題
第六章  Turing機
  6.1 Turing機的基本模型
  6.2 Turing機與可計算性
  6.3 Turing機接受的語言
  6.4 Turing機的各種形式
  6.5 非確定型Turing機
  習題
第七章  過程與文法
  7.1 半Thue過程
  7.2 用半Thue過程模擬Turing機
  7.3 文法
  7.4 再論遞歸可枚舉集
  7.5 部分遞歸函數(shù)
  7.6 Church-Turing論題
  習題
第八章  不可判定的問題
  8.1 判定問題
  8.2 Turing機的停機問題
  8.3 字問題和Post對應問題
  8.4 有關(guān)文法的不可判定問題
  8.5 一階邏輯中的判定問題
  習題
第九章  正則語言
第十章  上下文無關(guān)語言
第十一章  上下文有關(guān)語言
第十二章  計算復雜性
第十三章  NP完全性
第十四章  組合優(yōu)化問題的近似計算
附錄
參考文獻