以下文字资料是由小编为大家搜集整理后发布的内容，让我们赶快一起来看一下吧！
数学体系的的圣杯是否存在？——图灵机的源头
上一篇提到的无限这个原本大家都敬而远之的怪物，还是被康托尔用 ... 论驯服了， ... 论俨然成为建构数学体系的利器。然而过没多久，英国哲学家与数学家罗素 (Bertrand Russell) 却在 1901 年提出一个后来以他为名的「罗素悖论」（注一），指出 ... 论的矛盾之处，史称「第三次数学危机」。
尽管几位数学家着手修补，参考欧氏几何有五大公设，也为 ... 论制定一些公设，将「朴素 ... 论」改造为没有矛盾的「公设化 ... 论」，安然度过危机。但是数学体系接二连三出现裂缝，表示其中必有缺陷。大数学家希尔伯特 (David Hilbert) 因此呼吁重新审视所谓不证自明的公设或定理，从根基开始，重新打造完美无瑕的数学体系。
大数学家希尔伯特 (David Hilbert) 摄于 1912 年。图：Wikipedia1928 年，希尔伯特在国际数学家大会上抛出三大提问：
一、数学是否完备？所谓完备是指每则陈述（例如毕氏定理）都可以被证明为真或为假。
二、数学是否一致？也就是同一则陈述不会有既被证明为真、又被证明为假的矛盾情况。
三、数学是否可以判定？意思是任何陈述都有一套明确的程序可以用来判定其真假。（例如希尔伯特列举的 23 个悬而未决的数学问题，是否终究会找出证明的 ... ？）
基于数学以往几次克服危机的历史经验，希尔伯特相信这三个提问的答案都是肯定的；1930 年他发表退休演说时，就以「我们必须知道，我们将会知道！」做为结语。这并不是希尔伯特一厢情愿，事实上学界也都普遍相信完备且一致的数学体系指日可待。
哥德尔不完备定理敲碎美梦
不料第二年，大家的美梦就被一篇论文狠狠敲碎。才25岁的奥地利数学家哥德尔 (Kurt G?del) 提出「哥德尔不完备定理」，证明任何一个基于算术公设的系统如果有一致性，就不是完备的，也就是其中一定有无法证明真伪的陈述（注二）。而且「哥德尔第二不完备定理」还指出：这个系统的一致性根本无法在系统内部获得证明。
哥德尔 (Kurt G?del) 摄于 1925 年。图：Wikipedia哥德尔正式宣判完备且一致的数学体系并不存在，追求圣杯只是徒劳，大家可以散矣。整个学界感到震惊与失落，正如冯纽曼的喟叹：「一切都结束了！」。
如今希尔伯特的前两个问题显然答案都是否定的，而既然存在无法证明真伪的陈述，那么第三个问题当然也就没意义了。但能否退而求其次，把第三个问题改为：可否透过一套明确的程序判定某个陈述能不能被证明真假？也就是说，我们至少可以把这种无法证明真假的异类挑出来吧？
正是这个判定问题，让图灵跨入计算机的领域。
延续挚爱未竟之业——图灵奋发向前的动力
图灵于 1912 年在伦敦出生，到了中学就长得高大壮硕，还是长跑健将。不过他却不是阳光男孩，相反地，他个性内向，在学校没有多少朋友，其中最知心的是大他一个年级的莫康 (Christopher Mor)。莫康因为感染肺结核，身体嬴弱削瘦，但他课业名列前茅，与图灵一样对数学、科学有极高的兴趣，两人常一起讨论而成为莫逆之交。
图灵摄于 16 岁。图：Wikipedia图灵对莫康爱慕不已，也因此才察觉自己的同性恋倾向。无奈莫康在毕业前一年不敌病魔而过世，用情至深的图灵深受打击，却也因此更加专注于学业。他在写给莫康母亲的信上说：
「……我知道自己必须在学业上投注相同的心力，仿佛他仍然在世，因为他会希望我这么做。」
图灵如此努力的背后还有个重要动力。莫康原本已经获得剑桥大学的奖学金，图灵想替他实现未能完成的人生，以进入剑桥大学为目标，而最后图灵也如愿于 1931 年入学就读。
1935年春季，图灵在数学教授纽曼 (Max Newman) 的课堂上，听到教授介绍希尔伯特的三大问题。纽曼提及修正后的「判定性问题」时，不知有心或无意，用的词是「机械式程序」(mechanical process)，而不是「明确的程序」。
机械式程序听起来就是多了一层含意，暗示著一种不需人为介入的自动程序。而这层含意在图灵心中埋下了种子，然后在初夏某一天的下午，图灵慢跑完，躺在草地上休息时，想到了如何透过自动机器解决判定性问题。
图灵机构造与运作原理
图灵无意打造一台真正的机器，因为他要处理的是抽象的原则性问题，重点在于思辨过程，而不是加减乘除。因此图灵只须设想这台自动机器如何运作，无需考虑它如何制造。事实上这台后来以他为名的「图灵机」极为简化，硬体组成只有一个可以左右移动的读写头，以及一条无限长的纸带。与其说它是计算机，反倒比较像是台打字机。
这条纸带上面划分成一个一个方格，每个方格只能打印一个符号。读写头能扫描辨识符号、打印符号，或抹拭符号；它还能左右移动，但每次最多只能移动一格。读写头的动作取决于它正下方那个方格内的符号，以及机器目前的状态。这两个参数也会决定读写头每次做完动作后，机器状态是否要改变。
这些影响读写头与机器状态的规则可以整理成一张「行为表」，例如下面这张：
按照这张行为表，像下面图中的纸条，原本3 个 “1” 和 2 个 “1” 彼此隔开，经过图灵机后，就会变成 5 个 “1” 连在一起。我们可以当作这是 3+2=5 的计算，那么配备这张行为表的图灵机就是一台简易加法器，可以任意加总两个数目。
图灵机构造再简单不过，但只要在行为表中制定适当的规则，再复杂的计算，它都可以胜任。图灵把可以透过有限的规则，让图灵机进行计算并以小数的形式印出来的数，定义为「可计算数」。
可计算数不一定是有限小数，像 1/3=0.3333……也算，反正纸带无限长，或者你也可以决定小数点后几位就停下来。因此像 √2、π 这种无理数也都是可计算数，因为它们可以用具有规律的无限级数表示（例如莱布尼兹所发现的 π/4=1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + ……），就能透过有限的规则，让图灵机计算。
描述数与通用图灵机
不过图灵机只能从纸带上读取资料，所以行为表得用一行符号来表达，才能印在纸带上让图灵机扫描。例如上面那张行为表可能就会变成一行指令：
10RNN；11RN2；20R13；21RNN；30LN4；31RNN；40NNN；41N0N
接着我们把指令中的英文字母与符号用数字代替，例如 A ~ Z 改为 11 ~ 33，分号”；”=99，数字也跟着改用两位数 00 ~ 09表示。如此一来，指令就会化为一串数字，图灵称之为「描述数」，意指这行纯数字的数列就能描述图灵机的行为。
正常的描述数可以让图灵机经过有限步骤后停下来，产生可计算数。但某些描述数却可能让图灵机中途动弹不得，或是不断来回绕圈圈，无法产生有意义的答案。例如「读到 1 就往右；读到 0 则往左」这个指令，就会让图灵机遇到 “1”、”0”相邻时左右来回，永不停止（这其实就相当于「说谎者悖论」）。
如果一台图灵机只有一个描述数，我们当然可以轻易地发现某台图灵机停不下来，从而知道这个描述数有问题。不过实际上不需要建造那么多台图灵机。想像有台特别的「通用图灵机」（图灵称之为 ”Universal machine“），可以把其它图灵机的描述数都扫描进来，那么它便能模拟任何一台图灵机的运作。而且描述数除了代表运作规则，也可以当成数字做为编号，按大小顺序排列，方便图灵机搜寻。
停机问题
现在问题来了，我们怎么知道扫描进来的那么多描述数之中，是否掺杂着造成图灵机空转的描述数？有没有一套机械程序可以直接判定某个描述数能否让图灵机正常停机（而不用让图灵机实际执行，再看结果如何）？这就是所谓的「停机问题」。它的性质等同于希尔伯特的判定性问题：有没有一套明确的程序可以判定某个陈述能不能被证明真假？
我们先假设真的有这么一套判定停机与否的程序，那么它可以把所有描述数的执行结果列表如下：（H代表会停机，N代表不会停机）
还记得上一篇介绍过的康托尔对角线法吗？现在我们拿来如法炮制，可以编制一个新的描述数，输入 1 的结果是 ”N”，与 M1 相反；输入 2 的结果是 “N” 与 M2 相反；……以此类推。这么一来，这个描述数绝对不在原来的表里面，也就是出现判定程序不知其执行结果的描述数。
就算把这个新的描述数再纳入表中也没用，因为永远都可以再用康托尔对角线法，新增一个不在表上的描述数。因此，根本不可能有套程序可以判定任一个描述数会不会停机。停机问题无解，代表数学上的判定性问题也确定无望，希尔伯特的三大提问至此可以休矣。（注三）
计算机不只会计算，还能模拟人的思考方式
1936 年 5 月，图灵提交这篇影响深远的论文：《论可计算数及其在判定性问题上的应用》 (On Computable Numbers, with an Application to the Entscheidungsproblem)，不但在数学上占有重要地位，更展示许多计算机的创新设计。
他率先提出通用计算机的概念，将不同程式预先载入后再开始运行。而程式转化为描述数，使得程式和资料共用同一个载体，也是首创。同时描述数做为程式的独特编号，就相当于电脑程式在记忆体中的贮存位址；许多人相信这个概念启发了冯纽曼用于 ENIAC 的设计。
图灵还揭示了常人所未见的计算机角色。计算机的作用向来纯粹就只为数学计算，但图灵在这篇论文中却是从人类如何思考的角度，讨论如何让机器模仿计算者的心智状态。多年之后，图灵提出「图灵测试」，因而被称为「人工智慧之父」，但其实这颗种子早在此时就已埋下了。
图灵为了解决一个抽象的数学问题，而构思出通用图灵机这台纯属想像的机器。几年之后二次大战爆发，这次为了千百万人的生死存亡，图灵将动手打造真正的计算机。
__________________________________________________________________________
注一：罗素设想有个 ... R 是由所有不包含它本身的 ... 所构成的 ... 。这定义感觉很挠口，但其实相当合理。因为在实际生活的应用上，几乎所有 ... 本来就不包含本身，例如我们绝不会说昆虫这个 ... 的成员包括昆虫。问题来了，R 的成员应该包括它自己吗？
如果说不应该，那么 R 也是不包含自己的 ... ，所以 R 也应该属于 R。但是这样一来， R 就包含它自己，如此又不符合加入 R 的资格。结果不管 R 包不包含它自身，按照 R 的定义都会导致矛盾，这就是罗素悖论。
注二：算术公设指皮亚诺公设 (Peano axioms)，是义大利数学家皮亚诺提出关于自然数的五条公设。
注三：其实美国普林斯顿大学的数学家丘奇 (Alonzo Church) 比图灵早一个月，于 1936 年 4 月就提出论文，用正统的数学 ... 解决了判定性问题。图灵获悉后，也赶在论文发表前，在附录处加注说明丘奇的证明。不过丘奇用的形式系统复杂多了，不如图灵的 ... 简单易懂，所以一般讲到判定性问题的证明，都还是举通用图灵机为例。
