|
科普 | 图灵完备
科普 | 除了图灵完备概念，还有图灵测试、图灵等价、图灵机、图灵奖
付少庆
付少庆
2021-05-29
关于图灵完备，很多区块链项目的白皮书中都说到自己的项目支持什么图灵完备，或者图灵等价，包括以前也说过以太坊的智能合约是图灵完备的，比特币舍弃了图灵完备等等。了解图灵完备有利于更好的理解区块链领域中的技术。
从图灵完备，我们可以整体的了解一下，图灵、图灵完备与图灵等价、图灵测试、图灵机、图灵奖。
1.图灵本人
艾伦·麦席森·图灵（Alan Mathison Turing），1912年生于英国伦敦。艾伦·麦席森·图灵少年时就表现出独特的直觉创造能力和对数学的爱好。
1926年，他考入伦敦有名的舍本(Sherborne)公学，受到良好的中等教育。他在中学期间表现出对自然科学的极大兴趣和敏锐的数学头脑。
1931年，图灵考入剑桥大学国王学院，由于成绩优异而获得数学奖学金。在剑桥，他的数学能力得到充分的发展。
1935年，当选为国王学院的研究员，并于次年荣获英国著名的史密斯(Smith)数学奖，成为国王学院声名显赫的毕业生之一。
1936年5月，提出了“图灵机”，它第一次在纯数学的符号逻辑，和实体世界之间建立了联系（建立了对应），为此后的计算机和“人工智能”奠定了理论基础。
1936年9月，图灵应邀到美国普林斯顿高级研究院学习，并与丘奇一同工作。
1938年夏，图灵回到英国，仍在剑桥大学国王学院任研究员，继续研究数理逻辑和计算理论，同时开始了计算机的研制工作。
1939年秋，他应召到英国外交部通信处从事军事工作，主要是破译敌方密码的工作。由于破译工作的需要，他参与了世界上最早的电子计算机的研制工作。他的工作取得了极好的成就，因而于1945年获政府的最高奖——大英帝国荣誉勋章(O．B．E．勋章)。
1945年，图灵结束了在外交部的工作，他试图恢复战前在理论计算机科学方面的研究，并结合战时的工作，具体研制出新的计算机来。这一想法得到当局的支持。同年，图灵被录用为泰丁顿(Teddington)国家物理研究所的研究人员，开始从事“自动计算机”(ACE)的逻辑设计和具体研制工作。
1945年到1948年，他在英国国家物理实验室工作，负责自动计算引擎的研究。
1948年，图灵接受了曼彻斯特大学的高级讲师职务。
1949年成为曼彻斯特大学计算机实验室的副主任，负责最早的真正意义上的计算机——“曼彻斯特一号”的软件理论开发，因此成为世界上第一位把计算机实际用于数学研究的科学家。
1950年，并提出了著名的“图灵测试”。
1950年，他提出关于机器思维的问题，他的论文“计算机和智能(Computing machinery and intelligence)，引起了广泛的注意和深远的影响。1950年10月，图灵发表论文《机器能思考吗》。这一划时代的作品，使图灵赢得了“人工智能之父”的桂冠。
1951年，由于在可计算数方面所取得的成就，成为英国皇家学会会员，时年39岁。
1954年6月7日，图灵被发现死于家中的床上，床头还放着一个被咬了一口的苹果，当时图灵41岁。
2. 图灵完备与图灵等价
图灵完备：一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。一个能计算出每个图灵可计算函数（Turing-computable function）的计算系统被称为图灵完备的。一个语言是图灵完备的，意味着该语言的计算能力与一个通用图灵机 （Universal Turing Machine）相当，这也是现代计算机语言所能拥有的最高能力。
在可计算理论中，当一组数据操作的规则（一组指令集，编程语言，或者元胞自动机）满足任意数据按照一定的顺序可以计算出结果，被称为图灵完备（turing complete）。一个有图灵完备指令集的设备被定义为通用计算机。如果是图灵完备的，它（计算机设备）有能力执行条件跳转（“if” 和 “goto”语句）以及改变内存数据。 如果某个东西展现出了图灵完备，它就有能力表现出可以模拟原始计算机，而即使最简单的计算机也能模拟出最复杂的计算机。所有的通用编程语言和现代计算机的指令集都是图灵完备的（C++ template就是图灵完备的），都能解决内存有限的问题。图灵完备的机器都被定义有�茩�内存，但是机器指令集却通常定义为只工作在特定的，有限数量的RAM上。
图灵等价：我们可能经常会在某些文章里面看到图灵等价（Turing equivalence）和图灵完备(Turing completeness)，但是这两个词的含义是有区别的。尤其是很多书或文章经常对这两个词进行混用，可能会把事情搞复杂。
在可计算理论里，一个数据操作规则的系统（比如：指令集、编程语言、细胞自动机）被称作图灵完备或者通用计算的，当且仅当它可以被用来模拟单带图灵机。在可计算理论里，有一个很相关的概念叫图灵等价。当计算机 P 和计算机 Q 是图灵等价的，P可以模拟Q而且Q也可以模拟P（从理论上，两个图灵等价的系统可以是非图灵完备的）。现实中，一个图灵完备的系统可以模拟图灵机，这个术语（即图灵等价）常常被用来指与图灵机等价。
所以一个图灵完备的系统可以被称为图灵等价的，如果任何它可以计算的函数也是图灵可计算的。也就是它可计算的函数和图灵机可计算的函数是完全相同的。换句话说，就是图灵等价的系统就是能模拟通用图灵机同时也能也被通用图灵机模拟的系统，所有已知的图灵完备的系统都是图灵等价的。
通过上面的分析，我们就可以清楚的知道这两个词的意思和关系了。图灵等价有两个意思，一个是指两个计算系统在可计算性上计算能力相同；另一个，也是常用的一个就是指一个系统的计算能力与通用图灵机计算能力相同（在可计算性的意义上）。而图灵完备是指能够模拟通用图灵机的计算系统。而所有已知的图灵完备的系统都是图灵等价的，这也增加了对丘奇-图灵论题的支持。因此，就简单的理解来说，在现有的计算机系统（编程语言、指令集等）上，使用图灵等价和图灵完备是一个意思。
3. 图灵机
1935年，一个夏天。英国剑桥郁郁葱葱，23岁的图灵在此读书。这位年轻人性格内向，做人偏执，还是一名天赋异禀的马拉松跑者。他的马拉松最好成绩是2小时46分，还差点代表英国国家队参加奥运会。某次长跑后，图灵瘫倒在草地上，大口呼吸着剑桥的空气，心跳逐渐平复，脑中却出现了一场风暴。他一跃而起，跑回宿舍，在狂热的心跳中写下了脑中的风暴。他假想出一台“图灵机”：它可以从一条纸带上读取命令、进行操作，从而模拟任何“明确程序”。
他进一步证明人们可以设计出通用图灵机，模拟任何图灵机的运作，然后他进一步证明了即便通用图灵机也�茠k让所有命题可判断——我们不能用一个算法来判定一台给定的图灵机是否会停机。
图灵机的整个构造是一场思想实验。它用纸笔和头脑完成，不是一台真的机器——在图灵证明了存在通用图灵机后的十来年，第一台可编程的计算机被建造出来了。图灵机后来成为整个电子计算机的蓝图。
图灵机理论示意图
图灵机理论示意图
在第二次世界大战中，他加入了英国绝密的破解德军谜团密码（Enigma）计划。在图灵的领导下，秘密工作小组几乎破解了所有使用谜团密码的情报，构成二战转折点，成为战胜纳粹的重要因素。
战后，图灵的兴趣又回到他脑中的世界。这位天才科学家继续着他纯粹意义上的头脑风暴——用思考，而不是手，去实现不完美世界中“可以自行迭代的机器”。如今的互联网、人工智能与整个计算机世界，和彼时图灵的设想高度吻合。
设想一下，我们在计算乘法的时候：在每个时刻，我们只将注意力集中在一个地方，根据已经读到的信息移动笔尖，在纸上写下符号或数字；而指示我们写什么怎么写的，则是早已背好的九九乘法表，以及简单的加法。
参考维基百科中图灵机的基本思想：图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某个位置的符号和（b）此人当前思维的状态。
图灵机的实现结构并不复杂，它有一条�茩�长的纸带，纸带由方格组成。有一个读写头在纸带上移来移去，读写头连接控制器，控制器内有状态转移表，还有一些固定的程序。在每个时刻，读写头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。图灵机不断重复上述的步骤，这便是执行的过程。
4. 图灵测试
1950年，图灵发表了题为《机器能思考吗》的论文，在论文里提出了著名的“图灵测试”。论文的开篇是一条明确的声明：“我准备探讨‘机器能思考吗’这个问题。”然后，童心未泯的图灵设计了一个游戏来解释这个问题的实证含义。他为人工智能给出了一个完全可操作的定义：如果一台机器输出的内容和人类大脑别�茪G致的话，那么我们就没有理由坚持认为这台机器不是在“思考”。这就是“人工智能”的最初设想，这份设想也在�荍峇�让图灵摘得了“人工智能之父”的桂冠。
图灵测试
图灵测试
图灵测试，也就是图灵所说的“模仿游戏”的操作很简单：一位询问者将自己的问题写下来，发给处于另外一个房间之中的一个人和一台机器，然后根据他们给出的答案确定哪个是真人。
至于何时会出现能够通过图灵测试的计算机，图灵给出了自己的预测：“我相信在50 年左右的时间内，计算机编程技术将可能……实现顺利通过模仿游戏的计算机，普通询问者在经过5 分钟的询问之后的判断准确率将不高于70%。”
图灵预想到自己对思考的定义将会引来许多质疑，所以他尝试在论文中逐一反驳它们。针对来自神学方面的质疑，也就是上帝只将灵魂和思考能力赐给了人类，图灵表示这种观点实际上是对“上帝的全知全能的严重限制”。他提出了一个问题：上帝是否“有自由向一头合适的大象授予灵魂”？想必他是可以这样做的，那么按照同样的逻辑，上帝当然也可以随心所欲地向一台机器授予灵魂。这番话从不信仰上帝的图灵口中说出还是有些讽刺意味的。
在《计算机器与智能》发表之后的几年时间里，图灵似乎很喜欢参与到自己惹出的争论当中。他以自己带有讽刺性的幽默感取笑了那些关人类高等意识的主张：“终有一天，女士们会带着她们的计算机到公园散步，并且互相诉说“我的宝贝计算机在今天早上跟我说了这么一件有趣的事情”！智能手机是不是完全是这种预测？
5. 图灵奖
图灵奖杯
图灵奖杯
图灵奖，由美国计算机协会(ACM)于1966 年设立，有“计算机界诺贝尔奖”之称。奖杯是一个银色的碗。
从1966年到2019年，图灵奖已经走过了半个多世纪，这也是计算机科学走过的半个世纪，获奖成果串连起来，就是一部计算机科学史。 这条旅途跌宕起伏，光影变幻，人类历史上从没有过哪个学科，在破壳而出后的短短半个世纪里推进如此之远。图灵奖的奖金设奖初期为20万美元，1989年起增到25万美元，奖金通常由计算机界的一些大企业提供。目前图灵奖由Google公司赞助，奖金为100万美元。
对于每一个行业和领域来说，几乎都存在一两项令其领域内所有人视为“终极荣誉”的大奖，例如电影业的奥斯卡奖、新闻领域的普利策奖，数学领域的沃尔夫奖和费尔兹奖等等。而在计算机行业，图灵奖则是当之�虓\的最高奖项。
从1966年颁发图灵奖至今，已有50多个年头，共授予了70位科学家。据相关资料统计，截止2018年，美国斯坦福大学的图灵奖人数(校友或教职工)位列世界第一，美国麻省理工学院、美国加州大学伯克利分校并列世界第二；哈佛大学和普林斯顿大学分列世界第四和第五名。其中美国学者最多，此外还有英国、瑞士、荷兰、以色列、挪威等国少数学者。
华人学者目前仅有2000年图灵奖得主姚期智一人。
姚期智，1946年出生于中国上海，计算机学家，2000年图灵奖获得者，美国国家科学院院士、美国艺术与科学学院院士、中国科学院院士、港科院创院院士，清华大学高等研究中心教授，香港中文大学计算机科学与工程学系教授，清华大学-麻省理工学院-香港中文大学理论计算机科学研究中心主任，清华大学金融科技研究院管委会主任。他的主要贡献领域为计算理论，包括伪随机数生成，密码学与通信复杂性。
图灵是现代计算机设计思想的创始人，对计算机的贡献杰出！
参考文献：
[1] [英] 安德鲁·霍齐斯 著，孙天齐 译，《艾伦·图灵传》2017年10月
| 
