除了图灵完备性的概念，还有图灵测试、图灵等价性、图灵机、图灵奖

关于图灵完备性，很多区块链项目的白皮书都提到了他们的项目支持什么图灵完备性或者图灵等价性。 图灵完备等等。 理解图灵完备性有助于更好地理解区块链领域的技术。

从图灵完备性，我们可以对图灵、图灵完备性和图灵等价性、图灵测试、图灵机、图灵奖有一个整体的认识。

1.图灵本人

艾伦·马西森·图灵

艾伦·马西森·图灵1912年出生于英国伦敦。艾伦·马西森·图灵年少时就表现出独特的直觉和创造力以及对数学的热爱。

1926年考入伦敦著名的舍伯恩公立学校以太坊图灵完备可以执行什么程序，接受了良好的中学教育。 中学时代就表现出对自然科学的浓厚兴趣和敏锐的数学头脑。

1931年，图灵考入剑桥大学国王学院，并以优异的成绩获得数学奖学金。 在剑桥，他的数学能力得到了充分的发展。

1935年被选为国王学院研究员，次年获得英国著名的史密斯（Smith）数学奖，成为国王学院著名的毕业生之一。

1936年5月，“图灵机”提出，首次建立了纯数学的符号逻辑与物理世界的联系，为后来的计算机和“人工智能”奠定了理论基础。

1936年9月，图灵应邀到美国普林斯顿高等研究院学习，并与丘奇一起工作。

1938年夏，图灵回到英国，仍在剑桥大学国王学院做研究员，继续研究数理逻辑和计算理论，同时开始了计算机的研制。

1939年秋，应召到英国外交部通信司从事军事工作，主要是破译敌方密码。 由于破译工作的需要，他参与了世界上最早的电子计算机的研制。 他的工作非常成功，以至于他于 1945 年获得了政府的最高奖项，即大英帝国勋章 (OBE)。

1945年，图灵结束了在外交部的工作。 他试图恢复战前在理论计算机科学方面的研究，并结合战时的工作来开发新的计算机。 这个想法得到了当局的支持。 同年，图灵被特丁顿国家物理研究所聘为研究员，开始从事“自动计算机”（ACE）的逻辑设计和具体开发工作。

1945年至1948年在英国国家物理实验室工作，负责自动计算引擎的研究。

1948年，图灵接受了曼彻斯特大学的高级讲师职位。

1949年任曼彻斯特大学计算机实验室副主任，负责最早的真正计算机——“曼彻斯特一号”的软件理论开发，从而成为世界上第一位真正利用计算机进行数学计算的科学家。研究。

1950年，他提出了著名的“图灵测试”。

1950年，他提出了机器思维的问题。 他的论文《计算机器与智能》引起了广泛关注和深远影响。 1950年10月，图灵发表论文《机器能思考吗？ 这一划时代的工作使图灵赢得了“人工智能之父”的称号。

1951年，39岁的他因在可计算数方面的成就成为英国皇家学会会员。

1954年6月7日，图灵被发现死在家中的床上，床头放着一个被咬过的苹果，时年图灵41岁。

2. 图灵完备与图灵等价

图灵完备：所有可计算的问题都可以计算，这样的虚拟机或编程语言称为图灵完备。 可以计算每个图灵可计算函数的计算系统被称为图灵完备的。 一种语言是图灵完备的，这意味着该语言的计算能力相当于一个通用图灵机（Universal Turing Machine），这是现代计算机语言所能拥有的最高能力。

在可计算理论中，当一组数据操作规则（一组指令集、编程语言或元胞自动机）满足任何数据并能按一定顺序计算结果时，称为图灵完备。 . 具有图灵完备指令集的设备被定义为通用计算机。 如果它是图灵完备的，它（计算机设备）就有能力执行条件跳转（“if”和“goto”语句）和改变内存中的数据。 如果一个东西表现出图灵完备性，它就有能力证明它可以模拟原始计算机，甚至最简单的计算机也可以模拟最复杂的计算机。 现代计算机的所有通用编程语言和指令集都是图灵完备的（C++模板是图灵完备的），可以解决内存受限的问题。 图灵完备机器被定义为具有无限内存，但机器指令集通常被定义为仅在特定的、有限数量的 RAM 上工作。

