可计算性与计算复杂性导引

第一章  程序设计语言和可计算函数
  1.1 预备知识
  1.2 程序设计语言
  1.3 可计算函数
  1.4 宏指令
  习题
第二章  原始递归函数
  2.1 原始递归函数
  2.2 原始递归谓词
  2.3 迭代运算、有界量词和极小化
  2.4 配对函数和Godel数
  2.5 原始递归运算
  2.6 Ackermann函数
  习题
第三章  通用程序
  3.1 程序的代码
  3.2 停机问题
  3.3 通用程序
  3.4 参数定理
  3.5 递归定理
  习题
第四章  字符串计算
  4.1 字符串的数字表示
  4.2 程序设计语言
  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 部分递归函数
  7.6 Church-Turing论题
  习题
第八章  不可判定的问题
  8.1 判定问题
  8.2 Turing机的停机问题
  8.3 字问题和Post对应问题
  8.4 有关文法的不可判定问题
  8.5 一阶逻辑中的判定问题
  习题
第九章  正则语言
第十章  上下文无关语言
第十一章  上下文有关语言
第十二章  计算复杂性
第十三章  NP完全性
第十四章  组合优化问题的近似计算
附录
参考文献