图灵的秘密 他的生平 思想及论文解读[The Annotated Turing]pdf

图灵的秘密 他的生平 思想及论文解读[The Annotated Turing] 内容简介

在数字计算机出现之前，阿兰·图灵就预想了它们的功能和通用性……也证明了哪些事是计算机永远做不了的。

由Windows编程大师Charles Petzold耗时多年编写的这本书剖析了现代计算机原理开山之作、阿兰·图灵流芳百世的论文 “On Computable Numbers， with an Application to the Entscheidungsproblem”。图灵在其中描述了一种假想的计算机器，探索了其功能和内在的局限性，由此建立了现代程序设计和可计算性的基础。《图灵的秘密：他的生平、思想及论文解读》也像是一本小说，行文间穿插讲述了图灵的成长经历和教育背景，以及他跌宕起伏的一生，包括破解德国恩尼格密码的传奇经历，他对人工智能的探索，他的性取向，以及最终因同性恋的罪名而在41岁时自杀的悲惨结局。全书完整揭示了阿兰·图灵非凡、传奇而悲剧的一生，是了解图灵的思想和生平的极好著作。

阿兰·图灵（1912—1954）是英国数学家、逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。为纪念他在计算机领域的卓越贡献，美国计算机协会于1966年设立图灵奖，此奖项被誉为计算机科学界的诺贝尔奖。

图灵的秘密 他的生平 思想及论文解读[The Annotated Turing] 目录

第一部分 　基 　 　础

第1章 　这个墓穴埋葬着丢番图

第2章 　无理数和超越数

第3章 　几个世纪以来的发展

第二部分 　可计算数

第4章 　图灵的学业

第5章 　运作的机器

第6章 　加与乘

第7章 　子程序

第8章 　万物皆数字

第9章 　通用机

第10章 　计算机与可计算性

第11章 　机器与人

第三部分 　判定性问题

第12章 　逻辑与可计算性

第13章 　可计算函数

第14章 　主要证明

第15章 　λ演算

第16章 　对连续统的设想

第四部分 　题外话

第17章 　万物皆是图灵机？

第18章 　长眠的丢番图

参考文献

图灵的秘密 他的生平 思想及论文解读[The Annotated Turing] 精彩文摘

一种可行的方法是，依次计算每一项的第一位，直到某一项的第一位数字为0，然后，再依次计算每一项的第二位，直到某一项的前两位数字均为0，依此类推。这显然是一个很复杂的过程，特别是你不想机器在计算得到结果后再擦除结果的任意位时。

执行正弦函数只是一个问题，输入从哪里来呢？

或许我们的直觉是让机器的使用者以某种方式“键入”机器需要计算的角。这显然是受现在的交互式计算机和屏幕计算器的启发，但是为了接受这种形式的输入，需要重新设计图灵机。这比目前我们所做的工作量更大。第二种观点是将函数的输入“硬编码”在机器内部。例如，我们可以设计一台专门计算37.85°的正弦值的机器。尽管这样会把机器限制为只能求解某一个角度的正弦值，但是我们还是希望设计出的这种机器易于修改，从而可以计算其他角度的正弦值。

第三种方法是把角度编码到纸带上。机器读取这个输入，计算正弦值，然后再把结果打印到纸带上。（我猜你喜欢这么做！我也是。）

第四种方法是让机器自己产生输入。例如，机器首先计算角度为0°的正弦值，然后计算角度为1°的正弦值，再计算角度为2°的正弦值，等等，并把每个结果都打印在纸带上，最后会得到一张包含很多角度正弦值的“表”。这种方法要求机器计算得到的每个结果都只包含有限个数位。

第五种方法需要两台不同的机器。第一台机器计算实数，第二台计算该数的正弦值。我说两台机器的时候，实际上是指可以实现两台机器逻辑的一台机器。我们已经遇到过以这种方式结合的机器。在第8节中（本书第166～167页），图灵把一台判定机器D和通用机u结合起来，构造成机器H来分析标准描述。这种做法的好处是，我们可以“插入”不同的第一台机器来计算不同角度的正弦值。

这些做法都是有问题的。一个大问题是正弦函数的输入和输出都是实数（至少理论上是这样的），而实数包含无限位。键入一个有无限位的数或将这样的数编码在纸带上都是不可能的。

事实上，即使你将角度限制在简单的、可以表示成有限的十进制数的范围内，正弦函数需要的也是弧度制的角度。180°对应π个弧度，因此看上去很简单的10°其实是π／18个弧度——个包含无限个十进制位数的超越数。