The Annotated Turing (豆瓣)

副标题: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine
作者: Charles Petzold
出版社: John Wiley & Sons
页数: 372
定价: $ 33.89
ISBN: 9780470229057

8.5

(14人评价)

64.3%

14.3%

21.4%

0.0%

想读在读读过

评价:

内容简介 · · · · · ·

　　(excerpts from my proposal for the book)
　　Anyone who has explored the history, technology, or theory of computers has likely encountered the concept of the Turing Machine. The Turing Machine is an imaginary — not even quite hypothetical — computer invented in 1936 by English mathematician Alan Turing (1912–1954) to help solve a question in mathematical logic. As a byproduct, Tur... (展开全部) 　　(excerpts from my proposal for the book)
　　Anyone who has explored the history, technology, or theory of computers has likely encountered the concept of the Turing Machine. The Turing Machine is an imaginary — not even quite hypothetical — computer invented in 1936 by English mathematician Alan Turing (1912–1954) to help solve a question in mathematical logic. As a byproduct, Turing also founded the field of computability theory — the study of the abilities and limitations of digital computers.
　　Although the concept of the Turing Machine is well known, Turing’s original 1936 paper is only rarely read. This neglect may have something to do with the paper’s title — “On Computable Numbers, with an Application to the Entscheidungsproblem” — and perhaps the paper’s extensive use of a scary German gothic font. That’s too bad, because the paper is not only a fascinating read but a milestone in the history of computing and 20th century intellectual thought in general.
　　This book presents Turing’s original 36-page paper (and a follow-up 3-page correction) with background chapters and extensive annotations. Mathematical papers like Turing’s are often terse and cryptic. I have elaborated on many of Turing’s statements, clarified his discussions, and provided numerous examples.
　　Interwoven into the narrative are the highlights of Turing’s own life: his years at Cambridge and Princeton, his secret work in cryptanalysis during World War II, his involvement in seminal computer projects, his speculations about artificial intelligence, his arrest and prosecution for the crime of “gross indecency,” and his early death by apparent suicide at the age of 41.
　　The book is divided into four parts: Parts I and II together are about 200 pages in length and cover the first 60% of Turing’s paper, encompassing the Turing Machine and computability topics. This part of the book is entirely self-contained and will be of primary interest to most readers.
　　Part III is a faster paced look at the remainder of Turing’s paper, which involves the implications for mathematical logic. Some readers might want to skip these chapters.
　　Part IV resumes the more "popular" presentation showing how the Turing Machine has become a vital tool in understanding the workings of human consciousness and the mechanisms of the universe.
　　Although I expect the primary readers of the book to be programmers, computer science majors, and other “techies,” I have tried my best to make the book accessible to the general reader. There is unavoidably much mathematics in the book, but I have tried to assume that the reader only has knowledge of high-school mathematics, and probably a foggy one at that.　　

豆瓣成员常用的标签(共34个) · · · · · ·

计算机科学(35) turing(25) 计算机(15) 图灵(13) AlanTuring(12) Computer.Theory(11) Computer(6) 历史(4)

喜欢读"The Annotated Turing"的人也喜欢 · · · · · ·

: 计算机程序的构造和解释

: UNIX编程艺术

: C Programming Language

: 代码大全（第2版）

: 算法导论

: 哥德尔、艾舍尔、巴赫

: 深入理解计算机系统（修订版）

读书笔记 · · · · · · (共16篇)
我来写笔记

按有用程度 按页码先后 最新笔记

第3章

透明 (达摩流浪者)

希尔伯特先后在哥尼斯堡（七桥之城）大学和哥廷根大学任教。在哥廷根大学时他教授实平面几何，把欧几里得第5公理去掉之后创造非欧几何系统。（光是看看他的同事们的名字就已经如雷贯耳啊～）新世纪到来之前希尔伯特提出了一堆尚待解决的问题，其中第10个待解的问题就是Entscheidung：按照某确定且有限的过程，判定任意丢番图方程是否存在有理数解。当时的学术氛围非常乐观，“total knowledge”的获得似乎只差时间和工作量，就... (更多)

