带你深入理解图灵机--天才所在的时代

这几年由于区块链的大热，以太坊独特的solidity语言实现智能合约功能， 图灵完备 这个词走进大家的视线。

没有计算机专业知识的同学其实很难理解这个词的意思，其实计算机专业的同学都没有深入理解图灵机，图灵完备，图灵测试等概念包含的内涵。为了方便理解区块链技术，理解智能合约，笔者准备分几篇文章来带大家从浅入深，一步一步带你深入理解图灵机，相信通过这几篇文章能就能够理解什么是图灵完备。

艾伦·麦席森·图灵（Alan Mathison Turing，1912年6月23日－1954年6月7日），英国数学家、逻辑学家， 被称为计算机科学理论之父，人工智能之父。

1931年，图灵考入剑桥大学国王学院，由于成绩优异而获得数学奖学金。

1936年5月，年仅24岁的图灵发表一篇题为《论数字计算在决断难题中的应用》的论文，论文中提出一种计算装置，后被称为 “图灵机” ，图灵机不是具体的计算机，而是一种计算概念、计算理论。

1938年在普林斯顿获博士学位，其论文题目为“以序数为基础的逻辑系统”，在数理逻辑研究中产生了深远的影响；同年图灵回到英国，在剑桥大学国王学院任研究员。

第二次世界大战期间，1939年图灵到英国外交部通信处从事军事工作，主要是破译敌方密码的工作。由于破译工作的需要，他参与了世界上最早的电子计算机的研制工作。他的工作取得了极好的成就，破译了德国人Enigma密码，于1945年获政府的最高奖——大英帝国荣誉勋章。

1945年，图灵结束了在外交部的工作，他试图恢复战前在理论计算机科学方面的研究，具体研制出新的计算机来。

1950年他发表论文《计算机器与智能》（ Computing Machinery and Intelligence），为后来的人工智能科学提供了开创性的构思。提出著名的 图灵测试 。

1950年，1950年10月，图灵发表论文《机器能思考吗》。这一划时代的作品，使图灵赢得了“人工智能之父”的桂冠。此时，人工智能也进入了实践研制阶段。随着这几年AI技术的不断成熟，人们越来越认识到图灵思想的深刻性：它们至今仍然是人工智能的主要思想之一。

1954年6月7日，年仅41岁的图灵被发现死于家中的床上，床头还放着一个被咬了一口的苹果。这就是现在大名鼎鼎的苹果电脑公司logo的来源。

从图灵的生平中，我们知道，他出生在20世纪初，1912年。

在世界国家格局上，这个时候刚刚爆发第一次世界大战（1913~1921），紧接着1939年至1945年第二次世界大战，大家知道，这两次世界大战倒逼了很多科技的发展，二战期间恰好是图灵青年时代。

在科技文明发展上，由于逻辑的数学化，促使了数理逻辑学科的诞生和发展。但同时这个时期数学上发生了第三次数学危机，具体介绍在下方。图灵在剑桥读大学期间，修读了“数学基础”课程，授课人是纽曼，纽曼整个课程包含对哥德尔不完备性定理的证明和尚未解决的判定性问题。

这些科技事件的背后，其实是人们在认知上，对 可计算性理论 的研究，图灵正是这个问题终结者。

随便提一下，爱因斯坦1905年提出狭义相对论，1927年年仅15岁的图灵为了帮助母亲理解相对论，还写过论文的摘要。

在20世纪以前，人们普遍认为，所有的问题类都是有算法的，人们的计算研究就是找出算法来。1900年，当时著名的大数学家希尔伯特在世纪之交的数学家大会上给国际数学界提出了著名的23个数学问题。

其中第十问题是这样的：

“丢番图方程”指：有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行。

上面这个问题简单点解释是：随便给一个不确定的方程，是否通过有限的步骤运算，判断这个方程是否存在整数解。

这个问题在1970年，苏联一个数学家证明了其实很多数学问题，是没有答案，甚至没有答案的问题比有答案的问题还要多。

这里就提出来了有限的、机械的证明步骤的问题，其实就是算法。但在当时，人们还不知道“算法”是什么。实际上，当时数学领域中已经有很多问题都是跟“算法”密切相关的，因而，科学的 “算法” 定义呼之欲出。之后到了30年代的时候，终于有两个人分别提出了精确定义算法的方法，一个人是图灵，一个人是丘奇。而其中图灵提出来的图灵机模型直观形象。

图灵思考这个问题的方式和常人不一样，在写前面提到的论文《论可计算数及其在判定性问题上的应用》的时候，图灵在思考三个问题

