人工智能标准是否通过图灵测试，图灵测试到人工智能
人工智能标准是否通过图灵测试，图灵测试到人工智能▲《模仿游戏》中破解密码机的图灵电影《模仿游戏》详细地介绍了他的生平，据历史学家估计，图灵因为破解德国的恩尼格玛密码机（Enigma Machine）而拯救了1400万英国人。在破解恩尼格玛密码机的时候，图灵沉浸在密码学之中。▲美剧《西部世界》第二季剧照图灵的论文《可计算数及其在可判定性问题上的应用》(《On Computable Numbers，with an Application to the Entscheidungsproblem》）发表于1936年，在这篇论文中，他构造了一个图灵机来计算可计算数，证明希尔伯特提出的通用可判定性方法不存在。图灵机的具体构造可以参考图灵的论文，这篇论文阅读起来非常晦涩。但如果要理解他的构思或者灵感，那么阅读他的论文是最直接的方式。图灵不是我们同时代的人，要推测图灵的构造灵感非常困难，但是读者可以像作者这样通过阅读到的文字和听到的故事去隔空对话这位伟
导读：美国电视剧《西部世界》第二季的第一集一经播出就引起热议。一时间，人和人工智能这个话题又重新被辩论。由于程序功能越来越强大，人们开始担心：“人工智能程序会不会全面取代人类？”
人工智能是否会取代人类这个问题，实际上涉及对于认知的无穷边界的考量：图灵机能表达的带有人工智能模型的可计算数（程序）无穷大，人的思考过程也无穷大，哪个无穷大更大？
作者：冯雷 姚延栋 高小明 杨瑜
如需转载请联系华章科技
▲美剧《西部世界》第二季剧照
01 图灵机和可计算数图灵的论文《可计算数及其在可判定性问题上的应用》(《On Computable Numbers，with an Application to the Entscheidungsproblem》）发表于1936年，在这篇论文中，他构造了一个图灵机来计算可计算数，证明希尔伯特提出的通用可判定性方法不存在。
图灵机的具体构造可以参考图灵的论文，这篇论文阅读起来非常晦涩。但如果要理解他的构思或者灵感，那么阅读他的论文是最直接的方式。图灵不是我们同时代的人，要推测图灵的构造灵感非常困难，但是读者可以像作者这样通过阅读到的文字和听到的故事去隔空对话这位伟人，推敲他的灵感来源。
电影《模仿游戏》详细地介绍了他的生平，据历史学家估计，图灵因为破解德国的恩尼格玛密码机（Enigma Machine）而拯救了1400万英国人。在破解恩尼格玛密码机的时候，图灵沉浸在密码学之中。
▲《模仿游戏》中破解密码机的图灵
密码学就是将一组数字按照某种规则让机器变成另外一组数字。接收方可以根据一个反向规则让机器将其变成原文。举个简单的例子，10多年前为了让我的信件不被家长偷看，我曾构造过一个简单的加密方法：把所有的英文字符换成英文字符表的下一个字符，接收者把每个英文字符换成字符表的前一个字符即可以重构原文。
举一个更加复杂的例子，计算机科学一般用两位数字01，02，…26来表示英文字母A，B，…Z，用00表示空格。这样，一个关于聚会的时间和地点的文字消息就可以转化为一串数字。接收者收到这串数字后，把每两位数字转换成对应的字母，就可以还原出文字消息了。
把一个句子通过一个机器逻辑映射成一个数字非常有意思，例如ICU可以映射成090321。图灵在破解恩尼格玛密码机的时候可能深谙其中的乐趣。
《Cloud Foundry：从数字化战略到实现》一书的第1章曾回顾香农信息论为代表的数字世界的崛起。我们谈到了冯·诺伊曼为何建议香农在他的信息论中采用物理学中熵的概念，但是我们并没有仔细讨论后面的哲学，这里可以再继续深入讨论一下。
物理学家和数学家都隐隐约约感觉到物质和能量背后存在的信息（数字）世界，那么我们能否用数字世界来描述物理世界？香农和奈奎斯特独创了信息论。在他们两位开天辟地的工作成果下，我们可以通过一个机器把图像、音频编码成一组数字。
于是，我们今天可以用二进制编辑器打开任何一台计算机上的图片或者音频，其实它们只是一串0和1编码。这些0和1的字符串对应了一个数的二进制表示，所以它还是一个数。
图灵在从事密码破译工作的时候，有机会去美国的贝尔实验室协调英美两国的合作。他在贝尔实验室遇到了两位大师（可见人生结交高质量的朋友多么重要）。
作者猜测图灵从两位大师制作的编解码机器中大受启发，将他对世界万物都是数的信念往前推进了一步：如果说人的五官能够感受到的世间万物都可以用机器转换成数字来表示，那么人的思考过程是否也能用机器转换成数字来表示？
为帮助读者理解图灵的这个构思，可以用iPhone手机上的Siri语音助手来类比。Siri是一个能思考和分析的程序，如果你用一个二进制编辑器打开它，它也是一个用二进制0和1表示的数。但是Siri对应成iPhone这个机器（本质上就是一个图灵机）上的一个数字后，在机器上的运作就能起到人工智能的效果。
通过这个例子，读者也可以看到数字化是人类前进的一个新方向，相比人类在工程和物理领域的几千年的研究，数字世界的探讨从图灵等人在20世纪40年代开辟这个话题算起，到今天才经历了几十年。
图灵的论文详细介绍了图灵机的构造和定义在图灵机上的可计算数。如果读者觉得论文太难懂，可以参考《图灵的秘密》一书，该书做了非常详细的注解。
图灵用极其简单的抽象机器来模拟一个数学工作者。一个数学工作者脑子里面有个思考状态（上下文），他在纸上扫描到下一个字符的时候脑子里会产生一个状态，然后可能在纸上移动位置写下一个符号，不断重复这个过程。图灵机的构造就是这么简单，图1-12就是图灵机的一个大致描述。
▲图1-12 图灵机的大致表示，来源：维基百科
图灵机在无限长的纸带上移动，每次移动读取一个符号（数字用二进制表示），然后图灵机的内部状态进行改变，并决定图灵机下一个移动的位置。图灵在论文中给出的一个例子是打印一个分数1/3。
这个图灵机很简单：打印1个0往右移动一格，然后再往后移动一格，留出一个空格做可能的符号标记，然后再打印一个1并往右移动一格，之后，图灵机再往右移动一格从而留出一个空格作为可能的符号标记。之后以此类推。以上过程可以用表1-1所示的状态切换表来表示。
表1-1 可计数1/3的图灵机表示：
写过程序的读者会发现，这有非常经典的汇编程序的味道。机器打印出来的纸带如图1-13所示（早期的软件工程师应该有使用穿孔纸带的经历）。
▲图1-13 可计算数1/3的图灵机纸带
把这个纸带标记为小数点后的二进制数字（0.010101…），读者可以用级数求和，其结果等价于1/3。
读者可能有两个疑问：
- 二进制表示对数字计算机的产生有极大帮助，那么图灵是如何突发奇想地想到用二进制来表示图灵机？
- 图灵为何只讨论0到1之间的实数？这两个问题的确非常重要，因为这涉及我们对人和机器之间的互补和竞争关系的讨论：机器到底是否会取代人？我们在下一节中再展开讨论，这里暂时聚焦在图灵机上。
这个图灵机只做一件事情，就是表示一个可计算数1/3。为了达到举一反三的目的，我们可以把表1-1中的b和k的顺序更换一下，从而创造另外一个计算2/3的图灵机。表格如表1-2所示。
表1-2 可计数2/3的图灵机表示：
它的纸带如图1-14所示，其中1和0的顺序与数1/3纸带中1和0的顺序正好相反。
▲图1-14 可计算数2/3的图灵机纸带
我们现在了解了图灵机的定义和运行机制，能够用图灵机计算的数叫作可计算数。目前，得到了两个表格表示的不同图灵机，分别用来计算可计算数1/3和2/3。写过程序的人可以把这两个表当作两个程序，以方便理解后面的内容。
如果图灵只是用假想的机器来编码可计算数，那与香农和奈奎斯特的成果没有任何可比性，因为两位大师已经用机器把图像、声音等信号用机器编码成数字。但是图灵往前走了一步，他不仅把数字编码成特定的图灵机，还把特定的图灵机编码成通用的图灵机。
读者可简单地理解为图灵创造了一个通用的机器，在这个机器里面，上面的两个图灵机(可以简单理解成上面的表1-1和表1-2）也可以编码成两个可计算数（程序），这意味着（理论上）通用计算机的诞生。对于数学领域的人而言，世界上已经存在计算机了。
把表1-1表示的计算1/3的程序和表1-2表示的计算2/3的程序输入到这个通用计算机，就会输出对应的纸带：图1-13和图1-14。香农和奈奎斯特的编解码机器也可以在这台通用图灵机上运行。
用今天的事物来类比，就是把微信程序、地图程序、Siri程序输入到iPhone这个通用计算机上执行。普遍被认为具有人工智能的Siri，从这个意义上说只是图灵机上的一个可计算数而已。对图灵的这个通用计算机的构造有兴趣的读者可以阅读他的论文或者有注解的《图灵的秘密》一书。
提出通用计算机以后，图灵就开始为他假想出来的计算机编写程序。图灵当然也关心如何在物理世界创造出一台物理计算机，但是这需要获得大量物理世界的资源、聚集团队和持续执行才能实现。最终，冯·诺依曼实现了这个目标，但作者不认为第一台可存储程序计算机是冯·诺依曼一个人创造的，而应该是他和他的团队一起创造出来的。
数字是数，信号是数，程序也是数，世界万物都是数。自从第一台假想计算机和第一台物理计算机诞生以后，再加上香农和奈奎斯特把物理世界的信号编码成数字，数字技术开始蓬勃发展，进入了大型机、PC机和云计算机时代。
一批数学、物理工作者后来转变成为能编写程序的软件开发人员。从计算机发明到现在短短六七十年，开发人员编写出各种各样的程序，不少程序带有人工智能或机器学习的数学模型，涉及虚拟现实、无人驾驶、人脸识别、语音助理等领域。
由于程序功能越来越强大，人们开始担心：“人工智能程序会不会全面取代人类？”
人工智能是否会取代人类这个问题，实际上涉及对于认知的无穷边界的考量：图灵机能表达的带有人工智能模型的可计算数（程序）无穷大，人的思考过程也无穷大，哪个无穷大更大？面对这个问题，大部分人会困惑“两个无穷大的数还能区分大小？”所以，这里有必要重新理解一下数。
数有两个让人最头疼的问题：无穷问题和无理问题。据说知名的数学家、集合论的创始人康托尔（Cantor）就因为沉溺于数的无穷问题而得了躁狂型抑郁症。作者无意将这种痛苦带给读者，但是对于思考AI是否要取代人的读者，这个是绕不过去的坎。
自然数集、有理数集合和无理数集合在有限情况下非常容易理解，但是在无限的情况下很多属性会发生变化。我们看下面两个集合（N为自然数）：
- 自然数集合A{1，2，3，4，...，N}
- 偶数集合B{2，4，，...，2N}
在N是个有限的数的情况下，集合A的元素的元素数（叫作基）是集合B的基的两倍。但是，当N无穷大的时候，两个集合的势（无限集合的基）就相等了。为什么呢？从偶数集中拿出一个2，从自然数集合中拿出1，再从偶数集中拿出4，从自然数集中拿出2，如此进行下去，可以用无穷自然数集1对1数的无穷集合叫作“可数”。
一个无穷集合如果是可数的，那么就说它们的基和自然数集A相等。读者可以尝试证明一下无穷有理数集合也是可数的，只要把集合元素顺序的写法写得可数。具体做法就是把分子分母之和等于1，2，3，4的自然数一一列举如下：
- 有理数集合C{1/1，1/2，2/1，1/3，2/2，3/1…}
读者可能兴致勃勃地把这个可数的数的证明推广到实数集，但是康托尔用对角论证法证明了实数集合是不可数的。康托尔的证明激发了图灵只讨论[0，1]区间的二进制形式的数，而使用二进制对实际计算机的发明产生极大的帮助。
这里简单介绍一下这个证明方法，具体证明方法可以参考维基百科。假设我们数完了所有的[0，1]之间的实数r1，r2，举个象征性的排列例子如下（来自维基百科）：
r1 = 0 . 5 1 0 5 1 1 0 …
r2 = 0 . 4 1 3 2 0 4 3 …
r3 = 0 . 8 2 4 5 0 2 6 …
r4 = 0 . 2 3 3 0 1 2 6 …
r5 = 0 . 4 1 0 7 2 4 6 …
r6 = 0 . 9 9 3 7 8 3 8 …
r7 = 0 . 0 1 0 5 1 3 5 …
我们现在把所有无理数数完了。我们创造一个新的超越数，它的第k位取自上面数字rk的小数点后的第k个位并加1，如果遇到9变成0，所以这个新数就是0.6251346...它和上述的数都不一样，所以它不在这个可数数列表中，可得出实数集是不可数的结论。
这个证明带来另外一个非常有意思的结论：同样是无穷，实数集合的无穷要比自然数集合的无穷更大。如果把自然数集合的势记为aleph-0（康托尔把它叫作超限数），因为康托尔想计算实数集的势，于是他引入了[0，1]区间的二进制形式的数和集合论。他尝试用小数点后无限位二进制数的0和1的交替的记法去对应实数里面的元素。为帮助读者理解，列举几个数如下：
0.0000000…
0.1000000…
0.0100000…
0.1100000…
0.0010000…
0.1010000…
0.0110000…
0.1110000…
如果我们把1当作√一样的标记，学过子集的读者肯定觉得这个标记和列举含3个元素{0，1，2}集合的所有子集的记法很相似：
将这个二进制小数列表无穷列举下去，那么对应的子集表也可以无穷列举下去。这些二进制形式的小数对应所有［0 1］区间的实数，而表格第五列中子集的列表也等同于无穷自然集的子集。因为一个含有N个元素（基为N）的集合的子集数目为2^N，无穷自然数子集的数目就是2^aleph0，这个数也就是实数集合的势。
康托尔猜测2^aleph0就是下一个超限数aleph1，中间不存在其他超限数，也叫连续统假设（这是希尔伯特提出的23个问题中的第一个问题）。
因为康托尔的工作，我们知道了实数集与可数数集同样是无穷大，但是实数集更大。图灵发明了图灵机和定义在其上的可计算数，所以图灵自然要考虑：“可计算数对应了可数数还是整个实数集？”
遗憾的是，图灵证明了可计算数虽然包含无理数中的代数数（例如根号2这样的代数方程的解）和部分超越数（例如π和e），但它是可数的。可数数的势aleph0远小于实数集合的势aleph1 = 2^aleph0。而世间万物都是数，且大部分数都是实数，实数中的大部分超越数都无法用图灵机表示。
这意味着什么？第一个选择是我们拒绝承认不可计算的实数的存在，这就等同于我们构造了不存在的数；第二个选择是我们承认它们的存在，图灵机无法表达一个随机生成的无理数。那么人脑是否有个思考过程能对应一个无限、无理的数？图灵和邱奇恰恰认为人脑不能完成这个工作，这就是他们提出的邱奇-图灵论题。
这个论题可以简单地表述为：“凡是人类能够执行的算法，图灵机也可以。”用其等价的逆反命题来说是：“如果算法过程是图灵机不能解的，人类也不能解。”到这里，读者可以清晰地知道，这个是论题，它并不能被证明。
人工智能是否能够取代人，本质上也依赖于这个论题是否正确。在作者眼里，这个论题就像几何的五个公理或者物理学里面的能量守恒定律一样，是我们公理化的认知边界。
到这里，读者已经看到图灵机上能表达的可计算数是无穷的，但是有个更大的实数无穷是图灵机无法表达的。这两个极限的差别表现出图灵机的解决问题的范畴是有局限的。
举个例子来说，我们不能发明一个程序检查另外一个程序的错误。一个错误的程序会使图灵机进入失控状态，计算过程会进入到一个表格里面不存在的状态（m-config）。
回到希尔伯特可判定性的讨论，图灵试图构造一个图灵机，从希尔伯特的《数学原理》中的几个公理和规则出发，让图灵机列举出所有可证明的公式。但是，图灵证明了这样的图灵机不存在。根据邱奇-图灵论题，人类数学工作者也找不到一个思考过程判断一个公式的可证明性。
图灵接下来讨论了一系列人和机器智能的问题。在1950年的Mind杂志上，图灵就人工智能这个话题发表了另外一篇论文“Computing Machinery and Intelligence”。在这篇论文中，他提出了“机器能够思考吗？”这个问题。他认为思考和机器（读者可以认为AI）的定义过于模糊，为此给出了知名的图灵测试来回答这个问题。
在图灵测试中，被测试者（人）在一个黑暗的屋子里面与一台机器或一个人进行对话（那个年代采用文本方式，现在则可以升级到语音方式），若被测试者无法区分对话的是人还是机器，则可以称机器通过了图灵测试。这也是电影《机械姬》的故事情节的基础。
▲《机械姬》剧照
我们如何看待邱奇-图灵论题决定了我们怎么看待人和AI之间的关系。为帮助读者理解邱奇-图灵论题，作者尝试用通俗易懂的语言来表述。图灵机在某个状态下观察一个符号，然后切换到下一个状态，这个行为和我们人类数学工作者几乎一样。差别在于，邱奇和图灵认为机器的状态是有限的，类似于我们构建的表1-1的行状态是有限的。
图灵认为，如果人脑有无限的状态，必然因为有些状态无限接近而造成混乱。但是作者认为“人的思想可以支持一个无穷状态”，因为我们对人的意识理解得并不清楚，证明数学不完备性的数学家哥德尔也表示了类似的观点。
但是，机器智能或者人工智能的产生，极大地解放了人类在可计算数范围内求解问题的速度。机器智能的诞生似乎加速了人类对于数字世界中未知领域的探索。只是，我们对于新生事物的直觉反应总是恐惧，对机器智能的兴起也有类似的反应。
图灵认为人类在上个世纪末不再会抵触和反对机器思考。但是到了今天，我们还是因为不了解或无法掌控机器智能而感到恐惧或不安，过度的恐惧和不安又有可能限制我们充分利用机器智能的长处，进而错过对于机器智能以外的世界的探索。
我们今天感受到的数字世界，存在一定的公理和论题上的边界。在这个边界里面也有黑洞，原因是不完备性；我们没有一条快速路径来鉴别黑洞，是因为不可判定性。
但是，如果你和作者一样认为人的意识格局相比图灵机具有无限性，那么应该持续地去拓展这个边界。在拓展或者重构这个边界的时候，有些黑洞或许会消失，或许可以找到一条路径鉴别黑洞。就像希尔伯特说的：“我们必须知道；我们必将知道。”
本文摘编自《Greenplum：从大数据战略到实现》，经出版方授权发布。
延伸阅读《Greenplum：从大数据战略到实现》
推荐语：本书由Greenplum核心研发团队精心编写，融入了团队十余年来对云计算、大数据和人工智能驱动的企业数字化转型、先进技术发展趋势以及产品研发的深刻思考，对Greenplum这款快速成长的开源大数据平台进行了全方位深度解读，无论是企业决策者，还是大数据相关的技术人员，都能从本书中获益。