希尔伯特先后在哥尼斯堡（七桥之城）大学和哥廷根大学任教。在哥廷根大学时他教授实平面几何，把欧几里得第5公理去掉之后创造非欧几何系统。（光是看看他的同事们的名字就已经如雷贯耳啊～）
新世纪到来之前希尔伯特提出了一堆尚待解决的问题，其中第10个待解的问题就是Entscheidung：按照某确定且有限的过程，判定任意丢番图方程是否存在有理数解。当时的学术氛围非常乐观，“total knowledge”的获得似乎只差时间和工作量，就像希尔伯特列举的23个待解问题。
几乎与此同时，弗雷格的“逻辑主义”——尝试用集合论重建数学的公理体系——引起了罗素的注意。（罗素的教父是约翰-斯图尔特-穆勒～）
一战期间希尔伯特提出了“纲领”：一个独立、一致、完整、可判定的公理体系。完整且可判定，正如Behmann所说，也就是可以用机器进行所有的计算和证明而不需任何人的思想参与。但哥德尔说：一个可以推导出所有正确的逻辑方程的公理体系，看起来仍然是一个未解决的问题。
哥德尔最终解决了这个问题（实际上是证明了这个问题的不可解决性），通过证明代数体系的不完备性：尽管一阶谓词演算中所有的断言都是可证的，但加入代数公理之后某些断言是不可证的——代数体系本身应该是一致的，但这种一致性是不可证的。
随后丘奇和图灵分别证明了代数体系的不可判定性：不可能发展出一个通用的算法过程用于判断一个断言是否可证。“不可能用一个程序来判定任意程序是否存在错误”（即：不可能证明软件的正确性）实际上是Entscheidungsproblem的一个推论。
（注：但某些特定而且常见类型的数理逻辑方程的可判定性是存在的，只是不存在一个“通用判定算法”。希尔伯特和阿克曼已经发展出了一些这样的非通用判定过程。对应到软件开发上：因为不可能证明软件正确性就宣称软件的bug是不可避免的，这是在逃避责任。） (收起)

2011-08-31 07:54:10 1人收藏回应

收藏
推荐
第11章

透明 (达摩流浪者)

图灵认为，人脑的“思考”过程实际上和图灵机是等价的：读入有穷的信息，进入有穷的N种可能的状态中的某一种，并输出（或记录）有穷的信息。实际上，在证明数学问题（以及，解答绝大多数科学和工程问题）时人们用的就是这样的过程，并且他们在纸上记录这样的过程——纸的二维特性是不必要的，这从绝大多数论文的出版形式上就能看出来。所以图灵认为，人脑就是一个插上纸带的图灵机。但哥德尔批评了这种观点。简言之，哥德尔认.. (更多)

图灵认为，人脑的“思考”过程实际上和图灵机是等价的：读入有穷的信息，进入有穷的N种可能的状态中的某一种，并输出（或记录）有穷的信息。实际上，在证明数学问题（以及，解答绝大多数科学和工程问题）时人们用的就是这样的过程，并且他们在纸上记录这样的过程——纸的二维特性是不必要的，这从绝大多数论文的出版形式上就能看出来。所以图灵认为，人脑就是一个插上纸带的图灵机。
但哥德尔批评了这种观点。简言之，哥德尔认为人脑是在使用过程中不断发展的，而不是“只有固定的N种m-config”。然而图灵并没有说人脑不能发展。图灵的说法是：人脑的各种可能的状态固然可能有很多但必定是有穷的，因为如果人脑有无穷多种可能的状态，那么其中的绝大部分必然是无限相似从而无法区分。
对“人脑可能的状态是否无限”这个问题的不同观点，正是“是否相信思维是一个机械过程”的两派人的根本差异所在。（个人而言我更认同哥德尔的观点，但不得不承认很多时候图灵是对的：很多人的整个思维方式完全就跟一台机器一样——只要你知道这台图灵机的m-config集合，你就能预测什么输入会得到什么输出。）
后半段的八卦是悲哀的。据说苹果电脑那个咬了一口的苹果logo是在向图灵致敬。我愿意相信这个故事。 (收起)

