图灵机与图灵测试

图灵测试

  1. 图灵测试发表于图灵的一篇重磅论文《ComputingMachinery and Intelligence （计算机器与智能）》，也正是这篇论文奠定了图灵作为人工智能之父的地位，这篇论文着重回答一个问题：机器能思考吗？<br />    图灵测试（英语：Turing test，又称“图灵判断”），是阿兰·图灵于1950年提出的一个关于判断机器是否能够思考的著名试验，测试某机器是否能表现出与人等价或无法区分的智能。如果一个人（代号C）使用测试对象皆理解的语言去询问两个他不能看见的对象任意一串问题。对象为：一个是正常思维的人（代号B）、一个是机器（代号A）。进行多次测试后，如果机器A让平均每个参与者做出超过30%的误判，那么这台机器就通过了测试，并被认为具有人类智能。

发展

  1. 关于这个测试很有一点行为主义的特点，它把计算机当做一个黑盒看待，我们不了解其中的过程，但是通过表现来判断是否具备人类一般的智能。按照这个标准，其实已经有很多种不同程度图灵测试已经被搞定。

1997年，CMU和IBM联合研发的国际象棋计算机程序深蓝下赢了世界冠军。

2014年，聊天计算机程序尤金·古斯特曼成功让人类相信他是一个13岁的男孩。

2015年，Science杂志封面文章报道一个AI系统可以根据未见过的文字字符，书写同样的字符并创造相似的字符。

2016年，围棋AlphaGo击败世界冠军。

  1. 从最早的图灵测试角度来说，计算机的“智能”在不断提高，不论是通过什么样的方式，从专家系统、遗传算法、演化计算、深度学习到强化学习等等，但是关于图灵测试也有很多种不同的声音和发展。<br />    1989年，Harnad提出完全图灵测试（Total Turing Test， T3），即在原始图灵测试的基础上增加了视觉、听觉、触觉、味觉等等不同维度的测试，所有的感知和认知能力达到了人的标准才算是通过图灵测试，这当然是进一步的发展，但是图灵当年提出的测试大概是基于一种可行的方式来考虑的一种形式化定义，所以才以语言为主。<br />    另外一个比较有意思的是中文房间思想实验，这个实验的意思是如果一个只会英文的人被关在封闭屋子里，即使他使用中文字典对递给他的纸条给出了合理的回答，也只能让屋外的人误以为他会中文，而并不是真的会中文。这个实验主要是用来推翻人工智能中所谓计算机程序可以像人一样思考的观点。

图灵机

图灵机（Turing Machine）是图灵在1936年发表的 “On Computable Numbers, with an Application to the Entscheidungsproblem”（《论可计算数及其在判定性问题上的应用》）中提出的数学模型。既然是数学模型，它就并非一个实体概念，而是架空的一个想法。在文章中图灵描述了它是什么，并且证明了，只要图灵机可以被实现，就可以用来解决任何可计算问题。
图灵机的结构为：

  • 一条无限长的纸袋（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个字符（symbol）。
  • 一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符（包括特殊的空白字符）。
  • 一个读写头（head），可理解为指向其中的一个格子的指针。它可以读取，擦除，写入当前格子的内容，此外也可以每次向左或右移动一个格子；
  • 一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行或终止）。当这个状态从运行变成终止，则运算结束，机器停机并交回控制权。
  • 一个有限的指令集（instructions table），它记录着读写头在不同情况下应该执行的行为。可以想象为读写头对应的操作指南。比如”当前处于编号53的格子，看到其中内容为0，则擦除，改写为1，并向右移动一格，下一状态为运行”。指令集就对应着计算模型，即函数。

在计算开始前，纸带可以是完全空白的，也可以预先写入字符。运算开始时，读写头从某一位置开始，严格按照此刻的配置（configuration），即：

  • 当前所处位置；
  • 当前格子内容；

  • 一步步对照着指令集去进行操作，直到状态变成停止，运算结束。而纸带留下的字符序列作为输出，由人为解码为自然语言。

    可计算问题

    图灵在图灵机思想中证明了，假设上述所说的功能都能以某种物理形式实现，那么任何可计算问题都可以被解决。
    在计算机领域，我们研究的一切问题都是计算问题，计算问题泛指一切与计算相关的问题。比如：

  • 给定一个正整数n，判断它是否是质数；

  • 给定一个0-1序列，把它们按位取反；
  • 给定一个字符串，判断某个字符是否存在，以及查找存在的位置；
  • 给定一个蕴含逻辑的命题，求它的逆否命题；

相反，非计算问题为：

  • 今晚看什么书；
  • 你为什么叫白景屹。

计算问题有的可解决，有的不可解决。从而引出计算问题的可计算性（computability），它可以被理解为”是否存在一个算法，能解决在任何输入下的此计算问题”。比如上面的问题”给定一个正整数，判断它是否是质数”。我们确实可以找到一个算法判断一个数是不是质数，比如从2遍历到n − 1 n-1n−1，看n nn是否可以整除它，因此，这个问题是可计算的。

不可计算-图灵停机问题

