新書推薦：
《
DK威士忌大百科
》
售價：NT$
1340.0
《
小白学编织
》
售價：NT$
299.0
《
Android游戏开发从入门到精通 第2版 王玉芹
》
售價：NT$
495.0
《
西班牙内战：秩序崩溃与激荡的世界格局：1936-1939
》
售價：NT$
990.0
《
非对称创新：中国企业赶超战略 魏江 刘洋
》
售價：NT$
495.0
《
潜能觉醒
》
售價：NT$
395.0
《
初平：汉末群雄混战（190—195）
》
售價：NT$
245.0
《
建安：官渡大决战（196—200）
》
售價：NT$
245.0
|
| 編輯推薦： |
大众对图灵的认识往往停留在二战时期破解密码拯救生命这个层面。
对于图灵在学术上的成就却知之甚少。
本书深入分析图灵一生中*重要的论文《论可计算数及其在判定问题上的应用》，从科学的角度讲述图灵为什么重要，如果没有图灵，我们的世界将会怎样。
|
| 內容簡介： |
1936年，24岁的图灵发表了现代计算领域奠基性的论文《论可计算数及其在判定问题上的应用》。这篇论文堪称图灵一生中最重要的贡献。然而，大众对图灵的了解多停留在破解德国的著名密码系统Enigma，帮助盟军取得二战的胜利上。对于数学家图灵，人们往往知之甚少。
在本书中，作者深入分析了图灵的这篇论文，读者只需具备高中水平的数学知识，即可轻松读懂这篇划时代的论文，了解其对现代计算发展的杰出贡献。正如人工智能之父马文明斯基所说，图灵的论文有着超乎寻常的简洁性及数学之美。任何希望深入了解图灵及其工作的读者都不该错过这本书！
|
| 關於作者： |
|
克里斯伯恩哈特是美国费尔菲尔德大学数学系的一位教授，他从数学的角度入手，研究图灵的可计算数理论及现代计算的诞生，堪称图灵理论最深入的研究者。
|
| 目錄：
|
前
言 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
|
| 內容試閱：
|
1935 年，22 岁的艾伦图灵当选剑桥大学国王学院研 究员。那时的他刚刚完成了数学专业的本科课程。年轻的图 灵聪慧而又野心勃勃，读本科的时候就完成了中心极限定理
（Central Limit Theorem）的证明。这个定理可能是统计学中
最基础的定理，它说明了正态分布的普遍性并解释了其多样
性。虽然图灵完成了证明，但他很快发现自己并不是第一个
完成了这个任务的人。
早
在 10 年
之 前，亚 尔 瓦 尔德 马 林 德伯 格（Jarl Waldemar
Lindeberg）就发表了对这一定理的证明。虽然图灵
的证明并非首创，但却展现出了他过人的天分和非凡的潜力。
这足以让他被剑桥选中，获得研究员的职位：这份工作为他
赢得了奖金和三年食宿补助，他唯一要做的就是把精力投入
数学研究之中。现在，图灵必须要证明自己。要想做到这一
点，他得完成一些真正具有独创性的事情。还有什么比解决
一个世界顶级数学家提出的猜想，并证明他是错误的更令人
心动？这正是图灵想要做的，他将解决希尔伯特的判定问题。
在介绍图灵的工作之前，我们有必要了解希尔伯特提出
这一问题的原因。这还要追溯到 19 世纪下半叶至 20 世纪上
半叶数学领域的发展。我将用较多的笔墨介绍数学逻辑的兴
起、人们为追求数学公理化所做的努力以及算法扮演的角色
与作用。
数学通常被视作确定的代名词。如果数学真理不是
确定的，又有什么事情存在定数？纵观数学史，由于根基不
牢靠而导致整个结构崩溃的案例并不少见。人类第一次感觉
到数学的非确定性要追溯到公元前 5 世纪。据传，这种非确
定性的发现也导致希帕索斯（Hippasus）因为自己证明的定理而惨遭谋杀。如今希帕索斯的证明原稿早已不知所踪，不
过这段论证很可能也会归入最美丽的数学论证之列（我们将
在稍后看到完整的证明）。
古希腊数字系统由两部分组成完整数以及完整数的
比率，也就是我们现在常说的整数和有理数。希帕索斯首先
假定了一个底和高都是 1 的直角三角形，接下来他发现这个
三角形的斜边长度并不是有理数。现在看来，这完全不是问
题。因为除了有理数，我们还有像
、e 这样的无理数。我们明白希帕索斯论证中的斜边长度，实际上就是
这个无理数。
然而对于古希腊人来说，这无疑是个大问题他们的数字
系统中只存在有理数。对他们来说，希帕索斯论证中那条斜
边的长度无法由他们的数字表示，这也意味着还有更多的长
度不是数字！
希帕索斯是毕达哥拉斯学派的成员，这个神秘的学派
相信，数字能够表示所有事物的本质。由学派成员证明出
数字无法表示所有长度，这无异于晴天霹雳，令人心神不
安这一论断直接撼动了他们最基础的信念。据说当希帕
索斯将自己的证明展示给其他毕达哥拉斯派成员时，愤怒的
同伴用沉重的链条缠住他的身体，将他溺毙在湖中央。这个
故事的真实性难以考证，但无法测量的长度这一发现无疑引
发了数学史上第一场地震般的剧变。
数字和长度都是基本的实体，你能够画出底和高都是 1 的直角三角形，意味着它的斜边是真实存在的。这条斜边
拥有自己的长度，但对于古希腊人来说这却非常怪异，因为
他们无法给这个长度分配一个数字。这类论证使古希腊人认
为，长度才是更基础的实体。这样看来，数字确实让人有些
不安它缺少绝对的确定性。数字理论曾经被视作数学中
最基本、最确定的概念，在经历了这场风云突变后，几何学
很快取而代之。
从那以后直到现在，几何学都是数学教学重要的组成部
分。这主要归功于一个人和一本书欧几里得（Euclid）及
其所著的《几何原本》（Elements）。《几何原本》是欧几里德
编撰的收录了已知数学知识的百科全书，也是一本教科书。
自 2 000 多年前写就以来，这些文字一直备受追捧，不断吸
引着研究者的目光，在拜占庭和阿拉伯数学家中广为流传。 1482 年《几何原本》首次印刷出版，并在之后不断再版。
欧几里德从一系列公理、假设入手 2，逐渐延展、推理出
更多新的结论。每一个新定理都能够通过公理以及之前的推
论得出。这种公理化的方法给人们带来了一种数学具有确定性的
印象。如果我们知道自己使用的最初级的公理是正确的，就
会知道自己的逻辑推理是有效的，这样也就能够肯定通过推
理得出的结论。然而问题在于我们很容易做出一些无根据的
假设这些假设可能显而易见，甚至可能是正确的，但是却不能由最初的几条公理推导而出。当这些无根据的假设被
加入证明过程时，逻辑的有效性顷刻土崩瓦解，数学的必然
性也就此丧失。
在 19 世纪，有人意识到欧几里德做出的很多假设并非
基于自己的推导。因此，他的几何学著作需要重新修订。欧
几里德在证明过程中使用的一些无法从公理中推断出的陈述，
必须添加到他的公理列表之中。整个几何学的框架都需要重
新扩展、更新。
戴维希尔伯特提出了新的挑战。1899 年，他发表了学
术著作《几何基础》（Grundlagen der Geometrie），在书中列 出了一个更新、更长也更完整的公理列表。希尔伯特十分审 慎，希望确保没有根据的假设不会混入证明过程。为了实现 这一目标，他对公理的定义与欧几里德的定义有着非常大的 差异。
在欧几里德看来，像两点确定一条直线这样的公理
是不证自明的。点和线都有自身的含义。希尔伯特
的方法却不同，他意识到任何公理和定义系统都应该始于某
个起点，这些最初的陈述中势必会包含此前从未被定义过的
术语。
对希尔伯特来说，公理是能够用来证明其他观点的陈
述，但公理并不能被视作不证自明的真理。欧几里德的公理
两点确定一条直线中包含了点和线这两个没有被定义过的概念，因此这两个字不应该具有任何意义。公理会
定义这些未定义概念之间的关系。正如希尔伯特指出的，由
于这些术语并没有任何意义，因此理论上你可以选用任何一
个词来替换点和线。据说，他曾将公理中的点、
线、面等字眼，换作桌子、椅子、几杯啤酒。
伯特兰罗素曾经颇为风趣地对此做出总结：数学可
能就是这样一个学科，我们可能永远不知道自己在谈论什么，
或者无法判断自己说的是对还是错。3 我们当然希望点、
线这样的术语指代的是我们平时谈论的点和线，但是希尔
伯特认为任何涉及这些术语的证明，都只应通过公理推导而
出，不该源于我们对这些文字的直观理解。
希尔伯特在几何学方面的成功自然而然地带来了一个问
题：公理化方法是否能够应用到整个数学学科？是否能够找
出一组公理，构建出数学学科的全部？包括希尔伯特和罗素
在内的一些数学家认为这种公理化方法是可行的。但是，在
讨论罗素、希尔伯特和其他人的研究前，我们还需要了解一
下数学逻辑的发展。
|
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 聯絡我們
| 運費計算
| 幫助中心 |
加入書簽
HOME
新書上架