图灵等价：我们可能经常在一些文章中看到图灵等价和图灵完备，但这两个词的含义是不一样的。 特别是，很多书籍或文章经常将这两个词一起使用，这可能会使事情复杂化。

在可计算性理论中，数据操作规则系统（例如，指令集、编程语言、元胞自动机）被称为图灵完备或通用计算当且仅当它可以用于模拟单带图灵机时。 在可计算理论中，有一个非常相关的概念，称为图灵等价性。 当计算机P和Q是图灵等价时，P可以模拟Q，Q可以模拟P（理论上两个图灵等价系统可以是非图灵完备的）。 实际上，一个图灵完备系统可以模拟一个图灵机，这个术语（即图灵等价）常被用来指代与图灵机等价。

因此，如果一个图灵完备系统可以计算的任何函数也是图灵可计算的，则该系统可以称为图灵等价的。 也就是说，它的可计算函数与图灵机可计算的函数完全相同。 换句话说，图灵等效系统是可以模拟通用图灵机，也可以被通用图灵机模拟的系统。 所有已知的图灵完备系统都是图灵等价的。

通过上面的分析，我们可以清楚的知道这两个词的含义和关系。 图灵等价性有两种含义，一种是指两个计算系统在可计算性方面具有相同的计算能力； 性意识）。 图灵完备是指能够模拟通用图灵机的计算系统。 并且所有已知的图灵完备系统都是图灵等价的，这增加了对 Church-Turing 论点的支持。 因此，就简单的理解而言，在现有的计算机系统（编程语言、指令集等）上使用图灵等价性和图灵完备性是同一个意思。

3.图灵机

1935年，一个夏天。 英国剑桥郁郁葱葱，23岁的图灵就在这里求学。 这个年轻人内向、偏执，是一位有天赋的马拉松选手。 他的马拉松最好成绩是2小时46分，差点代表英国国家队出战奥运会。 长跑后，图灵倒在草地上，呼吸着剑桥的空气，心跳渐渐平复，脑海中却出现了风暴。 他一跃而起，跑回宿舍，在狂热的心跳中写下脑海中的风暴。 他设想了一台“图灵机”：它可以从一张纸带上读取命令，进行运算，从而模拟出任何“清晰的程序”。

他进一步证明了可以设计一个通用图灵机来模拟任何图灵机的运行，然后他进一步证明即使是通用图灵机也不能使所有命题可判定——我们不能用算法来确定给定的图灵机是否会存在是停机时间。

图灵机的整个构造是一个思想实验。 它是用笔、纸和头脑完成的，而不是一台真正的机器——第一台可编程计算机是在图灵证明通用图灵机存在十年左右之后建造的。 图灵机后来成为整个电子计算机的蓝本。

图灵机理论示意图

二战期间，他加入了英国的绝密恩尼格玛计划，破译了德军的恩尼格玛密码。 在图灵的带领下，秘密工作组利用神秘密码破解了几乎所有的情报，构成了二战的转折点，成为打败纳粹的重要因素。

战后，图灵的兴趣又回到了他脑海中的世界。 这位天才科学家继续他纯粹意义上的头脑风暴——用思维而非双手，在不完美的世界中实现“可以自行迭代的机器”。 今天的互联网、人工智能乃至整个计算机世界，都与图灵当时的设想高度吻合。

想象一下，当我们计算乘法时：每一时刻，我们只专注于一个地方，根据阅读的信息移动笔尖，在纸上写下符号或数字； 我所学的是我已经背过的九十九乘法表，还有简单的加法。

参考维基百科中图灵机的基本思想：图灵的基本思想是用一台机器来模拟人用纸笔进行数学运算的过程。 他把这样的过程看作是以下两个简单的动作：在纸上书写或擦除一个符号； 将注意力从纸上的一个位置转移到另一个位置； 在每个阶段，此人决定下一步做什么，具体取决于 (a) 此人当前关注的纸上位置和 (b) 此人当前的精神状态。

图灵机的实现结构并不复杂。 它有一条无限长的纸带，纸带是由正方形组成的。 纸带上有一个左右移动的读写头，读写头与控制器相连，控制器中有一个状态转换表，以及一些固定的程序。 每时每刻，读写头需要从当前磁带中读取一个格子信息，然后根据自身内部状态查找程序表，根据程序向磁带格输出信息，并转换自身内部状态，然后移动。 图灵机不断重复以上步骤，这就是执行的过程。

