论可计算数

前 言 // VII

第一章 背景

数学的确定性 //004

布尔逻辑//008

数学逻辑//010

逻辑机器//011 更多>>

前 言 // 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

第二次世界大战 // 209

20 世纪 40 年代的计算机发展 // 213

克兰德•楚泽 // 214

莫奇利和艾克特 // 214

冯•诺依曼 // 215

图灵测试 // 218

陨落 // 221

道歉和赦免 // 223

拓展阅读 // 227

注 释 // 231