改网站标题,自己做个网站,十款看免费行情的软件推荐,做外贸网站报价来源#xff1a; 数学职业家提出问题和解决问题的人2012#xff0c;图灵诞辰100周年#xff0c;献给这位伟大的开拓者。计算无处不在。走进一个机房#xff0c;在服务器排成的一道道墙之间#xff0c;听着风扇的鼓噪#xff0c;似乎能嗅出0和1在CPU和内存之间不间断的流动… 来源 数学职业家提出问题和解决问题的人2012图灵诞辰100周年献给这位伟大的开拓者。计算无处不在。走进一个机房在服务器排成的一道道墙之间听着风扇的鼓噪似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘到今天的计算机我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多甚至超越了它们的制造者。上个世纪末深蓝凭借前所未有的搜索和判断棋局的能力成为第一台战胜人类国际象棋世界冠军的计算机但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识而仅仅十余年后Watson却已经能凭借自己的算法先“理解”问题然后有的放矢地在海量的数据库中寻找关联的答案。长此以往工具将必在更多的方面超越它的制造者。而这一切都来源于越来越精巧的计算。计算似乎无所不能宛如新的上帝。但即使是这位“上帝”也逃不脱逻辑设定的界限。第一位发现这一点的便是图灵。一切从逻辑开始1900年的巴黎在世纪交替之际希尔伯特提出了他著名的23个问题。其中第二个问题——算术系统的相容性——正是他那雄心勃勃的“希尔伯特计划”的最后一步。这位数学界的巨人打算让整个数学体系矗立在一个坚实的地基上一劳永逸地解决所有关于对数学可靠性的种种疑问。一切都为了回答三个问题数学是完备的吗也就是说面对那些正确的数学陈述我们是否总能找出一个证明数学真理是否总能被证明数学是一致的吗也就是说数学是否前后一致不会得出某个数学陈述又对又不对的结论数学是否没有内部矛盾数学是可判定的吗也就是说能够找到一种方法仅仅通过机械化的计算就能判定某个数学陈述是对是错数学证明能否机械化希尔伯特明确提出这三个问题时已是28年后的1928年。在这28年间数学界在算术系统的相容性上没有多少进展。但希尔伯特没有等太久仅仅三年后哥德尔就得到了前两个问题的答案尽管这个答案不是希尔伯特所希望看到的。哥德尔的答案分两部分。第一任何包含了算术的数学系统都不可能同时拥有完备性和一致性也就是说如果一个数学系统包含了算术的话要么它是自相矛盾的要么存在一些命题它们是真的但我们却无法证明。这说明希尔伯特的前两个问题不可能同时为真。在这里“算术”有着精确的含义就是皮亚诺公理一组描述了自然数的公理。第二任何包含了算术的数学系统如果它是一致的那么我们不能在它的内部证明它本身的一致性。这说明我们没有希望解决第二个问题。这就是著名的哥德尔不完备性定理与其说它回答了希尔伯特的前两个问题不如说它阐述了为什么我们根本不可能解决这两个问题。哥德尔的证明非常精巧。他先将所有的数学陈述和证明符号化然后给每个符号串赋予一个数字这个过程被称为哥德尔配数法。借助数学归纳法我们可以建立针对所有自然数的陈述而这样的陈述本身对应着一个数字这个数字也符合陈述本身的要求。换言之这个陈述陈述了它本身的性质。哥德尔正是通过这样魔法般的自指完成了他的证明。这个证明之所以重要是因为它第一次提供了一套完整的数学工具和方法用于证明有关数学证明的不可能性。这本身就是数学的一次重大胜利说明数学的力量强大得可以用纯粹逻辑的方法证明它本身的力量是有界限的。在数学的领地上有些东西我们不知道也不可能知道。希尔伯特的前两个问题已经解决只剩下最后一个问题。然而如果一个数学系统不完备的话它显然不可能是可判定的因为机械化的计算本身也可以看成一种证明而在一个不完备的系统中真理不总能被证明。所以最后一个问题只对完备的数学系统有意义。所幸完备的数学系统是存在的。同样是哥德尔他证明了所谓“一阶谓词演算”的逻辑系统是完备的这被称为哥德尔完备性定理。一阶谓词演算是一个比较弱的逻辑系统在其中我们甚至不能有效唯一地描述算术。比如说自然数系统符合皮亚诺公理的一阶版本但它并不是唯一的还有无数种所谓“非标准模型”同样符合这套一阶系统。在一阶谓词演算中对于一套公理系统如果一个命题在所有的模型中都正确那么必定可以形式地证明这个命题这就是一阶谓词演算的完备性。在一阶谓词演算中真理总能被证明。在这个弱得多的逻辑系统中我们有了完备性真的命题必定可以被证明。那么它是不是可判定的我们能不能找到一种机械计算的方法判定其中数学陈述的对错数学称述的真假是否可判定的这个问题就是希尔伯特的可判定性问题。注希望更深入了解哥德尔不完备性定理的读者可以重温旧文《希尔伯特之梦以及梦的破灭》复杂的简单机器在纽曼教授的数理逻辑课上图灵第一次听到希尔伯特的可判定性问题以及哥德尔不完备性定理。那是1935年的春天他刚刚完成在剑桥国王学院的四年本科学习以优异的成绩被选为学院研究员正准备在数学界大显身手数理逻辑自然而然吸引了他的兴趣。图灵清楚地意识到解决可判定性问题的关键在于对“机械计算”的严格定义。考究希尔伯特的原意这个词大概意味着“依照一定的有限的步骤无需计算者的灵感就能完成的计算”这在没有电子计算机的当时算是相当有想象力又不失准确的定义。但图灵的想法更为单纯。什么是“机械计算”机械计算就是一台机器可以完成的计算这就是图灵的回答。用机器计算的想法并不新鲜。17世纪的莱布尼兹就曾设想过用机械计算来代替哲学家的思考而19世纪的Charles Babbage和Ada Lovelace就设计出了功能强大的“分析机”只可惜Babbage欠缺管理才能这台超越了时代的机器始终没有完全造好。但图灵需要的机器跟先驱设想的机器稍有不同。它必须足够简单简单得显然能造出实物也可以用一目了然的逻辑公式描述它的行为它又必须足够复杂有潜力完成任何机械能完成的计算。图灵要找的是一种能产生极端复杂行为的简单机器。这并非易事但图灵做到了据说这是他某次长跑过后在某块草坪上发呆的成果。他设计了一类机器然后定义“机械计算”为“这类机器可以完成的计算”。他设计的这类机器正是日后以他名字命名的图灵机。图灵机的示例。绿点指示处为当前状态每条规则的4项分别是当前位置读入的字符、当前位置写入的字符、纸带的移动方向、将要转移到的状态。图灵机的结构非常简单它由两部分组成一个读写头还有一条两边无限延长的纸带纸带被划分为小格每格中只能有0和1两种符号。读写头的限制则稍微宽松一些虽然每次只能对着纸带上的一个格子但它本身可以处于不同的状态虽然状态的数目是有限的。在所有状态中有一个特殊的“停机”状态读写头一旦处于停机状态就会停止运作但如果读写头一直没有到达停机状态的话它就会永远运转下去。整台图灵机的秘密在于读写头的状态转移表它指示着读写头的状态和当前读写头正对格子的符号如何变化。它只有一种非常简单的规则就是“如果在状态A的读写头对着符号x那么对当前格子写入符号y将纸带左移一格/右移一格/保持不动然后转移到状态B”。状态转移表就是由一系列这样的简单规则组成的。可以说状态转移表就相当于图灵机的源代码。实际上我们平时笔算乘法的思维过程跟一台图灵机的运转非常相似在每个时刻我们只将注意力集中在一个地方根据已经读到的信息移动笔尖在纸上写下符号而指示我们写什么怎么写的则是早已背好的九九乘法表以及简单的加法。如果将一个笔算乘法的人看成一台图灵机纸带就是用于记录的纸张读写头就是这个人和他手上的笔读写头的状态就是大脑的精神状态而状态转移表则是笔算乘法的规则包括九九表、列式的方法等等。这种模式似乎也适用于更复杂的机械计算任务。如此看来图灵机虽然看起来简单但它足以作为机械计算的定义。既然图灵机如此简单能不能将它“升级”赋予更多的硬件和自由度使它变得更强大呢比如说让它拥有多条纸带和对应的读写头而纸带上也不再限定两种符号而是三种四种甚至更多种符号的确放宽限制之后在某种程度上对于相同的任务我们能设计出更快的图灵机但从本质上来说“升级”后的图灵机能完成的任务原来的图灵机也能完成虽然也许会慢些。也就是说这种“升级”在可计算性上并没有意义放宽限制后的机器能计算的原来的机器也能完成。既然计算能力没有质的变化无论采取什么样的结构用多少种符号都无所谓。图灵机的一大优点就是它的简单。只要给出状态转移表任何一个人都可以模拟一台图灵机的计算。对工程师而言在现实中用机械建造一台图灵机也并非什么难事。对于程序员来说写一个模拟图灵机的简单程序更是不在话下。但如此简单的机器它又能做什么呢它真的能充当“机械计算”的定义吗以上文章观点仅代表文章作者仅供参考以抛砖引玉未来智能实验室的主要工作包括建立AI智能系统智商评测体系开展世界人工智能智商评测开展互联网城市云脑研究计划构建互联网城市云脑技术和企业图谱为提升企业行业与城市的智能水平服务。 如果您对实验室的研究感兴趣欢迎加入未来智能实验室线上平台。扫描以下二维码或点击本文左下角“阅读原文”