4.图灵测试

1950年，图灵发表了一篇题为《机器能否思考》的论文，提出了著名的“图灵测试”。 该论文以一个明确的声明开头：“我将探讨‘机器能思考吗？’这个问题。” 然后天真烂漫的图灵设计了一个游戏来解释这个问题的经验含义。 他为人工智能提供了一个完美的操作性定义：如果机器的输出与人脑无法区分以太坊图灵完备可以执行什么程序，那么就没有理由坚持认为机器没有在“思考”。 这就是“人工智能”最初的想法，而这个想法也让图灵获得了“人工智能之父”的称号。

图灵测试

图灵测试，也就是图灵所说的“模仿游戏”，其操作非常简单：提问者写下自己的问题，发给另一个房间的人和机器，根据他们给出的答案来判断这是真实的人。

至于何时能出现能够通过图灵测试的计算机，图灵给出了自己的预测：“我相信在50年左右的时间里，计算机编程艺术将有可能……实现能够顺利通过图灵测试的计算机。”模仿游戏，经过5分钟的提问，评委的准确率不会高于70%。

图灵预料到他对思维的定义会招来很多质疑，因此他在论文中试图一一反驳。 针对神学界对上帝只赋予人类灵魂和思考能力的质疑，图灵表示，这种观点实际上是“对上帝全知全能的严重局限”。 他提出一个问题：上帝是否“有自由将灵魂赋予合适的大象”？ 想必他可以做到这一点，那么按照同样的逻辑，上帝当然可以随意将灵魂赋予机器。 有点讽刺的是，这些话出自不信上帝的图灵之口。

在 Computing Machinery and Intelligence 出版后的几年里，图灵似乎很享受参与他所创造的辩论。 他用自己讽刺的幽默感取笑人类更高意识的说法：“有一天，女士们会带着她们的电脑去公园散步，并互相告诉对方‘我珍贵的电脑今天早上和我在一起。说这么有趣事物”！ 智能手机都那么可预测吗？

5. 图灵奖

图灵奖杯

图灵奖由计算机协会（ACM）于1966年设立，被誉为“计算机界的诺贝尔奖”。 奖杯是一个银碗。

从1966年到2019年，图灵奖走过了半个多世纪，这也是计算机科学的半个世纪。 获奖成果连在一起构成了一部计算机科学史。 这段旅程充满了跌宕起伏和光影变化。 在人类历史上，还从来没有哪一门学科在破壳而出后仅半个世纪就发展到如此地步。 图灵奖的奖金最初定为20万美元，1989年增加到25万美元，奖金通常由计算机行业的一些大公司提供。 目前，图灵奖由谷歌赞助，奖金为100万美元。

对于每一个行业和领域，几乎都有一两个奖项被业内人士视为“终极荣誉”，比如电影界的奥斯卡奖、新闻界的普利策奖、新闻界的沃尔奖等。数学领域。 夫奖、菲尔兹奖等 在计算机界，图灵奖是当之无愧的最高奖项。

图灵奖自1966年颁发至今已有50多年，共有70位科学家获奖。 据相关统计，截至2018年，斯坦福大学获得图灵奖的人数（校友或教职员工）位居世界第一，麻省理工学院和加州大学伯克利分校并列世界第二； 哈佛大学和普林斯顿大学分列世界第四和第五。 其中以美国学者最多，也有少数来自英国、瑞士、荷兰、以色列、挪威等国的学者。

目前，获得2000年图灵奖的中国学者只有姚期智一人。

姚期智，1946年出生于中国上海，计算机科学家，2000年图灵奖获得者，美国国家科学院院士，美国艺术与科学院院士，中国科学院院士，创始成员香港科学院院士，清华大学高等研究中心教授，香港中文大学计算机科学与工程系教授，清华大学-麻省理工学院-香港中文大学计算机理论系主任科学研究中心，清华大学金融科技研究院管委会主任。 他的主要贡献领域是计算理论，包括伪随机数生成、密码学和通信复杂性。

图灵是现代计算机设计思想的奠基人，对计算机做出了卓越的贡献！

参考：

[1] [英文]安德鲁·霍奇斯，孙天琪译，《艾伦·图灵传》，2017年10月