1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”。
在这篇开创性的论文中,图灵给“可计算性”下了一个严格的数学定义，并提出著名的图灵机"(TuringMachine)的设想。
“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想像得到的可计算函数。
"图灵机"与"冯.诺伊曼机"齐名，被永远载入计算机的发展史中。
1950年10月，图灵又发表了另一篇题为"机器能思考吗"的论文,成为划时代之作。
也正是这篇文章,为图灵赢得了"人工智能之父"的桂冠。
故事从谜开始
英国现代计算机的起步是从德国的密码电报机——Enigma(谜)开始的,而解开这个谜的不是别人,正是阿兰·图灵,一个在计算机界响当当的人物,可与美国的冯·诺依曼相媲美的电脑天才。
在他短暂的生涯中,图灵在量子力学、数理逻辑、生物学、化学方面都有深入的研究,在晚年还开创了一门新学科——非线性力学。
图灵英年早逝。
在他42年的人生历程中,他的创造力是丰富多彩的,他是天才的数学家和计算机理论专家。
24岁提出图灵机理论,31岁参与COLOSSUS的研制,33岁设想仿真系统,35岁提出自动程序设计概念,38岁设计"图灵测验"。
这一朵朵灵感浪花无不闪耀着他在计算机发展史上的预见性。
特别是在60年代后当然,图灵最高的成就还是在电脑和人工智能方面,他是这一领域开天辟
地的大师。
为表彰他的贡献,专门设有一个一年一度的"图灵奖",颁发给最优秀的电脑科学家。
这枚奖章就像"诺贝尔奖"一样,为计算机界的获奖者带来至高无上的荣誉。
而阿兰·图灵本人,更被人们推崇为人工智能之父,在计算机业十倍速变化的历史画卷中永远占有一席之地。
他的惊世才华和盛年夭折,也给他的个人生活涂上了谜一样的传奇色彩。
每次骑车时,他总是嘴里念念有词,在心里细细计算,这链条也怪,总是转到一定的圈数就滑落了,而图灵竟然能够做到在链条下滑前一刹那停车,让旁观者佩服不已,以为图灵在玩杂技。
后来图灵又居然在脚踏车旁装了一个小巧的机械记数器,到圈数时就停,歇口气换换脑子,再重新运动起来。
1936年,图灵向伦敦权威的数学杂志投了一篇论文,题为《论数字计算在决断难题中的应用》。
在这篇开创性的论文中,图灵给"可计算性"下了一个严格的数学定义,并提出著名的"图灵机"(TuringMachine)的设想。
"图灵机"不是一种具体的机器,而是一种思想模型,可制造一种十分简单但运算能力极强的计算机装置,用来计算所有能想像得到的可计算函数。
装置由一个控制器和一根假设两端无界的工作带(起存储器的作用)组成。
工作带被划分为大小相同的方格,每一格上可书写一个给定字母表上的符号。
控制器可以在带上左右移动,它带有一个读写出一个你期待的结果。
外行人看了会坠入云里雾里,而内行人则称它是"阐明现代电脑原理的开山之作",并冠以"理想计算机"的名称。
这篇论文在纸上谈了一把兵,创造出一个"图灵机"来。
但现代通用电脑确实是用相应的程序来完成任何设定好的任务。
这一理论奠定了整个现代计算机的理论基础。
"图灵机"更在电脑史上与"冯·诺依曼机"齐名,被永远载入计算机的发展史中。
图灵机理论不仅解决了纯数学基础理论问题,一个巨大的"意外"收获则是,理论上证明了研制通用数字计算机的可行性。
虽然早在100年前的1834年,巴贝奇(CharkBabbage,1792～1871)就设计制造了"分析机"以说明具体的数字计算,但他的失败之处是没能证明"必然可行"。
图灵机理论不仅证明了研制"通用机"的可行性,而且比世界上第一台由德国人朱斯(K·Zuze)于1941年制造的通用程序控制计算机Z-3整整早5年。
这不得不使人惊叹这一理论的深刻意义。
谜语图灵
正当图灵的理论研究工作进一步深入时,战争爆发了。
他被派往布雷契莱庄园承担"超级机密"研究。
当时的布雷契莱庄园是一所"政府密码学校",即战时的英国情报破译中心。
在这座幽静的维多利亚式建筑里,表面上鸟语花香、人迹罕见,其实每天都有12000多名志愿者在这里夜以继日地工作,截获、整理、破译德国的军事情报,有些结果甚至直达丘吉尔首相本人手中。
在这里,图灵被人们称为"教授",没有人知道他的真名。
当时德国有一个名为"Enigma"(谜)的通信密码机,破译高手们绞尽脑汁也难以破解。
这个难题交到了图灵手中,他率领着大约200多名精干人员进行密码分析,其中甚至还包括象棋冠军亚历山大。
分析和计算工作非常复杂,26个字母在"Enigma"机中能替代8万亿个谜文字母。
如果改动接线,变化会超过2.5千万亿亿。
最后多亏波兰同行们提供了一台真正的"Enigma",图灵才凭借着他的天才设想设计出一种破译机。
这台机器主要由继电器构成,还用了80个电子管,由光电阅读器直接读入密码,每秒可读字符2000个,运行起来咔嚓咔嚓直响。
它被图灵戏称为"罗宾逊",至今没人能搞懂图灵究竟如何指挥它工作。
但"罗宾逊"的确神通广大,在它的密报下,德国飞机一再落入圈套,死无葬身之地。
1945年,图灵带着大英帝国授予的荣誉勋章,来到英国国家物理研究所担任高级研究员。
两年后,图灵写了一份内部报告,提出了"自动程序"的概念,但由于英国政府严密、死板的保密法令,这份报告一直不见天日。
1969年,美国的瓦丁格(Woldingger)发表了同样成果,英国才连忙亮出压在箱底的宝贝,终于在1970年给图灵的报告"解密"。
图灵的这份报告后来收入爱丁堡大学编的《机器智能》论文集中。
由于有了布雷契莱的经验,图灵提交了一份"自动计算机"的设计方案,领导一批优秀的电子工程师,着手制造一种名叫ACE的新型电脑。
它大约用了800个电子管,成本约为4万英镑。
1950年,ACE电脑就横空出世,开始公开露面,为感兴趣的人们玩一些"小把戏",赢得阵阵喝彩。
图灵在介绍ACE的内存装置时说:"它可以很容易把一本书的10页内容记住。
"显然,ACE是当时世界上最快、最强劲的电子计算机之一。
1946年,在纽曼博士的动议下,皇家学会成立电脑实验室。
纽曼博士是皇家学会会员,又是当年破译小组的成员,正是他对"赫斯·鲁宾逊"的制造起了关键作用。
皇家学会的这一新实验室不在伦敦,而是设在曼彻斯特大学,由纽曼博士牵头负责。
1946年7月,研制基金到位,纽曼博士开始招募人选。
阿兰·图灵也在次年9月加盟电脑实验室。
一时间,曼彻斯特大学群英会萃。
到了1949年10月,各项改进工作都已展开,夹在两层存储器之间的自动控制系统已正常运转,并能在程序的控制下,实现磁鼓和阴极射线管存储单元间信息交互。
图灵设计出一些协同电路来做输入和输出的外设。
有关电动打字设备也是图灵通过老关系从他战时供职的外交部通信部门弄过来的,其中甚至包括一个战后从德国人那里收缴来的穿孔纸带键盘。
这样,整个模型机已大功告成。
在整个试验阶段,大家忙上忙下。
1949年底,模型机交付给曼彻斯特当地的一家叫弗兰尼蒂(Ferranti)的电子公司,开始正式建造。
1951年2月完工,通称"迈可1型"。
它有4000个电子管,72000个电阻器,2500个电容器,能在0.1秒内开平方根、求对数和三角函数的运算。
比起先前的模型机,"迈可1型"功能更为齐全,静电存储器的内存容量已翻倍,能存256个40位字长字,分别存在8个阴极射线管中,而磁鼓的容量能扩容到16384个字,真是一项了不起的工程。
与冯·诺依曼同时代的富兰克尔(Frankel,冯氏同事)在回忆中说:冯·诺依曼没有说过"存储程序"型计算机的概念是他的发明,却不止一次地说过,图灵是现代计算机设计思想的创始人。
当有人将"电子计算机之父"的头衔戴在冯·诺依曼头上时,他谦逊地说,真正的计算机之父应该是图灵。
这说明图灵在二战结束后就开始了后来被称为"人工智能"领域的探索,他开始关注人的神经网络和电脑计算之间的关联。
1950年,图灵又来到曼彻斯特大学任教,同时还担任该大学自动计算机项目的负责人。
就在这一年的十月,他又发表了另一篇题为《机器能思考吗?》的论文,成为划时代之作。
也正是这篇文章,为图灵赢得了一顶桂冠--"人工智能之父"。
在这篇论文里,图灵第一次提出"机器思维"的概念。
他逐条反驳了机器不能思维的论调,做出了肯定的回答。
他还对智能问题从行为主义的角度给出了定义,由此提出一假想:即一个人在不接触对方的情况下,通过一种特殊的方式,和对方进行一系列的问答,如果在相当长时间内,他无法根据这些问题判断对方是人还是计算机,那么,就可以认为这个计算机具有同人相当的智力,即这台计算机是能思维的。
这就是著名的"图灵测试"(TuringTesting)。
当时全世界只有几台电脑,根本无法通过这一测试。
但图灵预言,在本世纪末,一定会有电脑通过"图灵测试"。
终于他的预言在IBM的"深蓝"身上得到彻底实现。
当然,卡斯帕罗夫和"深蓝"之间不是猜谜式的泛泛而谈,而是你输我赢的彼此较量。
故事以谜结束
1951年,图灵以他杰出的贡献被当选为英国皇家学会会员。
就在他事业步入辉煌之际,灾难降临了。
1952年,图灵遭到警方拘捕,原因是他是一个同性恋者。
与其他一些智慧超群的人物一样,图灵在个人生活方式上也"与众不同"。
当时,人们对同性恋还没有像现在这样宽容,而是把这种行为当作一桩伤风败俗的罪孽。
事情的败露是这样的,当时有一位叫琼·克拉克(JoanClarke)的姑娘爱上了图灵,图灵也对对方很有好感,并向对方求婚,琼欣然接受。
但不久,图灵自己退缩了,告诉琼,他是同性恋者。
在1948年,图灵就由于同性恋倾向,离开了当时属于高度保密的英国国家物理实验室(NPL)。
但也有人说,图灵是被英国军事情报部门"开除"出去的,对于这位天才的离去,许多人怅惜不已。
1952年3月31日,图灵更因为和曼彻斯特当地一位青年有染,被警方逮捕。
在法庭上,图灵既不否认,也不为自己辨解。
在庄严的法庭上,他郑重其事地告诉人们:他的行为没有错,结果被判有罪。
在入狱和治疗两者中间,图灵选择了注射激素,来治疗所谓的"性欲倒错"。
此后图灵开始研究生物学、化学,还和一位心理医生有很深的交往。
那时,他的脾气已变得躁怒不安,性格更为阴沉怪僻。
1953年3月,他因为接待过一位被英国警方注意的挪威客人,成为警方的目标,甚至去希腊度假时也被跟踪。
1954年6月8日,图灵42岁,正逢进入他生命中最辉煌的创造顶峰。
一天早晨,女管家走进他的卧室,发现台灯还亮着,床头上还有个苹果,只咬了一小半,图灵沉睡在床上,一切都和往常一样。
但这一次,图灵是永远地睡着了,不会再醒来……经过解剖,法医断定是剧毒氰化物致死,那个苹果是在氰化物溶液中浸泡过的。
图灵的母亲则说他是在做化学实验时,不小心沾上的,她的"艾伦"从小就有咬指甲的习惯。
但外界的说法是服毒自杀,一代天才就这样走完了人生。
图灵机的诞生
1936年11月30日出版的《伦敦数学学会会刊》，有一篇标题看来平平无奇的文章︰〈论可计算数及其在判定问题上的一个应用〉，作者是图灵。
2012年，图灵诞生100周年，学界将该年订为「图灵年」，举办活动以纪念其重大贡献。
2014年电影《模仿游戏》也讲述了图灵于二战时协助破解德军密码的故事（虽然忽略了波兰数学家的贡献），相信不少人对图灵的名字、贡献及其因同性恋倾向被迫害的经历略有所闻。
图灵的众多贡献当中，最为重要的正是1936年这份论文，因为在文中他首次提出「图灵机」这个概念——文中他称为a-机器，a代表「自动」（automatic）——为现代计算机、计算机科学及计算理论奠下数学基础。
当然，除图灵以外，他之前及之后均有不少人对计算机发展贡献良多。不过在这篇文章，让我们先看一看他的「图灵机」为何如此重要。
数学基础
一切源自一个貌似非常奇特、与计算机毫不相干的问题︰我们如何确定数学知识可靠？
19世纪，数学发展越来越抽象，因此亦出现了各种公理系统——公理是指被视作「不证自明」的命题，数学家以公理为基础，再用逻辑推论出不同数学定理。
但到了20世纪初，有批数学家（以及关心数学的哲学家）开始担心数学知识不够稳固，他们想确保由特定公理出发时，不会推论出现矛盾——假如有矛盾的话，数学就完了。
他们不是杞人忧天，当时集合论中出现了数个悖论（指一种导致矛盾的命题），或许会导致数学出现矛盾。
幸运的话，有些悖论可以透过引入新概念去解决，例如自数学界出现「极限」的严格定义后，甚少人会认为「阿基利斯永远无法追上乌龟」的芝诺悖论是个问题。
那个时候这批数学家大概分成三派，其中一派是数学家。
主导的「形式主义」。简略来说，形式主义者希望藉由把数学还原成纯粹符号的形式系统，再用（有限制的）数学去证明这个系统不会出现「0=1」之类的矛盾句，从而确保数学不会产生矛盾。
罗素及怀海德三大册《数学原理》，则是从逻辑主义出发，尝试以逻辑公理推导出整个数学系统——他们想的是，既然逻辑不可能自相矛盾，只要证明数学是由逻辑延伸出来，就可以确保数学一致。
两人终告失败（原因并非本文重点），不过书中改良自弗雷格（GottlobFrege）的逻辑系统，促进了数理逻辑发展。
其后逻辑学家整理出一套现称为「一阶逻辑」的系统，包含若干逻辑公理和推导规则，由此出发可以推导出不少已知的逻辑定理，是个很好用的系统。
判定问题
回到希尔伯特，他想完全将数学化约成一个仅有符号的形式系统（这方面罗素及怀海德贡献了不少），只要按照规则，完全不懂数学、不知道符号意义的人也可以推演出「数学定理」，这样就可以撇除人为错误（例如受直觉误导）。
他又希望找到一套清晰的判定程序，去确认如何判断一个逻辑公式是否属于逻辑系统的定理，假如成功，下一个目标自然是判断数学命题是否数学定理——这样数学家就不用再苦苦思索那些悬而未决的数学猜想，只要一起运行这个「判定程序」，就可以获得答案，简单直接。
不过，希尔伯特于1928年提出的这个「判定问题」，在1935至1936年期间，分别由数学家邱奇及图灵先后得出答案︰不可能。
要解决判定问题，首先需要厘清一个概念︰何谓「清晰的判定程序」？当然，有一些条件非常明显，例如程序必须是有限的——仅包含有限条规则、能够在有限时间完成。
程序当中的规则也必须极之简单，以符合希尔伯特的要求。
举个例，假如我要教一位小学生判定一个数字以否质数，可以利用他懂得「整数」、「除数」、「余数」和「比较大小」等概念，去让他按照程序执行，然后他就会发现7是质数、8不是质数、9不是质数…。
但希尔伯特所要求的还要更少——执行规则的人只能够辨认符号（不会把不同的符号混淆）、抄写符号、按照规则把符号串转换等，甚至不懂「加减乘除」等基本数学运算，也不会知道数学符号的意思。
图灵机
终于回到图灵的论文，在〈论可计算数〉中他设想以下一部机器，包含以下部份︰。
·一条纸带，这条纸带分成一格一格的（好吧听起来的确有点像厕所卫生纸），每格可以印一个符号。第一格的编号为0，然后是1、2、3…没有尽头，以表示空格。
·可以在纸带上左右移动的读写头，它每次能够读取所处位置那一格的内容（同一时间只可读取一格），亦可以改变其内容——改写其他符号或变成空格。
·会存在机器目前状态（state）的状态缓存器，每部机器的可能状态数目有限，其中一个称为「开始状态」，就是机器一开始时所处的状态。
·储存所有规则的指令集，机器会根据其目前状态以及读写头当时读取的方格内容来执行指令，进行下一步动作。
上述4个部份当中，决定机器如何运作的是指令集及状态。为方便说明，以下机器的状态以颜色表示，而符号只有0、1及（空格）。图灵把指令限制在这个形式︰。
·当处于A状态并读取到符号X时，写入符号Y，移动读写头，并转至B状态。
以下是一些例子︰
·当处于红色状态并读取到符号0时，写入符号1，读写头左移一格，并转至蓝色状态。
·当处于黄色状态并读取到符号1时，写入符号1（即维持原状），读写头留在原处，并维持在红色状态。
·当处于蓝色状态并读取到符号0时，清除符号（变成空格），读写头右移一格，并转至黄色状态。
如果没有适用的指令时，这部设想中的机器——后世称为图灵机——就会停止运作。
一个图灵机模型
不同图灵机分别，在于它们拥有不同的可能状态以及指令集——事实上，我们只需要看一部图灵机的指令集，就知道它可以有甚么状态，因此可以说，图灵机的指令集（以及一开始时纸带上的内容）决定了它如何运作。
这些看似非常简陋的图灵机其实可以做非常多事情，图灵在论文中举了两个图灵机作例子︰一个可以在纸带上不断印出「01010101….」，另一个可以印出「001011011101111...」。
事实上，我们也能设计出会进行加法、减法、乘法、除法、比较两个数字大小…的图灵机（在图灵机中，数字可用符号「1」的数量来表示，例如用「111」代表3、「1111111」代表7，数字与数字之间则用符号「0」去分隔）。
通用图灵机
图灵的〈论可计算数〉没有在此打住，正如上文所述，一部图灵机的指令集可以抽述了它如何运作，因此图灵就想到把图灵机（的指令集）编码，换言之，用不同的数字就可以表述不同的图灵机——就这样，每个图灵机都获得一个标准编号。
下一步，图灵构造了一部特别的图灵机，称为「通用图灵机」。通用图灵机可以「扮演」不同的图灵机——只要输入某部图灵机M的标准编号，它就可以像M一样印出相同的符号序列。
如果上面的句子太过抽象，不妨换个（灵异一点的）说法︰有了通用图灵机以后，理论上我们不再需要制造其他图灵机——因为其他图灵机都可以由「硬件」变成「软件」，「附上」通用图灵机来运作。
对，那就是为何我们打开手机、计算机上的计算数件，便能够使用计算器的功能——现代计算机某程度上是一部通用图灵机（当然，计算机没有无限长的纸带）。
通用图灵机成为现代计算机的理论模型，图灵这篇论文也奠定了计算机科学、可计算性理论等学科的基础。
当然，由纸上理论代为现实，中间还有一大段历史发展，图灵亦有参与，在此先行略过。（停机问题也是〈论可计算〉的重要结果，篇幅所限同样略过。）。
邱奇—图灵论题
在图灵之前，数学家——特别是关心数理逻辑的数学家——已经在思考如何严格定义「机械程序」或者「算法」，因为缺乏这个定义的话，界定「形式系统」时会出现一个问题︰怎样的符号变换规则可以接受？
哥德尔（KurtGdel）在1931年证明其著名的不完备定理时，引入了（原始）递归函数的概念，以便从数学角度讨论形式系统，其后他跟英年早逝的埃尔布朗（JacquesHerbrand）将之发展成广义递归函数。
但要直到图灵的论文面世后，哥德尔才认为人们能「精确及毫无疑问充足」地定义形式系统。
文首提到比图灵稍早解决判定问题的邱奇，在他1936年的论文中使用了λ演算（λ-calculus）去地义何谓「λ可计算函数」。
而对于任何（以自然数为定义域的）函数f(x)，如果存在一部可以顺序印出f(0),f(1),f(2)…的图灵机，那么这个函数就称为「图灵可计算函数」。
邱奇和图灵证明了这三种函数——广义递归函数、λ可计算函数及图灵可计算函数——等价，换言之，虽然它们有非常不同的定义，但实际上还是一样。
〈论可计算数〉发表以后，也有各种计算模型出现，但没有一个能够超越图灵机——它们所定义的函数，都是可以用图灵机（或λ演算、广义递归函数）去定义。
邱奇及图灵认为，任何可以计算的函数，都是λ可计算／图灵可计算函数，这称为「邱奇—图灵论题」。
他们把「可以计算的函数」这个直观概念，跟数学上有严格定义的「λ可计算／图灵可计算函数」划上等号，由于论题涉及直观概念，本身无法以数学证明。
根据理论计算机科学这80年来的发展，邱奇—图灵论题几乎无人质疑︰即使计算机速度突飞猛进，能够完成各种以往无法想象的任务，现实中我们仍然未能找到一个超越图灵机的计算模型（理论上倒有一些，但不包括现时的量子计算机模型）。
未来发展会怎样？不知道，可能他日人工智能的数学家、逻辑学家会发现到一个超越图灵机的计算模型——而我们无法理解？或者明天就有人发现了？（当然我认为这不可能。）。
没有〈论可计算数〉，我们也许还有「计算机」可用，但那些「计算机」应会截然不同，发展也慢得多。在图灵机面世80年后，我只想介绍一下这个对人类历史有深刻影响的故事。
看完本文有什么想说的吗？欢迎大家留言讨论哦~
还没有评论，来说两句吧...