图灵这样的天才考虑问题的认知是高屋建瓴的。

图灵首先考虑的是是否所有数学问题都用解，如果这个问题不解决，辛辛苦苦解题，最后发现无解，一切的努力都是浪费时间和精力。

对于存在答案的数学问题，只有部分是可以在有限步骤内完成，这样把计算机的边界确定下来了。

确定了边界之后，就要设计一种通用、有效、等价的机器，保证可以按照这个方法做事，最后得到答案。而图灵机就是图灵设计出来的这样的一个机器，严格来讲是一种数学模型、计算理论模型。

从图灵机提出到现在已经过去了80多年，今天所有的计算机，包括量子计算机都没有超出图灵机的理论范畴。

第三次数学危机产生于十九世纪末和二十世纪初，当时正是数学空前兴旺发达的时期。首先是逻辑的数学化，促使了数理逻辑这门学科诞生。

早在19世纪末的时候，康托尔为集合论做了奠基性的研究。人们发现，运用集合这个概念可以概括所有的数学，也就是说集合是一切数学的基础。然而就当这座大厦即将完工的时候，一件可怕的事情发生了，罗素提出来的罗素悖论粉碎了数学家的梦想。

关于罗素悖论的一个通俗化版本是：

为什么要第三次数学危机呢？

因为有个很重要的概念： 停机问题 ，停机问题是逻辑数学中可计算性理论中很重要的问题，也是第三次数学危机的解决方案。

停机问题 通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。

有人猜测图灵机模型是图灵在思考 停机问题 而顺带设计出来的，是很有道理的。

图灵在剑桥大学国王学院期间，研究过一本叫做《量子力学的数学基础》的新书，这本书由年轻的匈牙利数学家约翰·冯·诺依曼所著。图灵意识到计算可以用确定性的机械运动来进行表示。其实我们现在的电子计算机虽然不是我们传统意义上的机械，但是CPU内部的电子运动等价于机械运动。

同时图灵也意识到人的思想、意识来自于量子力学中的测不准原理，这不光是微观世界，同时也是这个宇宙本身的规律。所以图灵意识到计算是确定性的，可判定的，而意识是不定的，不可计算的。

在AI人工智能有巨大发展的今天，很多人担心计算机是否会和人一样有意识，其实图灵在80多年前已经考虑过这个问题了。

前面提到，图灵在1950年写过一篇论文《计算机器与智能》，在这篇论文中，图灵测试一词被提出来：

这个测试有多难？目前我们所有的人工智能都没有完成这个测试。最近2018年3月份的谷歌I/O大会上演示的AI产品，据说“部分通过图灵测试”。这个部分到底有多少也未可知。

从人类科技发展的历史上来看，19世纪末到20世纪中期，是第二次工业革命和第三工业革命过渡的时期。第二次工业革命主要电和磁、内燃机的发明和使用，发展到这个时候科学家对世界的认知越来越多，越来越清晰，物理学和数学等自然科学发展迅速。这个时候的数学家发现很多现象可以用数学模型来表示，从物体的运动到星球的运动、从热能到动能的转换、从电到磁的转换等等。那问题来了是否所有的现象都可以用数学模型来表达呢？真是这个问题，让人们对数学很多根本性问题进行思考和研究。

中国有句古话说：乱世出英雄。在图灵的时代，在科学历史上出了很多的科学英雄，包括爱因斯坦、冯诺依曼、图灵、哥德尔等等，一方面是时代背景使然，一方面真是他们的天赋和努力让以信息化为代表的第三次工业革命的进程大大加快了。

从这些巨匠的思考问题，解决问题的方法和认知来看是超出常人的。从对 可计算性理论 的思考，给了我们很大的启示：

**更多有关区块链的技术与思维，可扫码加入我的小密圈。在这里，我陪着你，大家一起研究区块链技术，探讨区块链思维，预测区块链未来，一起做未来前10%的人

**

所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。

在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

在某些模型中，读写头沿着固定的纸带移动。要进行的指令（q1）展示在读写头内。在这种模型中“空白”的纸带是全部为 0 的。有阴影的方格，包括读写头扫描到的空白，标记了 1,1,B 的那些方格，和读写头符号，构成了系统状态。（由 Minsky (1967) p.121 绘制）。

扩展资料：

通用机型

对于任意一个图灵机，因为它的描述是有限的，因此我们总可以用某种方式将其编码为字符串。我们用 <M>表示图灵机 M 的编码。