对于不可计算的计算问题，比如停机问题（Halting Problem）：把一段即将运行的代码作为字符串序列输入到该判断程序中，判断程序直接通过某种算法分析被输入程序的结构，并给出预报结果：该程序可以或不可以在有限时间内完成计算停止。这就是有名的停机判定问题。
很明显，这个计算问题不可计算，我们不能找到一个算法在任何情况下都判断它。
回到可计算问题，换言之，对于一个问题，对于任意输入，只要人类可以保证算出结果（不管花费多久），则图灵机也可以保证算出结果（不管花费多久）。

判定问题

判定问题是无穷多个同类个别问题的总称。例如，2是不是素数？6是不是素数？这些都是个别问题，把这类个别问题概括起来，就得到一个判定问题：任意给定的正整数是不是素数？这里的正整数集合称为该判定问题的域，给定域中的一个元素，判定问题就对应一个个别问题。
对于一个判定问题，如果能够编出一个程序，以域中任意元素作为输入，执行该程序就能给出相应的个别问题的答案，就称该判定问题为可判定的。
可判断问题是可计算问题的子集。

图灵完备

图灵完备性（Turing Completeness）是针对一套数据操作规则而言的概念。数据操作规则可以是一门编程语言，也可以是计算机里具体实现了的指令集。当这套规则可以实现图灵机模型里的全部功能时，就称它具有图灵完备性。
如果是图灵完备的，它（计算机设备）有能力执行条件跳转（if、while、goto语句）以及改变内存数据。 如果某个东西展现出了图灵完备，它就有能力表现出可以模拟原始计算机，而即使最简单的计算机也能模拟出最复杂的计算机。
当下的主流编程语言（C++，Java，Python）都是图灵完备的语言。回到语言的底层，一切编程语言实现的功能完全一样，本质上就是一个图灵机。
简单来说，一切可计算的问题都能计算，这样的虚拟机或者编程语言就叫图灵完备的。图灵完备可能因为陷入死循环而导致程序崩溃。与图灵完备相反的是图灵不完备，图灵不完备应该是不允许或限制循环，可以保证每段程序都不会死循环，都有运行完的时候。

Brainfuck（BF）编程语言

Brainfuck（BF）是一种极小化的程序语言，它是由Urban Müller在1993年创造的。它一共只包含8个有效字符，每个有效字符就是一条指令。

| 字符 | 含义 | | —- | —- |

| > | 指针向右移动1格 |

| < | 指针向左移动1格 |

| + | 使指针当前格中的数值加1 |

| - | 使指针当前格中的数值减1 |

| . | 把当前格中的数值按ASCII表输出到终端 |

| , | 从终端接受1byte数据，存储其ASCII对应的数值到当前格 |

| [ | 当指针当前值为0时，程序跳转至与之对应的 ] 之后；否则程序正常执行 |

| ] | 程序跳转回与之对应的 [ 处 |

这个语言是图灵完备的。
BF的工作机制与图灵机高度一致。首先存储数据的方式是一个不限长的一维整数数组，里面的数值全部初始化为0。此外，还有一个数据指针，每一时刻都指向数组的某一任意元素。指针可以向左或向右移动，也可以读取或修改当前值。

邱奇-图灵理论

该论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言的程序，所以该论题和以下说法等价：常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真，也被称为邱奇论题或邱奇猜想和图灵论题。

通过图灵测试意味着什么

图灵测试本质上不是智能测试，是替代测试，是机器人能不能替代人的工作。
通过图灵测试，可以代表机器在某一领域能够完成人类的工作。也代表着图灵测试该升级了。

分子计算机

查到的信息很少，看起来似乎是专门算DNA的。
按理说满足图灵机假设就是图灵机，计算机本身肯定不是图灵机，需要一套指令集（语言）使之成为图灵机。
##　尤金·古斯特曼
2014年6月7日是计算机科学之父阿兰·图灵（Alan Turing）逝世60周年纪念日。这一天，在英国皇家学会举行的“2014图灵测试”大会上，聊天程序“尤金·古斯特曼”（Eugene Goostman）首次“通过”了图灵测试。
尤金最初在2001年由弗拉基米尔·维西罗夫（Vladimir Veselov）、谢尔盖·乌拉森（Sergey Ulasen）和尤金·杰姆琴科（Eugene Demchenko）在俄罗斯圣彼得堡共同开发，它模拟的是一个13岁乌克兰男孩。“尤金诞生于2001年。”维西罗夫介绍道：“我们当时的主要想法是，尤金能够声称自己知道所有事情，但考虑到他的年龄，他不知道所有事情也是很合理的。”“我们花了很多时间去使他具备可信的人格。今年，我们改进了尤金的‘对话控制器’，使得跟只会回答问题的程序比起来，尤金在对话中更加像人类。”
尤金的设计思路并不是“一台在智力行为上表现得和人无法区分”的机器，而是一台“能够在5分钟长度对话内尽可能骗过人类”的机器。
该程序冒充的是一个来自乌克兰、英语非母语的13岁小孩，这实际上不完全公平。
图灵机与图灵测试 - 图1
模拟这样一个乌克兰小孩是“公平”的吗？其实两年前Abstrusegoose就嘲笑过这种思路。