2011-09-11 22:08:52 回应

收藏
推荐
第2章

透明 (达摩流浪者)

超越数（transcendental numbers）就是不能成为任何代数方程之根的无理数。π是超越数，所以化圆为方是不可能的。尺规作图实际是在解代数方程。自然数、整数、有理数的无限集都拥有同样的势（即元素数量），因为这几个无限集都可以与自然数建立一一映射。可以与自然数一一映射的集合被称为可数的（enumerable）。但实数连续统的势是大于有理数的，因为超越数是不可数的。往大的方向，二维平面的所有点，乃至N维空间的所有.. (更多)

超越数（transcendental numbers）就是不能成为任何代数方程之根的无理数。π是超越数，所以化圆为方是不可能的。尺规作图实际是在解代数方程。
自然数、整数、有理数的无限集都拥有同样的势（即元素数量），因为这几个无限集都可以与自然数建立一一映射。可以与自然数一一映射的集合被称为可数的（enumerable）。但实数连续统的势是大于有理数的，因为超越数是不可数的。
往大的方向，二维平面的所有点，乃至N维空间的所有点与实数连续统拥有同样的势。往小的方向，0～1之间的所有实数也与实数连续统拥有同样的势。
超越数集合之不可数性的对角线证明（康托尔）太精妙了！
有理数集合的势是阿来夫0，因此有理数集合的子集数量是(2的阿来夫0次方)。用0和1的矩阵描述各个子集的元素分布，即可得到0～1之间的所有二进制数，也即0～1之间的所有实数。因此实数集合的势是(2的阿来夫0次方)，即阿来夫1。
康托尔定理：非空集合不可能与其幂集建立一一映射。非空集合的势必定小于其幂集。因此阿来夫0小于阿来夫1——远远小于。也就是说几乎所有的实数都是超越数。

什么叫深入浅出？什么叫大师范儿？这就是～
(收起)

2011-08-29 22:39:48 1回应

收藏
推荐

第18章

透明 (达摩流浪者)

基于图灵的成果，任意丢番图方程之可解性的判定方法（希尔伯特第十问题）看起来是希望渺茫了。茱莉亚-罗宾逊、马丁-戴维斯和尤里-马蒂亚塞维奇，他们完成了最终的证明。希尔伯特第十问题最终被证明不可解决。结束。 (更多)

基于图灵的成果，任意丢番图方程之可解性的判定方法（希尔伯特第十问题）看起来是希望渺茫了。
茱莉亚-罗宾逊、马丁-戴维斯和尤里-马蒂亚塞维奇，他们完成了最终的证明。希尔伯特第十问题最终被证明不可解决。
结束。 (收起)

2011-09-28 22:53:03 回应

收藏
推荐
第17章

透明 (达摩流浪者)

这章的标题提出了一个问题：一切都是图灵机吗？图灵机给可计算性划下了边界，一个重要的边界是停机问题：一个图灵机无法判断另一个图灵机的“命运”。但是图灵机毕竟只是图灵用来解决Entscheidungsproblem的一个思维构建。尽管随后的研究发现从可计算性的角度递归函数等价于lambda函数等价于图灵机，但一切计算方法的可计算性都等价于图灵机吗？这里所说的“一切”主要是在说人脑。但背后还有一个更深远也更具哲学意味的问... (更多)

