点击查看【bilibili】

图灵

• 阿兰·图灵——计算机科学之父
• 1921 年出生在英国伦敦
• 1935 年，图灵开始解决德国数学家 大卫·希尔伯特 提出的 可判定性问题
• 二战期间，图灵和同事在布莱切利园努力破解德军英格玛加密机。解密得到的德国情报，为盟军赢得了很多优势
• 战后，图灵回到学术界，为许多早期计算机工作做出贡献，比如曼彻斯特 1 号，一个早期有影响力的存储程序计算机
• 1952 年，调查他家的入室盗窃案时，向当局暴露了他的性取向，被起诉 “行为严重不检点”，图灵被定罪，面临 2 个选择：1. 入狱 2. 接受激素来压制性欲。他选了后者，部分原因是为了继续学术工作。但药物改变了他的情绪和性格，图灵于1954年服毒自尽，年仅41岁。
• 图灵奖——计算机领域的最高奖项

可判定性问题 decision problem

定义：是否存在一种算法，输入正式逻辑语句，输出准确的”是”或”否”答案？eg. 如果这样的算法存在，可以回答比诸如”是否有一个数大于所有数”这样的问题。
答案：不存在这样的算法
意义：计算机的能力有极限。无论有多少时间或内存，有些问题是计算机无法解决的。——丘奇-图灵论题

证明 1：Lambda算子，阿隆佐·丘奇

• 美国数学家 阿隆佐·丘奇 于 1935 年，开发了一个叫”Lambda 算子”的数学表达系统，证明了这样的算法不存在。
• 该证明方法使用的数学技巧难以理解和使用

证明 2：图灵机，图灵

• 阿兰·图灵为解决可判定问题，提出了一种假象的计算机，现在称为图灵机。
• 图灵机提供了简单又强大的数学计算模型，虽然用的数学方法不同，但是图灵机的计算能力和 Lambda 算子一样
• 由于图灵机更简单，在新兴的计算机领域更受欢迎

图灵机的组成

• 一条无限长的纸带：纸带被分为一个个格子，每个格子上包含一个来自有限字母表的字符
• 一个读写头：可以在纸带上左右移动，并能读写纸带上的符号
• 一组控制规则：根据图灵机当前的状态 + 当前读写头所指的符号，决定图灵机下一步的动作（可能是在纸带写入一个符号；或改变状态寄存器的值，令图灵机进入新状态；或把读写头移动一格；或是以上动作的组合）
• 一个状态寄存器：保存图灵机当前所处的状态。图灵机所有可能的状态数目是有限的，且有一个特殊的停机状态

图灵完备

• 只要有足够的规则，状态和纸带，图灵机可以创造任何东西，可以实现任何计算
• 图灵机是很强大的计算模型。就可计算和不可计算而言，没有计算机比图灵机更强大。
• 和图灵机一样强大的，叫 “图灵完备“

停机问题——用图灵机回答可判定性问题

定义：给定图灵机描述和输入纸带，是否有算法可以确定机器会永远算下去还是到某一点会停机？
答案：停机问题是无法解决的
证明：

• 假设有一台假想图灵机 H，输入：问题的描述 + 纸带的数据；输出：Yes 代表会停机，No 代表不会停机
• 如果有一个程序，图灵机 H 无法判断是否会停机，则说明停机问题无法解决
• 为了找到这样的程序，新设定另一个图灵机 H’：如果图灵机 H 说程序会停机（即输出 Yes），新图灵机 H’ 就输出 Yes，但永远运行不停机；如果图灵机 H 输出 No，则让新图灵机输出 No，然后停机。新机器 H’ 实质上是一台和 H 输出相反的机器，如果程序不停机，就停机；如果程序停机，就永远运行下去。
• 在图灵机 H’ 前面加一个分离器，使机器只接收一个输入，这个输入既是程序，也是输入。把这台新机器叫作 异魔。
• 把 异魔 的描述，作为图灵机异魔本身的输入，这意味着在问图灵机 H，当异魔的输入是自己时，异魔会否停机？
• 但如果 H 说异魔会停机，那么异魔会进入无限循环，因此不会停机；如果 H 说异魔不会停机，那么异魔会输出 No 然后停机。
• 因此图灵机 H 不能正确判定 停机问题，因为没有答案，这是一个悖论

意义：由于图灵证明了图灵机可以实现任何计算（图灵完备），而图灵机无法回答停机问题，因此停机问题证明了不是所有问题都能用计算解决。

图灵测试

定义：1950 年，图灵设想了未来的计算机拥有和人类一样的智力，或至少难以区分。图灵提出如果计算机能欺骗人类相信它是人类，才算是智能。这成了智能测试的基础，如今叫”图灵测试”
规则：如果有一个人和一个计算机，你和他们沟通，但是你分不出哪个是人类，哪个是计算机，那么计算机就通过了图灵测试。
应用：验证码（全称”公开全自动图灵测试”），用于区分计算机和人类，防止机器人发垃圾信息等