可計(jì)算性與計(jì)算復(fù)雜性導(dǎo)引

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