信息、算法与编码

**部分 信息、算法与编码在数理逻辑中
§0．1 数理逻辑简介
**章 可计算性函数
§1．1 算法和能行过程的直观含义（非数学定义）
§1．2 计算机模型——无界存储机URM
§1．3 URM-可计算性函数
§1．4 可判定谓词及可判定问题
第二章 生成可计算性函数
§2．1 生成可计算性函数
§2．2 原始递归函数
第三章 丘奇论题
§3．1 图灵机
§3．2 丘奇论题定义及应用
第四章 哥德尔编码
§4．1 URM程序的编码
§4．2 可计算函数的编码
§4．3 s-m-n定理
§4．4 “好”的编码（一）
§4．5 范式定理
第五章 一些重要结果
§5．1 通用函数及通用计算机
§5．2 哥德尔不完全性定理（简单化）
§5．3 P与NP问题
§5．4 “好”的编码（二）
§5．5 加速定理（thespeed-uptheorem，Blum）
第六章 可判定问题、递归、规约及度
§6．1 可判定，不可判定
§6．2 部分可判定
§6．3 递归及递归可枚举集
§6．4 多一规约
§6．5 图灵（Turing）规约
§6．6 小结：复杂事物的编码

第二部分 信息、算法与编码在可计算分析中
第七章 可计算分析的背景、TTE的轮廓
§7．1 研究背景
§7．2 TTE体系的轮廓
第八章 康托（Cantor）空间上的可计算性
§8．1 T2-机器及可计算性
§8．2 可计算串函数是连续的
§8．3 连续串函数集的标准表示
第九章 “好”的命名系统
第十章 R上的可计算性

第三部分 算法信息
第十一章 实数函数的计算复杂性
……

第四部分 信息论

参考文献