牛津通识读本：计算机科学

作者简介

苏布拉塔？达斯古普塔 美国路易斯安那大学拉斐特分校计算与信息学院计算机科学信托基金杰出学者，曾任曼彻斯特大学科技学院计算机系统工程教授，并在牛津大学和剑桥大学等多所大学任访问学者。他著有多部关于技术、科学和创造力的书籍，包括《始于巴贝奇：计算机科学的起源》（2014）。

内容简介

前　言 20世纪60年代是一个社会和文化动荡的时代。冷战、民权运动、反战示威、女权运动、学生反抗、“权力归花运动”、静坐抗议和左翼激进叛乱，但隐藏其中—几乎没有被注意到—有一门新科学在西方的大学校园里应运而生，甚至在非西方世界的一些地区虽更为初步但也出现了。 这门科学的核心是一种新型机器：电子数字计算机。围绕这台机器的技术有多种名称，最常见的是“自动运算”、“自动计算”或“信息处理”。在讲英语的国家与地区，这门科学被称为“computer science”，而在欧洲，它被称为“informatique”或“informatik”。 自动计算的技术理念—设计和制造能够在最少人工干预情况下进行计算的真实机—至少可以追溯到19世纪初英国数学家查尔斯·巴贝奇的痴迷梦想。20世纪30年代末，英国逻辑学家艾伦·图灵和美国逻辑学家阿隆佐·丘奇首先研究了计算的数学概念。但是，真正的计算经验科学的推动力要等到20世纪40年代发明、设计和实现电子数字计算机之后，也就是第二次世界大战刚刚结束之后。即便如此，此时仍存在一段酝酿期。直到20世纪60年代，大学开始提供计算机科学的本科和研究生学位，第一代受过正规培训的计算机科学家走出校园，一门拥有自己名称和身份的自主科学才开始出现。 自1946年电子数字计算机问世以来，与这台机器相关的技术（现在一般称为“信息技术”或“IT”）以及相关的文化和社会变革（一般表述为“信息时代”“信息革命”“信息社会”）的惊人增长是有目共睹的。事实上，我们几乎被这种技术社会环境吞没了。然而，作为以技术为基础的科学——知识学科——在专业的计算机科学社群之外是不太可见的，当然也不太为人所知。然而，计算机科学无疑与分子生物学和认知科学一样，是第二次世界大战后最重要的新科学之一。此外，计算机科学有一种特殊性，它吸引了人们的注意力，并将其与所有其他科学区分开来。 我写这本书的目的，是为那些对科学思想和原理非常感兴趣的求知欲强的读者提供理解计算机科学基本性质的基础，以丰富对这门奇怪的、历史上独一无二的、意义重大的、仍然崭新的科学的理解。简而言之，本书力求以直接、简洁的方式回答这个问题：什么是计算机科学？ 在我们继续讨论之前，需要澄清一些术语。在本书中，我将使用“计算”这个词作为动词来表示某种活动；“计算结果”用作名词，表示计算的结果；“计算的”被用作形容词；“计算机”是一个名词，指的是进行计算的设备、人工制品或系统；“人工制品”指的是人类——有时是动物——制造的任何东西；“计算人工制品”是任何参与计算工作的人工制品。 最后，必须声明一个警告。本书首先接受这样一个命题：计算机科学确实是一门科学；也就是说，它体现了与科学概念相关的广泛属性，值得注意的是，它包含了对某种现象的本质进行探索的经验、概念、数学和逻辑、定量和定性模式的系统融合。对这一假设的质疑属于科学哲学的范畴，它超出了本书的范围。这里感兴趣的持久问题是计算机科学作为科学的本质，尤其是其独特而显著的特征。 第一章 计算的“特征” 什么是计算机科学？1967年，该学科的三位杰出早期贡献者——艾伦·佩利、艾伦·纽厄尔和赫伯特·西蒙——提供了一个现在已成为经典的答案，他们很简单地指出，计算机科学是对计算机及其相关现象的研究。 这是一个相当直接的回答，我认为大多数计算机科学家会接受它作为一个粗略且现成的工作定义。它以计算机本身为中心，当然，没有计算机就不会有计算机科学。但是，计算机科学家和好奇的外行人可能希望更精确地理解这一定义中的两个关键术语：“计算机”及其“相关现象”。 一种叫作“计算机”的自动机 计算机是一台自动机。这个词在17世纪被创造出来（复数形式为“automata”），指的是在没有外部影响的情况下，主要由自己的原动力驱动，执行某些重复的运动和动作模式的人工制品。有时，它也会模仿人类和动物的动作。早在基督以前的古代，人们就设计出了精巧的机械自动装置，主要是为了满足富人的娱乐需求，但有些具有非常实用的性质，例如，据说水钟就是公元1世纪亚历山大的工程师希罗发明的。15世纪在意大利发明的重量驱动的机械时钟，是这种自动机的一个非常成功和持久的派生物。在18世纪的工业革命中，由托马斯·纽科门（在1713年）发明，后来由詹姆斯·瓦特（在1765年）等人改进的“常压”蒸汽机，能驱动水泵从矿井中抽水，它是另一个实用的自动机实例。 因此，能够执行这样或那样物理动作的机械自动机有着悠久的历史；而模仿认知行为的自动机出现的时间则要晚得多。一个著名的例子是，20世纪40年代末至50年代初，英国神经生理学家格雷·沃尔特发明的“乌龟”机器人——“机器冒险者”。但是，在20世纪40年代后半期发展起来的自动电子数字计算机，则标志着一个全新的自动机类的诞生过程；因为计算机是用来模拟和模仿某些人类思维过程的人工制品。 将计算视为模仿人类思维的一种方式——将计算机视为“会思考的机器”——是一个非常有趣、令人不安和有争议的概念，我将在后面讨论这个概念，因为它是计算机科学的一个分支人工智能（AI）的根。但是，许多计算机科学家更愿意在他们的学科中不那么以人类为中心，有些人甚至否认计算与自主人类思维有任何相似之处。19世纪40年代，查尔斯·巴贝奇的同事、英国著名数学家阿达·洛芙莱斯伯爵夫人就指出，巴贝奇设想的机器（称之为分析机，一个世纪后成为现代通用数字计算机的第一个化身）没有“自诩”可以自行启动任务，它只能做人类命令它做的事情。现代人工智能怀疑论者经常重复这种观点，比如电子计算机的先驱之一莫里斯·威尔克斯爵士。他在20世纪末发表了一篇与洛芙莱斯的设想类似的文章，他坚持认为计算机只做“写下的程序要它们做的事情”。 那么，是什么让计算机与其他所有类型的人工制品（包括其他类型的自动机）区分开来的？是什么让计算机科学成为一门独特的科学学科的？ 在本章中，我将把计算机视为“黑盒子”。也就是说，我们或多或少会忽略计算机的内部结构和工作原理，这些会在后面讨论。目前，我们将把计算机视为一种通用的自动机，只考虑它做了什么，而不考虑它是如何做这些事情的。 计算作为信息处理 每一门渴望成为“科学”的学科，都受到其所关注的基础知识的限制。物理学的内容包括物质、力、能量和运动，化学是原子和分子，遗传学的本质就是基因，土木工程则包括使物理结构保持平衡的力。 计算机科学家普遍认为，计算机科学的基本内容是信息。因此，计算机是自动从“环境”中检索、存储、处理或转换信息，并将其释放回环境的工具。这就是为什么计算的另一个术语是信息处理；为什么在欧洲，计算机科学被称为“informatique”或“informatik”；以及为什么计算界的“联合国”被称为国际信息处理联合会（IFIP）。 问题是，尽管IFIP在1960年成立（因此对信息处理的概念给予了官方的国际支持），但直到今天，关于什么是信息仍然存在很多误解。正如莫里斯·威尔克斯曾经说过的那样，这是一件难以捉摸的事情。 “无意义的”信息 造成这种情况的一个重要原因是一个不幸的事实：“信息”一词被通信工程师用来表示与日常含义截然不同的东西。我们通常认为，信息会告诉我们关于世界的一些事情。在普通语言中，信息是有意义的。“X国的冬季平均气温是5摄氏度”这一陈述告诉了我们有关X国气候的一些情况，提供给我们关于X国的信息。相比之下，在通信工程学一个被称作“信息论”的分支中，信息这一词汇主要是由美国电气工程师克劳德·香农在1948年创立的，具体而它只是一种通过诸如电报线和电话线等通信渠道传输的商品。在信息论中，信息是没有任何意义的。信息论中的信息单位称为位或比特（二进制数字的简称），位只有两个值，通常表示为“0”和“1”。然而，在个人电脑和笔记本电脑的时代，人们对字节的概念更加熟悉。一个字节由8位组成。由于每个位可以有两个值中的一个，所以一个字节的信息可以有28（=256）个可能值，范围从00000000到11111111。不过，在“信息”这个意义上，位（或字节）的含义是无关紧要的。 在计算中，这种无意义层面的信息处理肯定是相关的，因为（后续将会介绍）由电子电路、磁性和机电设备等（统称为“硬件”）组成的物理计算机，是以位和字节的倍数来存储、处理和传递信息的。事实上，衡量计算工件的容量和性能的方法之一就是使用位和字节。例如，我可能会购买一台具有6千兆字节内部存储器和500千兆字节外部存储器（“硬盘”）的笔记本电脑（其中1千兆字节=109字节）；或者，我们可以说计算机网络以100兆位/秒的速率传输信息（其中1兆位=106位）。 “有意义的”（或语义）信息 但是，物理计算机（我们将在第二章中介绍）只是一种计算人工制品。无意义信息只是计算机科学家感兴趣的一种信息。另一种更重要（可以说更有趣）的信息是有意义的信息：语义信息。这样的信息与“真实世界”相联系——从这个意义上说，与这个词的日常使用相对应。例如，当我通过我的个人计算机访问互联网时，信息处理肯定是在物理或者说“无意义”的层面发生：位从某个远程计算机（“服务器”）通过网络传输到我的机器上。但我正在搜索的信息是关于某个事件的，比如说某个人的传记。我在屏幕上阅读到的文本结果对我来说是有意义的。在这个层面上，我正在与之交互的计算人工制品是一个语义信息处理系统。 当然，这些信息几乎可以是关于物理、社会或文化环境，关于过去，关于其他人公开表达的思想和想法，甚至关于一个人自己的想法（如果它们碰巧被记录或存储在某处的话）的任何东西。计算机科学家保罗·罗森布鲁姆曾经指出，这些有意义的信息与无意义的信息共享的是，这些信息必须用某些物理介质来表达，比如电信号、磁态或纸上的标记；而且它解决了不确定性。 信息是知识吗？ 我们来考虑一个语义信息项，例如个人传记。在阅读它时，我就可以断言我掌握了关于那个人的知识。这指出了普通语言中信息概念的第二个混淆来源：信息与知识的混淆。诗人T.S.艾略特对它们的区别毫不怀疑。在他的戏剧《岩石》（1934）中，他曾经提出一个著名的疑惑： 我们在知识中失去的智慧在哪里？ 我们在信息中丢失的知识在哪里？ 艾略特显然暗示了一种等级制度：智慧高于知识，知识高于信息。 计算机科学家通常避免谈论智慧，因为这超出了他们的职权范围。但至少在某些情况下，他们在区分知识和信息方面仍然有些不安。例如，在计算机科学的一个分支领域人工智能中，一个长期存在的问题是知识表示——如何在计算机内存中表示关于世界的知识。他们研究的另一种问题是，如何从知识体系中做出推断。人工智能研究人员认为的知识，包括事实（“人皆有一死”）、理论（“自然选择导致的进化”）、法则（“每一个作用力都有一个相等和相反的反作用力”）、信仰（“有一个上帝”）、规则（“总会在停车标志处停下来”）和程序（“如何制作海鲜秋葵汤”）等等。但是，这些实体是如何构成知识而不是信息的，这在很大程度上还没有被说明。人工智能研究人员可能会宣称，他们在计算机科学分支中所做的是知识处理而不是信息处理；但他们似乎不愿解释为什么他们关心的是知识而不是信息。 另一个被称为“数据挖掘”的专业，关注的是从大量数据中进行“知识发现”。一些数据挖掘研究人员将知识描述为隐藏在大型数据库中的“有趣”和“有用”的模式或规律。他们将知识发现与信息检索（另一种计算活动）区分开来，后者关注的是基于某些查询从数据库中检索“有用的”信息，而前者识别的知识不仅仅是“有用的”信息，或者说不仅仅是规律性的模式：这些信息必须在某种意义上是“有趣的”才能成为知识。和艾略特一样，数据挖掘研究人员认为知识优于信息。无论如何，数据挖掘的重点是知识处理，而非信息检索。 计算哲学家卢恰诺·弗洛里迪对信息和知识的关系提出了以下观点。信息和知识具有“家族相似性”。它们都是有意义的实体，但它们的不同之处在于，信息元素像砖块一样是孤立的，而知识将信息元素相互关联，这样人们就可以通过关系产生新的推论。 举个例子：假设在开车时，我在汽车收音机上听到日内瓦的物理学家检测到了一种叫作希格斯玻色子的基本粒子。这个新事实（“希格斯玻色子存在”）对我来说无疑是一条新信息。我甚至可能认为我获得了一些新知识。但其实这是一种错觉，除非我可以将这些信息与其他有关基本粒子和宇宙学的相关信息联系起来；而且，我也无法判断这些信息的重要性。物理学家掌握了关于亚原子粒子和宇宙结构的事实、理论、定律等的集成网络，使他们能够吸收这一新事实并掌握其意义或后果。他们拥有这样做的知识，而我只是获得了一条新信息。 信息是数据吗？ 在提到数据挖掘时，我引入了另一个非常相关的术语：数据。尤其是在计算机科学界，这个术语是我们对信息概念产生模棱两可理解的一个原因。 早在1966年，计算机科学家高德纳就曾评论过，这种模棱两可的理解，本质上是一种混乱的理解。当时，计算机科学本身就是一门科学学科，它要求发明新概念并澄清旧概念。高德纳指出，在科学中，“信息”和“数据”这两个术语似乎存在一些混淆。当科学家执行一项涉及测量的实验时，引发的可能是以下四种实体中的任何一种：被测量的“真实”值；实际获得的值——真实值的近似值；值的表示；以及科学家通过分析测量得出的概念。高德纳断言，“数据”一词最适用于这些实体中的第三个。因此，对于计算机科学家高德纳而言，数据是通过以某种精确方式观察或测量所获信息的表示。因此，在他看来，信息先于数据。在实践中，信息和数据之间的关系就像信息和知识之间的关系一样模糊不清。在这里，我只能列举一些关于这种关系的不同观点。 对于著名的系统和管理科学家罗素·阿科夫来说，数据构成了观察的结果。它们是对象和事件的表示。至于信息，阿科夫想象有人问一些数据问题，然后这些数据会被“处理”（可能是由人或机器）以提供答案，而后者就是信息。因此，根据阿科夫的说法，与高德纳相反，数据是先于信息的。 对于卢恰诺·弗洛里迪来说，数据也是先于信息的，但他是在不同的意义上讨论的。根据弗洛里迪的说法，只有当系统的两种状态之间缺乏一致性时，数据才会存在。正如他所说，只要有两个变量x和y，使得x≠y，就存在数据。因此，对于弗洛里迪来说，数据是一种条件，它本身没有任何意义，只是表示差异的存在。例如，当我接近红绿灯时，我观察到的红色信号是一个数据，因为它本来可以是其他情况：黄色或绿色。 鉴于数据的这一定义，弗洛里迪将信息定义为一个或多个根据某些规则结构化且有意义的数据元素。用语言学家的行话来说，当信息同时具有语法和语义时，它就是数据。因此，我对红色交通信号的观察——一个数据——变成了信息，因为红灯的含义是“驾车者必须在红绿灯处停车”。如果我不将此动作与红灯联系起来，后者将只是一个数据。 最后一个例子，对于人工智能研究人员杰弗里·施拉格和帕特·兰利来说，数据不是观察得来的。相反，观察就是数据；更准确地说，观察到的东西被选择性地记录下来以作为数据。信息是不在他们讨论之中的。 程序员的观点 这些示例足以从不同的角度说明信息和数据连接的模糊性。但是现在，让我们回到高德纳的观点。我认为，他对数据的定义在很大程度上反映了那些计算机科学家的观点，他们专门研究计算机科学的另一方面，即计算机编程——人类将计算任务传达给计算机的技术（我将在本书后面讨论这个话题）。即使在口头上支持计算作为信息处理的想法，程序员和编程理论家通常也不会考虑“信息”。相反，他们更关心像高德纳一样的科学家们的数据理念。更准确地说，他们将数据视为执行计算的基本对象（“数据对象”）；因此，他们专注于数据对象的分类（“数据类型”），表示复杂数据对象（“数据结构”）的规则，以及操作、处理和转换此类数据对象以产生新的数据对象的规则。对于这样的计算机科学家来说，重要的是数据，而不是信息，也不是知识。更准确地说，程序员理所当然地认为“现实世界”中存在信息。但对他们来说，更有趣的问题是，如何以一种不仅适用于自动计算而且适用于人类理解的形式来表示现实世界的信息。（毋庸赘言，像历史学家、统计学家和实验科学家这样的其他从业者，通常不会以这种方式看待数据。） 我将在本书后面详细说明这一点。但是，先举一个程序员的数据观点的非常简单的例子。在大学环境中，注册办公室存有注册学生的相关信息：他们的姓名、出生日期、家庭住址、电子邮件地址、父母或监护人姓名，他们主修的科目、修读的课程、获得的成绩、持有的奖学金、支付的费用等等。大学管理部门需要一个系统，将这些信息以系统的方式组织起来（即一个“数据库”），以便可以准确、快速地检索任何特定学生的相关信息，可以插入关于现有学生或新学生的新信息，可以有效地跟踪个别学生的进度，并且可以收集关于整个学生群体或某个子集的统计数据。被赋予创建这样一个系统任务的程序员并不关心信息本身，而是考虑到信息的性质，如何识别表示学生信息的基本数据对象，构造表示数据对象的数据结构，并构建一个数据库，以便满足大学管理部门所要求的计算任务。 符号结构作为共同命名 在本章开始时，我提出了这样一个命题：计算的基本内容是信息，计算机是处理信息的自动机，因此，计算机科学是一门研究信息处理的学科。 但我们也看到，对于一些计算机科学家（如人工智能研究人员）来说，计算的基本内容是知识而不是信息；对于其他人（例如程序员和编程理论家）来说，计算的基本内容是数据而不是信息。我们从以下计算文献中的术语示例中了解这三个实体的不同用法（其中一些已经出现在本章中，其他将在后面的章节中出现）： 数据类型、数据对象、数据结构、数据库、数据处理、数据挖掘、大数据…… 信息处理、信息系统、信息科学、信息结构、信息组织、信息技术、信息存储与检索、信息论…… 知识库、知识系统、知识表示、知识结构、知识论、陈述性知识、程序性知识、知识发现、知识工程、知识层次…… 那么，我们能否将这三个实体——信息、数据、知识——简化为一个共同命名呢？事实上是可以的。计算机科学家保罗·罗森布鲁姆将信息等同于符号，我们可以对此进一步分析；就计算机科学而言，所有这三个实体都可以（并且通常是）由符号表示——或者更确切地说，由符号系统、符号结构来表示——也就是说，这些实体“象征”或表示其他实体。 符号需要一种表达它们的媒介，比如纸上的标记。举一个例子，“希格斯玻色子存在”这段文字是一个符号结构，其组成符号是指声音单位或音素的字母字符，加上“空白”符号；当它们串在一起时，代表了物理世界的某些东西。对于物理外行来说，这是一条信息；对于粒子物理学家来说，这成为她关于基本粒子的知识体系的一个组成部分。然而，物理学家能够理解这些信息的知识本身，就是一个更复杂的符号结构，它存储在她的大脑中和/或印刷在书籍和文章的文本中。高德纳认为数据是信息的表示，这意味着数据也是表示其他意指信息的符号结构的符号结构。即使是信息论中“无意义的”信息，比如位和字节，也可以用计算机中的物理符号表示，例如电压电平或磁态，或者在纸上用0和1的字符串表示。 因此，就其最基本的性质而言，计算的东西是符号结构。计算是符号处理。任何能够处理符号结构的自动机都是计算机。佩利、纽厄尔和西蒙建议的与计算机相关的“现象”，最终都可以归结为符号结构及其处理。计算机科学归根结底是自动符号处理的科学，纽厄尔和西蒙都强调了这一观点。根据我们所属的计算机科学的特定“文化”，我们可以选择将这些符号结构称为信息、数据或知识。 正是这个概念——计算最终是符号处理，计算机是符号处理自动机，计算机科学是符号处理的科学——使得计算机科学区别于其他学科。至于它的特别之处，将在后面的章节中解释。 这是一部短小但内容充实的计算机科学普及读物，它成功地避开了复杂的数学语言，仅用文字和图表就清晰地道出了有关计算机科学☆为深奥的知识，对于非专业读者来说，可以无障碍地畅游计算机科学世界，有效激发探索信息科技和人工智能的兴趣与热情。