我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编码<M>，然后模拟 M 的运作，这样的图灵机称为通用图灵机(Universal Turing Machine）。

现代电子计算机其实就是这样一种通用图灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现该程序所描述的算法。但要注意，它只是模拟，因为现实中的计算机的存储都是有限的，所以无法跨越有限状态机的界限。

经典图灵机及其许多变形识别语言的能力都是相同的，正因为如此，图灵机可以作为计算的一般模型。另外，通用图灵机 (可编程图灵机) 是存在的，通用图灵机可以模拟任意一个图灵机，这也是将图灵机作为现代计算机的形式模型的根本原因。

参考资料来源：百度百科—图灵机

问题一：图灵测试是什么 就是测试计算机是否是智能的！图灵（Turing）奖”是美国计算机协会（ACM，Association for puter Machinery）干 1966年设立的，专门奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家。设立的初衷是因为计算机技术的飞速发展，尤其到20世纪60年代，其已成为一个独立的有影响的学科，信息产业亦逐步形成，但在这一产业中却一直没有一项类似“诺贝尔”、“普利策”等的奖项来促进该学科的进一步发展，为了弥补这一缺陷，于是“图灵”奖便应运而生，它被公认为计算机界的“诺贝尔”奖。

“图 灵”为 何 如 此 幸 运

不少人梦寐以求的国际计算机的最高奖项――图灵奖，为何它如此幸运，真是说来话长。

阿兰・图灵（Alan Turing），1912年6月23日出生于英国伦敦，他被认为成二十世纪最著名的数学家之一，谁也没有想到他的名字会和计算机产业挂钩。

20世纪的数学界正在热烈的讨论本世纪最伟大的科学发现之一 ――昆特.哥德尔的不完全性定理，在那以前，数学家们总认为，一个数学问题虽然要找到答案也许会很困难，但理论上总有一个确定的答案，一个数学命题，要么是真的，要么是假的。而哥德尔的不完全定理指出：在一个稍微复杂一点的的数学公理系统中，总存在那样的命题，我们既不能证明它是真的，也不能证明它是假的。数学家们大吃一惊，发现以往大家认为绝对严密的数学中，原来有令人如此不安的不确定性。每个逻辑学家都在苦苦思索，试图为陷入了危机的数学找到一条出路，这些逻辑学家包括当时在剑桥的贝特朗.罗素( Bertrand Russell ) 、阿尔丹雷德.怀特海（Alfred Whitehead）、路德维格.维特斯根坦 ( Ludwig Wittgenstein) 等著名的逻辑学家。这时的图灵正在剑桥求学，他也同样为此问题陷入了困境。

1936年，图灵作出了他一生最重要的科学贡献，他在其著名的论文《论可计算数在判定问题中的应用（On puter numbers with an Application to the Entscheidungs -problem）》一文中，以布尔代数[i]为基础，将逻辑中的任意命题（即可用数学符号）用一种通用的机器来表示和完成，并能按照一定的规则推导出结论。这篇论文被誉为现代计算机原理开山之作,它描述了一种假想的可实现通用计算的机器，后人称之为“图灵机”。

这种假想的机器由一个控制器和一个两端无限长的工作带组成。工作带被划分成一个个大小相同的方格，方格内记载着给定字母表上的符号。控制器带有读写头并且能在工作带上按要求左右移动。随着控制器的移动，其上的读写头可读出方格上的符号，也能改写方格上的符号。这种机器能进行多种运算并可用于证明一些著名的定理。这是最早给出的通用计算机的模型。图灵还从理论上证明了这种假想机的可能性。尽管图灵机当时还只是一纸空文，但其思想奠定了整个现代计算机发展的理论基础。

1945年，图灵被调往英国国家物理研究所工作。他结合自己多年的理论研究和战时制造密码破译机的经验，起草了一份关于研制自动计算机器（ACE：Automatic puter Engine ）的报告，以期实现他曾提出的通用计算机的设计思想。通过长期研究和深入思考，图灵预言，总有一天计算机可通过编程获得能与人类竞争的智能。1950年10月，图灵发表了题为《 机器能思考吗？》的论文，在计算机科学界引起巨大震撼，为人工智能学的创立奠定了基础。同年，图灵花费4万英镑，用了约800个电子管的AC......>>

问题二：什么叫做图灵测验 是图灵提出的一个关于机器人的著名判断原则。 一种测试机器是不是具备人类智能的方法。如果说现在有一台电脑，其运算速度非常快、记亿容量和逻揖单元的数目也超过了人脑，而且还为这台电脑编写了许多智能化的程序，并提供了合适种类的大量数据，使这台电脑能够做一些人性化的事情，如简单地听或说。回答某些问题等。那么，我们是否就能说这台机器具有思维能力了呢?或者说，我们怎样才能判断一台机器是否具存了思维能力呢?

为了检验一台机器是否能合情理地被说成在思想，人工智能的始祖艾伦??图灵提出了一种称作图灵试验的方法。此原则说：被测试的有一个人，另一个是声称自己有人类智力的机器。测试时，测试人与被测试人是分开的，测试人只有通过一些装置（如键盘）向被测试人问一些问题，这些问题随便是什么问题都可以。问过一些问题后，如果测试人能够正确地分出谁是人谁是机器，那机器就没有通过图灵测试，如果测试人没有分出谁是机器谁是人，那这个机器就是有人类智能的。目前还没有一台机器能够通过图灵测试，也就是说，计算机的智力与人类相比还差得远呢。比如自动聊天机器人。

问题三："图灵测试"是什么 意思? 图灵测试（又称“图灵判断”）是图灵提出的一个关于机器人的著名判断原则。 一种测试机器是不是具备人类智能的方法。如果说现在有一台电脑，其运算速度非常快、记亿容量和逻揖单元的数目也超过了人脑，而且还为这台电脑编写了许多智能化的程序，并提供了合适种类的大量数据，使这台电脑能够做一些人性化的事情，如简单地听或说。回答某些问题等。那么，我们是否就能说这台机器具有思维能力了呢?或者说，我们怎样才能判断一台机器是否具存了思维能力呢?

为了检验一台机器是否能合情理地被说成在思想，人工智能的始祖艾伦??图灵提出了一种称作图灵试验的方法。此原则说：被测试的有一个人，另一个是声称自己有人类智力的机器。测试时，测试人与被测试人是分开的，测试人只有通过一些装置（如键盘）向被测试人问一些问题，这些问题随便是什么问题都可以。问过一些问题后，如果测试人能够正确地分出谁是人谁是机器，那机器就没有通过图灵测试，如果测试人没有分出谁是机器谁是人，那这个机器就是有人类智能的。目前还没有一台机器能够通过图灵测试，也就是说，计算机的智力与人类相比还差得远呢。比如自动聊天机器人。

更多详细：baike.baidu/view/94296

问题四：著名的图灵测试,究竟是什么鬼? 图灵测试，如果你感觉这个词比较陌生，我们就先来解释一下：图灵测试是测试人(多人)在与被测试者(一个人和一台机器)隔开的情况下，通过一些装置(如键盘)向被测试者随意提问。问过一些问题后，如果测试人中超过30%的人不能根据答复确认被测试者哪个是人，哪个是机器，那么这台机器就通过了测试，并被认为具有人类智能。

这个看似无厘头的测试，是由现代计算机科学之父英国人阿兰?图灵在60多年前提出的。1950年，阿兰・图灵在那篇名垂青史的论文《计算机械与智力》的开篇说：“我建议大家考虑这个问题：‘机器能思考吗？’”

但是由于我们很难精确地定义思考，所以图灵提出了他所谓的“模仿游戏”：

一场正常的模仿游戏有ABC三人参与，A是男性，B是女性，两人坐在房间里；C是房间外的裁判，他的任务是要判断出这两人谁是男性谁是女性。男方是带着任务来的：他要欺骗裁判，让裁判做出错误的判断。

那么，图灵问：“如果一台机器取代了这个游戏里的男方的地位，会发生什么？这台机器骗过审问者的概率会比人类男女参加时更高吗？这个问题取代了我们原本的问题：‘机器能否思考？’”

这，就是图灵测试的本体。

问题五：著名的图灵测试，究竟是什么鬼 图灵测试，如果你感觉这个词比较陌生，我们就先来解释一下：图灵测试是测试人(多人)在与被测试者(一个人和一台机器)隔开的情况下，通过一些装置(如键盘)向被测试者随意提问。问过一些问题后，如果测试人中超过30%的人不能根据答复确认被测试者哪个是人，哪个是机器，那么这台机器就通过了测试，并被认为具有人类智能。 这个看似无厘头的测试，是由现代计算机科学之父英国人阿兰?图灵在60多年前提出的。1950年，阿兰・图灵在那篇名垂青史的论文《计算机械与智力》的开篇说：“我建议大家考虑这个问题：‘机器能思考吗？’” 但是由于我们很难精确地定义思考，所以图灵提出了他所谓的“模仿游戏”： 一场正常的模仿游戏有ABC三人参与，A是男性，B是女性，两人坐在房间里；C是房间外的裁判，他的任务是要判断出这两人谁是男性谁是女性。男方是带着任务来的：他要欺骗裁判，让裁判做出错误的判断。 那么，图灵问：“如果一台机器取代了这个游戏里的男方的地位，会发生什么？这台机器骗过审问者的概率会比人类男女参加时更高吗？这个问题取代了我们原本的问题：‘机器能否思考？’” 这，就是图灵测试的本体。

问题六：著名的图灵测试，究竟是什么鬼 图灵测试一词来源于计算机科学和密码学的先驱阿兰・麦席森・图灵写于1950年的一篇论文《计算机器与智能》。阿兰・麦席森・图灵1950年设计出这个测试，其内容是，如果电脑能在5分钟内回答由人类测试者提出的一系列问题，且其超过30%的回答让测试者误认为是人类所答，则电脑通过测试。

2014年6月7日是计算机科学之父阿兰・图灵（Alan Turing）逝世60周年纪念日。这一天，在英国皇家学会举行的“2014图灵测试”大会上，聊天程序“尤金・古斯特曼”（Eugene Goostman）首次“通过”了图灵测试。

问题七：一个图灵测试的问题 一上来，先问5个“你好”如果是机器面对重复问题，很可能露出马脚 而后问以下问题： 问： 请给我写出有关“第四号桥”主题的十四行诗。 答：不要问我这道题，我从来不会写诗。 问：34957加70764等于多少？ 答：（停30秒后）105721 问：你会下国际象棋吗？ 答：是的。 问：我在我的K1处有棋子K；你仅在K6处有棋子K，在R1处有棋子R。现在轮到你走，你应该下那步棋？ 答：（停15秒钟后）棋子R走到R8处，将军！ 诸如此类一般人无法回答但机器可以快速反应的问题。 然后问：你是人吗？重复问5遍 实在不行就骂（这样有些不道德，无论对人还是对AI）比如：你是畜生。你妈xx。 机器多半无法理解（最后一条是下下策）

问题八：图灵测试，你知道哪个被测试者是人吗？ 5分 2014年6月7日发生了一件事情：聊天程序“尤金・古斯特曼”在英国皇家学会举行的2014图灵测试大会上冒充一个13岁乌克兰男孩而骗过了33%的评委，从而按照图灵当初的定义，“通过”了图灵测试。

但实际上，在现实生活中，图灵测试的原始形式很少被使用。

不过，我们实际大量使用图灵测试的另外一种简化的形式――校验码。校验码的用处是区分 *** 作者是人还是机器人。仅仅通过一个简单的测试问题：能否从一个图片中看出里面写的是什么文字。

问题九：什么是图灵机和图灵测试 阿兰・麦席森・图灵（Alan Mathison Turing，1912.6.23―1954.6.7），英国数学家、逻辑学家，被称为人工智能之父。 1931年图灵进入剑桥大学国王学院，毕业后到美国普林斯顿大学攻读博士学位，二战爆发后回到剑桥，后曾协助军方破解德国的著名密码系统Enigma，帮助盟军取得了二战的胜利。 阿兰・麦席森・图灵，1912年生于英国伦敦，1954年死于英国的曼彻斯特，他是计算机逻辑的奠基者，许多人工智能的重要方法也源自于这位伟大的科学家。他对计算机的重要贡献在于他提出的有限状态自动机也就是图灵机的概念，对于人工智能，它提出了重要的衡量标准“图灵测试”，如果有机器能够通过图灵测试，那他就是一个完全意义上的智能机，和人没有区别了。他杰出的贡献使他成为计算机界的第一人，现在人们为了纪念这位伟大的科学家将计算机界的最高奖定名为“图灵奖”。上中学时，他在科学方面的才能就已经显示出来，这种才能仅仅限于非文科的学科上，他的导师希望这位聪明的孩子也能够在历史和文学上有所成就，但是都没有太大的建树。少年图灵感兴趣的是数学等学科。在加拿大他开始了他的职业数学生涯，在大学期间这位学生似乎对前人现成的理论并不感兴趣，什么东西都要自己来一次。大学毕业后，他前往美国普林斯顿大学也正是在那里，他制造出了以后称之为图灵机的东西。图灵机被公认为现代计算机的原型，这台机器可以读入一系列的零和一，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。在图灵看来，这台机器只用保留一些最简单的指令，一个复杂的工作只用把它分解为这几个最简单的 *** 作就可以实现了，在当时他能够具有这样的思想确实是很了不起的。他相信有一个算法可以解决大部分问题，而困难的部分则是如何确定最简单的指令集，怎么样的指令集才是最少的，而且又能顶用，还有一个难点是如何将复杂问题分解为这些指令的问题。 1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。“图灵机”与“冯・诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。

---