十五、阿兰图灵
图灵1912年出生于伦敦，数学、科学能力惊人。他对计算机科学的建树始于1935年，当时他还是剑桥国王学院的硕士生。他开始解决德国数学家大卫·希尔伯特提出的问题——“可判定性问题(decisionproblem)”。是否存在一种算法，能够输入一个以形式逻辑(formallogic)书写的语句，输出准确的“是”与“否”的答案？如果这样的算法存在，可以回答比如“是否有一个数大于所有数”——答案为“否”。我们主要关注的是这样的一个算法是否存在。AlonzoChurch在1935年首先提出解决方法，他开发了一种叫“Lambda算子”得数学表达系统，证明了这样的算法不存在。虽然Lambda算子能够表示任何计算，但它使用的数学技巧是难度较高的。同时图灵想出了自己的办法来解决“可判定性问题”，他提出了一种假想的计算机叫做“图灵机”。图灵机提供了简单又强大的数学计算模型，虽然使用了完全不同的运算方法，但是图灵机的计算能力和Lambda算子一样强。同时因为图灵机更简单，所以在新兴的计算机领域更加受欢迎。图灵机是一台理论计算设备，它有着无限长的纸带，纸带可以存储符号，它还有一个读写头，可以读取和写入纸带上的符号。它还有一个状态变量，保存当前状态。它还有一组规则，描述机器做什么。根据当前状态+读写头看到的符号，规则决定机器做什么。决定的结果可能是在纸带写入一个符号、改变机器的状态、把读写头移动一格，甚至执行上述动作的组合等等。我们可以举个例子：让图灵机读取一个以零结尾的字符串11111…11110，并计算1的出现次数是不是偶数。如果是，在纸带上写一个1；如果不是，在纸带上写一个0。首先要定义“图灵机”的规则，如果当前状态是“偶数”、当前符号是1，我们就把状态更新成“奇数”、把读写头向右移动。如果当前状态是偶数，当前符号是0——意味着我们到达了字符串结尾，那么我们在纸带上写一个1，并且把状态改成停机——也就是图灵机已经完成运算。我们还需要两条规则来处理状态为奇数的情况：状态为奇数且纸带读取到以及状态为偶数且纸带读取到1。最后我们需要给状态定初始值——偶数（0为偶数）。我们定义好了起始状态和规则，就像写好了程序，现在就可以输入了。假设将110放在纸带上，有两个1，因此1出现了偶数次。图灵机开始运行，机器起始状态为偶数，看到的第1个数为1，因此状态变为奇数且将头右移1格。然后又看到了1，但机器状态是“奇数”，所以执行第三条规则：将状态变为偶数且读写头右移1格。因为状态是偶数且当前读取符号为0，所以执行第二条规则，我们写入1并且将当前状态设为”halt”（停机）。以下是图灵机的厉害之处，图灵证明了这个简单假想机器可以在有足够内存和时间的情况下执行任何计算，他是一台通用计算机。同时一个很强大的伴生结论叫做“图灵完备”。现代的每个计算设备都是图灵完备的。那么怎么用图灵机回答可判定性问题呢？图灵设计了一个停机问题：给定一个图灵机的规则(program)以及输入纸带(input)，是否存在一种算法可以确定机器是否可以停机——是算到某一点终止程序还是进入了一个死循环？可惜视频上讲的实在是太烂了，我来回看都没看懂。这里直接上知乎的解释：假设我们想要测试的代码是一个函数其中t是一个字符串,我们可以用一个字符串表示任意输入,包括int,double,及复合数据类型;当f不需要输入时,t是一个空字符串。停机问题是指对给定任意的一个函数f和输入t,判断f对t是否会永远运行下去;如果程序的运行时间是有限长的,我们称f对t停机。遗憾的是,不存在这样的一个工具使得其能判断任意f的停机问题,即停机问题不可判定。以下我们用反证法证明这个断言。假设存在这样的一个函数可用于判断停机问题：其中f_code是我们要进行测试的函数f的ASCII源代码,我们可以认为对f_code进行编译得到了函数f。当f对t停机时,halts(f_code,t)返回true;当f对t不停机,halts(f_code,t)返回false。我们构造这样一个函数：即当f对f_code停机时,我们让modified_halts不停机;当f对f_code不停机时,modified_code停机。（至于f是否对f_code停机我们不关心，因为我们需要制造一个悖论）假设modified_halts这个函数的ASCII源代码是modified_halts_code,如果我们把modified_halts_code作为modified_halts的输入会是什么情况?若modified_halts对modified_halts_code停机,等价于halts(modified_halts_code,modified_halts_code)返回true,放入modified_halts函数中发现会进入if分支中，也就是说modified_halt接受modified_halts_code为输入时，程序进入死循环。根据停机的定义，这说明了modified_halts对modified_halts_code运行时间是无限长的，modified_halts对modified_halts_code是不停机的。若modified_halts对modified_halts_code不停机,说明halts(modified_halts_code,modified_halts_code)返回false,放入modified_halts函数中发现不会进入if分支中，也就是说modified_halt接受modified_halts_code为输入时，程序return。根据停机的定义，这说明了modified_halts对modified_halts_code运行时间是有限长的，modified_halts对modified_halts_code是停机的。综合以上两种情况,"modified_halts对modified_halts_code停机"当且仅当“modified_halts对modified_halts_code不停机”,这是一个矛盾,说明不存在这样一个halts函数可用于判断任意函数的可停机性。以上构造的程序f,halts,modified_halts就符合图灵机的定义。图灵已经证明了图灵机可以实现所有的计算（只要内存和时间无限），而停机问题就无法被图灵机解决，所以任何一种计算方法都不能解决停机问题（停机问题就属于一种形式逻辑描述的问题，我们希望算法对停机问题输出准确的“是”与“否”的答案）。因此不存在一种计算方法，可以能够输入一个以形式逻辑(formallogic)书写的语句，输出准确的“是”与“否”的答案，可判定性问题得到回答。因此Church和图灵都证明了计算机的能力有限。即使时间无限长、内存无限大，有些问题是计算机无法解决的。(后面的内容与计算机科普相关性不大，就不写上来了)以下是本集的总结：
图灵为何被称为人工智能之父
它是由一条无限长的纸袋子上读取命令来进行操作，从而模拟人类所有可能进行的任何计算过程。也就是说图灵机具有基本的输入和输出功能，并且还具有一个状态寄存器，保存机器当前的状态。
而这就是一台计算机的雏形了，为现代计算机的逻辑工作方式奠定了基础。
密码机破解1939年，二战爆发期间。
德军的作战信息正以莫尔斯码的形式在欧洲上空来回穿梭。这些莫尔斯码发出前都是由一种称作恩尼格玛的加密器加密，接收方又由同样的恩尼格玛解密。
在当时这个机器绝对是最先进的机械密码设备。
看到这里的小伙伴肯定会问，德军的这个设备真有这么牛么？
简单的说：恩尼格玛机器会加密明文，加密方式就是由它顶部的齿轮组合决定的。
恩尼格玛
每个齿轮都有26个可能的位置，机器前部还有一个插板，可以将两个字母互换，总共有数十亿种可能的设置。当时很多破译高手们绞尽脑汁也难以破解。于是这个难题交到了图灵手中，他率领着大约200多名精干人员进行密码分析。
他发现26个字母在恩尼格玛机中能替代8万亿个信息字符。这意味着，如果用十个人去检验每一种可能，就算不眠不休地进行验证，最少也需要两千万年的时间才能破译。
这明显普通人是根本没办法做到的，但是机器却可以。
于是他在波兰破译专家发明的一种叫做“炸弹”的原始解密仪器的基础上，凭借着他的天才设想，设计出一种全新的破译机。
这台机器主要由继电器构成，还用了80个电子管，由光电阅读器直接读入密码，每秒可读字符2000个。运行起来咔嚓咔嚓直响，它能对加密的消息尝试多种组合，这样就大大减少了检索量。
并最终破解了德军的种种加密机制，获取到了大量重要的情报，帮助盟军提早两年结束了战争，拯救了至少1400万生命。
图灵测试1950年，图灵设计了一个实验，这就是著名的图灵测试。
这个测试主要内容是什么呢？
我这里举个通俗易懂的例子:
想象下你和两个不同的人在交谈，那两个人在各自单独的房间里。不是面对面或者通过声音来交谈，而是使用来回传递信息的形式。
你可以问你想要问的任何问题，然后你就会收到回答。但是这两个人中有一个是计算机，如果你分辨不出来哪一个是人类，哪一个是电脑，那么这台计算机就算通过了“图灵测试”。
图灵测试的另一个版本，就是我们现在网站上的验证码。验证码是用来防止自动化软件在网站上发布垃圾信息，目的就是把人和机器区分开。
再比如如果你觉得这期的视频不错，就会给我视频点赞，以证明你是人类。但是机器却不可能这样做，如果机器也可以给我点赞的话，那么它就通过了“图灵测试”。
现代计算机雏形后来在1945年左右，冯诺依曼延续了图灵的思考和想法。发展提出了具有输入输出设备、运算器、存储器、控制器在内的电子计算机的基本架构。
正是从这些伟大想法的出现，人类的计算机时代乃至如今的信息时代，才正式开始。
图灵结局然而，就是这样一位才华横溢而且为战争立下巨大功勋的人，最后的结局却不尽如人意。
在图灵那个时代，同性恋在英国是非法的。
1952年他家中一起入室盗窃案的调查，那个小偷，也就是他的同性伴侣，向当局暴露了他的性取向。最后导致图灵被判处接受“化学阉割”。
但是药物改变了他的情绪和性格，虽然我们永远不会知道确切的情况。但是最广泛接受的结果是他于1954年服毒自尽。证据就是在他床的旁边放着一个沾满氰化物，而且啃了一口的苹果。
总结现在随着人工智能的深入研究，人们越来越认识到图灵思想意义的伟大。他开启了属于人工智能和数字化的新时代，被称为计算机科学之父、人工智能之父。
他将计算机用物理手段呈现出来，对计算机做出了最早的科学定义，并准确的预言百年之后人工智能的发展方向。
那么对于这么一个厉害的图灵，大家有什么看法呢？好啦，今天的内容就到这里，如果你喜欢我们“52赫兹实验室”。
欢迎订阅我们的频道，点赞转发或者在评论区和我交流。感谢观看，我们下期见咯..
最后附上视频版本：
视频链接地址返回搜狐，查看更多