这章的标题提出了一个问题：一切都是图灵机吗？
图灵机给可计算性划下了边界，一个重要的边界是停机问题：一个图灵机无法判断另一个图灵机的“命运”。但是图灵机毕竟只是图灵用来解决Entscheidungsproblem的一个思维构建。尽管随后的研究发现从可计算性的角度递归函数等价于lambda函数等价于图灵机，但一切计算方法的可计算性都等价于图灵机吗？
这里所说的“一切”主要是在说人脑。但背后还有一个更深远也更具哲学意味的问题：图灵机的极限究竟只是一类机器的建构，还是恰好反映了物理世界对认知的某种约束？图灵机恰好发现了人类不可获知之物吗？
从这个主题引出了很多重要的研究，例如魏纳的《控制论》、香农的《自动机研究》、冯诺依曼的《计算机与人脑》。目前为止的状态就像魏纳的另一本书的标题：《人有人的用处》。
（八卦：天才魏纳的故事太传奇了。）
再扩展一步，基本上就到了科幻的领域：整个宇宙是一台图灵机吗？如果宇宙的起源是确定的、宇宙中所有的规则是确定的，那么不就意味着宇宙中已经发生正在发生和将会发生的一切都是确定的吗？那么自由意志在哪里？拉普拉斯的魔鬼就是这样一个全知的存在。
拯救了自由意志的居然是Entscheidungsproblem：即使宇宙真的是一台图灵机，仍然没有办法预知未来，因为这是一个不可判定的问题。未来不存在，直到程序真的被执行。
未来仍然是等着人去创造的。这就是自由意志。 (收起)

2011-09-25 14:52:29 回应

收藏
推荐
第16章

透明 (达摩流浪者)

构造主义和直觉主义坚持，只有能够被构造出来的数学对象才是真实存在的。尽管形式主义者（例如希尔伯特）认为，即使不知道某些数学对象是如何构造的（甚至知道它们是不可构造的，例如绝大多数实数），但可以凭逻辑知道它们的存在。但直觉主义者认为，当我们谈论的是“无限”时，基本的逻辑原则例如排中律也未必成立，因此使用这些逻辑原则的推论也未必成立。例如布劳威尔的观点：如果一个表达式的值取决于“π中第一次出现0123... (更多)

构造主义和直觉主义坚持，只有能够被构造出来的数学对象才是真实存在的。尽管形式主义者（例如希尔伯特）认为，即使不知道某些数学对象是如何构造的（甚至知道它们是不可构造的，例如绝大多数实数），但可以凭逻辑知道它们的存在。但直觉主义者认为，当我们谈论的是“无限”时，基本的逻辑原则例如排中律也未必成立，因此使用这些逻辑原则的推论也未必成立。
例如布劳威尔的观点：如果一个表达式的值取决于“π中第一次出现0123456789这个序列的位置”是奇数还是偶数，那么它的值到底是什么？下面就是这个表达式：

k=(π中第一次出现0123456789这个序列的位置)
布劳威尔认为这个表达式的收敛极限值是不适用排中律的：它可能大于0，也可能小于0，还可能什么都不是（如果根本就不存在这样一个k值），而我们无法知道。有人反驳说，即使人类无法知道，上帝知道。布劳威尔说，但我没有与上帝沟通的渠道。
现在我们已经知道，0123456789这个序列在π中第一次出现的位置是偶数。这削弱了布劳威尔观点的说服力。但他的观点仍然有效：如果我们不是讲0123456789这个序列，而是“连续100万个7”呢？如果π的序列真的是随机的，那么有可能任意序列（哪怕是100万个7这样看起来几乎不可能的序列）都会在π中出现。但我们无法知道。π中存在的某些序列我们即使穷尽宇宙的资源也无法看到，但这不代表它们不存在。
布劳威尔倾向于用“选择顺序”来定义实数：可能是一个机械算法的选择，也可能是一个人的选择，但总之，实数是随时间被逐渐构造出来的，并且永远不会精确。在实数的构造上，布劳威尔和图灵有共通之处。
有趣的是，当把实数看作一个不断缩小但永远不会变成一个点的一维区间时，两个实数的相等性就无法判断了。图灵在他的论文勘误的最后一句提到了这件事。他并指出，一个实数本来就对应于无穷多个DN，并且无法判断两个DN是否等价。
直到今天，我们仍然在用“delta足够小”来判定两个实数的相等性。 (收起)

2011-09-25 12:07:24 回应

收藏
推荐