Alan Turing: Crash Course Computer Science #15

Summary

本视频介绍了计算机科学之父艾伦·图灵的生平和成就。图灵在剑桥大学攻读硕士期间，提出了解决德国数学家大卫·希尔伯特提出的“决策问题”的方法，即是否存在一个算法，能够对形式逻辑中的陈述给出始终准确的“是”或“否”答案。图灵提出了一种理论计算模型——图灵机，它虽然简单，但功能强大，与λ演算在计算能力上等价。图灵机通过无限长的纸带、读写头和一系列规则来模拟任何计算过程。图灵还探讨了著名的“停机问题”，证明了不存在一个算法能够确定任意程序是否会无限运行。在第二次世界大战中，图灵设计了一种名为“Bombe”的电子计算机，帮助破解了德国的恩尼格玛密码机，对战争胜利起到了关键作用。战后，图灵对人工智能领域做出了贡献，提出了著名的“图灵测试”。然而，由于当时对同性恋的法律迫害，图灵的生活悲剧性地结束。图灵的贡献被广泛认可，图灵奖就是以他的名字命名的计算机科学领域的最高荣誉。

Takeaways

• 👨‍💻 艾伦·图灵被誉为计算机科学之父，对现代计算理论有着深远的影响。
• 🧮 图灵在剑桥大学攻读硕士期间，首次接触了我们现在称之为计算机科学的问题，特别是希尔伯特的“决策问题”。
• ✅ 阿隆佐·丘奇和图灵分别独立提出了λ演算和图灵机，两者在计算能力上是等价的，但图灵机因其简单性更受欢迎。
• 📜 图灵机是一个理论计算模型，由无限长的纸带、读写头、状态寄存器和规则组成。
• 🔢 图灵机通过简单的规则可以模拟任何计算过程，证明了理论上的可能性，即所谓的“通用计算机”。
• 🔍 图灵在解决希尔伯特的决策问题时，提出了停机问题，并通过逻辑悖论证明了停机问题是不可解的。
• 🏆 图灵的成就不仅限于理论，他在第二次世界大战中对破译德国密码机“恩尼格玛”做出了重大贡献。
• 💻 图灵设计了一种名为“Bombe”的电子机械计算机，利用了恩尼格玛机的缺陷，极大地提高了破解效率。
• 🏛️ 战后，图灵继续在学术界工作，并对早期电子计算机的发展做出了贡献。
• 🧠 图灵对人工智能领域也有重要贡献，提出了著名的“图灵测试”，用以判断计算机是否能够展现出与人类不可区分的智能。
• 📛 图灵的个人生活悲剧与他的科学成就同样著名，他因同性恋倾向在当时的英国受到迫害，并最终选择了自杀。
• 🏅 图灵奖是计算机科学领域的最高荣誉，以艾伦·图灵的名字命名，表彰他在计算机科学上的巨大贡献。

Q & A

艾伦·图灵是如何对现代计算机科学产生影响的？

艾伦·图灵提出了许多理论概念，包括图灵机，这些概念为现代计算奠定了基础。图灵机提供了一个简单而强大的计算数学模型，与λ演算在计算能力上等价，但因其相对简单性，在计算机科学领域更受欢迎。

图灵机是如何工作的？

图灵机是一种理论计算设备，它有一个无限长的存储带，用于存储符号，一个读写头可以读取、写入或修改存储带上的符号，还有一个状态变量来存储关于机器当前状态的信息，以及一组规则描述机器的行为。给定一个状态和当前符号，规则可以决定写入符号、改变机器状态、移动读写头，或者这些动作的任意组合。

什么是图灵完备性？

图灵完备性是指一个系统能够执行任何计算，只要有足够的时间和内存。如果一个计算机或编程语言是图灵完备的，那么它就和图灵机一样强大，能够模拟任何计算机的计算过程。

艾伦·图灵是如何帮助解决二战中的密码破译问题的？

艾伦·图灵设计了一种特殊的电子机械计算机——Bombe，利用了恩尼格玛机的一个关键缺陷（即一个字母永远不会被加密成它自己），通过尝试大量可能的设置组合，排除那些会导致字母自我加密的设置，从而大大缩小了可能的恩尼格玛机设置数量。

什么是图灵测试？

图灵测试是由艾伦·图灵提出的一种测试，旨在判断计算机是否能够展现出与人类不可区分的智能。如果一个人在与两个对话者（一个是人类，一个是计算机）通过文字交流时，无法区分哪个是计算机，那么计算机就通过了图灵测试。

艾伦·图灵的个人生活对他有什么影响？

艾伦·图灵是同性恋者，但在当时，同性恋在许多地方是非法的。1952年，一次对他家的盗窃调查揭露了他的性取向，导致他被控以严重猥亵罪。图灵选择了缓刑和激素治疗以避免监禁，但这些治疗改变了他的情绪和个性。普遍认为，图灵在1954年因服用毒药自杀，享年41岁。

图灵奖是什么？

图灵奖是计算机科学领域的最高荣誉，相当于物理学、化学或其他科学领域的诺贝尔奖。它是为了纪念艾伦·图灵对理论计算机科学的贡献而设立的。

大卫·希尔伯特提出的决策问题是什么？

大卫·希尔伯特提出的决策问题（Entscheidungsproblem）询问是否存在一个算法，它可以接受一个用形式逻辑写成的语句作为输入，并总能产生一个准确无误的“是”或“否”答案。

Lambda Calculus 是什么？

Lambda Calculus 是一种数学表达式系统，由美国数学家阿隆佐·丘奇开发，用以解决决策问题。它能够表示任何计算，但数学技术难以应用和理解。

艾伦·图灵是如何证明停机问题的不可解性的？

艾伦·图灵通过设计一个思想实验，即一个能够判断其他程序是否会停机的图灵机（命名为H），然后构建了另一个图灵机（命名为Bizzaro），它的行为与H相反。当Bizzaro用自身的描述作为输入时，会导致一个悖论，从而证明了停机问题是不可解的。

为什么说图灵机是通用计算机的模型？

图灵机被认为是通用计算机的模型，因为它们能够模拟任何计算过程，只要给定足够的时间和内存。这意味着，理论上，一个图灵机可以通过改变其规则和输入，来执行任何计算机程序的功能。

图灵在普林斯顿大学完成了什么？

艾伦·图灵在普林斯顿大学完成了他的博士学位，期间他在阿隆佐·丘奇的指导下学习。