论可计算数-图灵与现代计算的诞生

前言 //  vii 第一章背景数学的确定性 //004布尔逻辑//008数学逻辑//010逻辑机器//011保卫数学基础//012希尔伯特的方法//014哥德尔结论//016图灵的结论//016 第二章一些不可判定的判定问题 埃米尔•波斯特  // 025波斯特的对应问题  // 026一个算法  // 030含有更多符号的对应问题  // 032希尔伯特的第 10 个问题 // 034停机问题  // 036剑桥的图灵  // 036 第三章有限自动机有限自动机 // 043我们的第一个机器 // 044字母表和语言 // 046有限自动机和回答问题 // 049问题的否定 // 051忽略图表中的陷阱 // 052一些基本事实 // 054正则表达式 // 057有限自动机的瓶颈 // 062同样数量的0 和1 // 063平衡括号 // 064磁带和配置 // 065联系对应问题 // 067 第四章图灵机 有限自动机  // 043我们的第一个机器  // 044字母表和语言  // 046有限自动机和回答问题  // 049问题的否定  // 051忽略图表中的陷阱  // 052一些基本事实  // 054正则表达式  // 057有限自动机的瓶颈  // 062同样数量的 0 和 1  // 063平衡括号  // 064磁带和配置  // 065联系对应问题  // 067图灵机的例子  // 079可计算函数和计算  // 088邱奇—图灵论题  // 090计算能力  // 092多项式时间  // 093非确定性图灵机  // 095不会停机的机器  // 097 第五章其他计算系统λ积分 // 106皮亚诺算术 // 108λ积分和函数 // 109算术 // 110逻辑 // 112标签系统 // 114一维元胞自动机 // 119  第六章编码和通用机器编码有限自动机的方法 // 129通用机器 // 133设计通用机器 // 136现代计算机是图灵机 // 138冯•诺依曼结构 // 140随机存取机器 // 142图灵机能够模拟ram // 145其他通用机器 // 147当我们把〈m〉输入m的时候会发生什么 // 149  第七章不可判定的问题 矛盾证明法  // 155罗素的理发师  // 158不接纳自己的编码的有限自动机  // 161不接纳自己的编码的图灵机  // 162“图灵机是否会在自己的编码上偏离”是不可判定的  // 164接纳、停机和空白磁带问题  // 166一个不可计算函数  // 168图灵的方法  // 170 第八章康托尔的 对角论证法 基数  // 177有理数的子集拥有相同的基数  // 179希尔伯特旅馆  // 182定义不完善的减法  // 184一般对角论证  // 184康托尔定理 // 186实数的基数 // 189对角论证法 // 193连续统假设 // 195计算的基数 // 195可计算数  // 197一个非可计算数  // 198存在可数数量的可计算数  // 199可计算数无法有效枚举  // 200 第九章图灵的遗产  图灵在普林斯顿大学  // 206克劳德•香农  // 208第二次世界大战  // 20920 世纪 40 年代的计算机发展 //213克兰德•楚泽  // 214莫奇利和艾克特  // 214冯•诺依曼  // 215图灵测试  // 218陨落  // 221道歉和赦免  // 223  拓展阅读 //  227注释 //  231