上海交通大学统战部
当前位置: 首页>>人物风采>>正文
2012年12月24日

黄林鹏:思维机械化与计算思维

点击:[] 黄林鹏

■ 制造一台通过图灵测试的机器是很多科学工作者努力的目标。

■ 不管如何,如果机器能思维,我们希望其具备的是理性的思维,因为只有理性的思维才能对人类社会的发展有所帮助。

■ 计算思维的提出使人们开始反思,开始认识到原先的那种试图教使人们像机器那样去思考并形成如同机器那样去解决问题的方式存在着严重的缺陷。

http://news.sjtu.edu.cn/_mediafile/newsnet/2012/12/22/27xy4vfvaq.jpg

从1984年大学毕业踏上高校讲坛,近30年来目睹了国家的繁荣富强,见证了信息技术的飞速发展,今年是计算机科学家图灵诞辰100周年,借此机会谈谈我个人对思维机械化学习和计算思维教学的一点感想。

让机器模拟人类求解问题的思维过程

我们有时会思考“解决问题的想法是如何产生并发展的?”、“人的思维寄生于何处?”等等。显然,这些问题目前不会有明确的答案。

但我们也注意到人类在求解数学问题或完成涉及智能的任务时,必定存在思维过程,进而得出求解问题的方法和过程步骤。这样,如果面临相同或类似的问题,他人就可以依所了解的既定过程步骤一步一步得到答案。那么所有这些过程该如何描述?最基本步骤是什么?这些方法是否可由机器来完成?

1900年数学家希尔伯特提出了对数学发展有着深远影响的23个问题,对其中第10个问题“能否通过有限步骤来判定不定方程是否存在有理整数解?”答案的寻求直接促使了计算机科学的诞生和发展。(注:1970年前苏联数学家马蒂塞维奇证明了:在一般情况下,答案是否定的。)

图灵从构造模拟人类求解问题过程的机器入手。当然要从人脑内部去了解一个人求解一个问题的思维奥秘那是非常困难的事情,但我们可以从外部去观察人是如何求解问题的。不管是数学家还是普通人,给你一张上面写着问题的纸张,求解问题,不外乎是阅读问题,按照某种方式进行计算,再给出答案。而阅读可以简化为每次阅读当前位置的一个字符(纸可以简化为纸带),虽然求解问题的思维过程无从猜想,但人脑解决问题的思维活动可以看成是从一个状态转换为另外一个状态,在任一个状态下,对于所读取的当前位置的字符会做出相应的动作,并进入另外一个状态,动作可以是在当前位置写入一个字符或什么都不做、接着将当前位置前移、后移或保持当前位置不变。这看似奇怪,但你不得不承认,对求解问题过程的最简单的机械化抽象确实就是这样的,而最重要的状态迁移规则反映了求解一个问题的过程步骤。

如果对上面的描述进行分析,会发现存在两类东西,一类是纸(纸带),它存放的是描述问题、存储临时结果最终答案的数据,还有一类是状态迁移的规则,是求解问题过程步骤的某种表示,机器可在后者的驱动下一步一步模拟人类求解问题的行为最终得到问题答案的。到这里,不难想到,不管人是如何求解问题的,只要有状态变迁的确切描述,就可以构造出一台机器来模拟人的求解问题的行为。另一方面,有了图灵的计算模型,人解决问题时的复杂过程也有了一种表示的载体。图灵进一步尝试,构造一个机器,将状态变迁图本身(即求解问题的程序)和待处理的问题一起作为机器的输入,而机器的功能就是将求解问题的程序施加于问题,进而得到问题的答案。图灵最终成功构造出了被称为通用图灵机的机器。这也是目前我们所使用的冯·诺依曼“存储程序式”通用计算机的理论基础。在此之前,完成特定任务的过程步骤是作为机器本身的固有结构存在的,因此机器只能专用于解决某个特定问题,有了广义图灵机,程序就可如数据一般被存储于机器的存储器中,一台计算机可以随时载入不同的程序以解决不同的问题,这也就是今天的通用计算机。(80年代初,笔者用过DJS130国产计算机,其虽简单但庞大,程序需要从穿孔纸带载入,但其有别于通常的仅能完成特定任务的机器,比如那些精巧的由复杂齿轮驱动的跳舞机器玩偶,可以完成各种不同的计算任务。)基于通用图灵机,图灵证明了:停机问题(即是否存在一个算法,对于任意给定的图灵机,其都能判定从任意初始状态出发该机器的运行是否会终止。)是不可判定的。

图灵将论文交给纽曼审稿,纽曼虽被图灵的伟大思想所震撼,但他知道普林斯顿大学的邱奇已经给出了相同的答案,邱奇证明了任意两个lambda项是否等价的问题是不可判定的。但纽曼认为图灵的工作是从完全不同的角度出发的,他将人类求解问题的计算步骤用基本、简单、确定的机器指令进行描述,有着重要的价值,因此他推荐图灵到邱奇那里继续学习。图灵接着证明了图灵机可计算函数与λ可定义函数是等价的,并和邱奇一起提出了图灵-邱奇论题,即所有能行(有效)可计算的函数都可以由图灵机计算。之所以是一个论题,是因为有效可计算的概念不是一个严格定义的概念,这也反映了人类对思维本身这个问题的认识。

机器和思维

前面谈及人类求解一个问题的过程是否能由机器实现。但有一个问题更加根本,那就是机器能否思维?那是图灵对计算机科学的另外一个贡献,即图灵测试。斯坦福大学计算机前系主任Nilson在人工智能的教科书中写到,要回答这个问题,首先要弄明白什么是机器?什么是能?什么是思考?对于第一个问题就有着各种各样的答案?一种答案若人是机器,那么问题就不需要回答了,以为人类本身就是一个例子;如果人不是机器,那么人和机器的根本区别又在哪里,如果说区别是人能思维,那又绕回去了。

图灵则另辟蹊径,还是从观察人的行为出发。图灵注意到当时有一个电视节目,节目的参与者通过电传机和幕后的一男一女进行交互,通过询问问题、分析答案,辨识出性别。于是图灵提出,将一男一女分别换成机器和人类,如果参与者不能区分和你对话的是人还是机器,那么机器就具备了思维的能力。这就是图灵测试。

制造一台通过图灵测试的机器是很多科学工作者努力的目标。目前有多个机器人有着不俗的表现,比如Cleverbot在印度的一个节目中就成功地让59.3%的人相信它是人类(相比在同一个测试中人类选手也只获得了63.3%的信任票)。而IBM的Watson在美国知识竞赛类电视节目中也令人类选手刮目相看。其实要从能力上来说,机器和人类相比孰胜孰负很难说。如果从棋类博弈等人工智能最早涉及的领域看,西洋跳棋,由于规模不大,机器能生成所有的状态空间图并在极短的时间内完成搜索得到最佳路径,人类根本没有胜算;对于国际象棋,深蓝和人类顶级棋手的博弈则说明除了了了几个国际特级大师外,其余的和机器都不是一个数量级的。现在很多以前认为是机器无法胜任的领域,如汽车自动驾驶等,机器也基本可以胜任。目前计算机在整个经济社会中扮演着非常关键的作用,可以开玩笑地说如果机器停了,大家饭都没得吃,因为食堂吃饭要在机器上刷卡,没有刷卡,服务员是不会让你端者饭菜走的。

目前有很多学者认为能力(包括智能)和思维不一样,虽然机器能力强,甚至可能存在某种智能,但目前还不具备思想。另外还有一些研究人员试图通过读取脑信号并进行解释以试图揭开人类思维之谜。当然不管如何,如果机器能思维,我们希望其具备的是理性的思维,因为只有理性的思维才能对人类社会的发展有所帮助。

程序语言和思维

目前计算机的结构还是属于冯o诺伊曼“程序存储式”范畴,其包括中央处理单元(CPU)、存储程序和数据的存储器以及输入和输出设备。虽然程序可以是图灵机的指令序列,但为了方便和计算机交互,人类发明了程序设计语言,包括机器语言、汇编语言和高级语言等。机器语言使用的是CPU提供的指令集,指令是由0和1组成的二进制序列。为了更容易为人们所理解和记忆,汇编语言则使用了“助忆符”来表示机器指令。而有着严格定义的高级语言则吸收了自然语言和数学表达式的优点。但我们也认识到作为工具的语言,它和人的思维必然存在着相互的作用。

前面提到的图灵机,有着一个个状态,每个状态对应不同的输入有着既定的动作,包含后续状态的选取,在程序存储式计算机里,如果这些动作对应着指令序列,那么后续状态的选择就对应着设置下次要执行的指令序列的地址,因此在设计CPU指令系列的时候就有了“跳转”指令,在早期的过程式语言中就有了goto语句。使用goto语句,程序员在编写程序的时候就可以自由控制程序的执行流程,但也带来了问题,就是程序不易阅读、维护性也差。后来人们认识到顺序、选择、循环就足以表示各种程序控制结构,程序员设计程序的思维也就发生了改变。最早的程序设计语言之一LISP,它的理论基础就是前面提到的lambda演算,lambda演算是对函数定义及其函数应用的刻画,过程式语言中的顺序结构可以使用函数复合表示、选择可以使用lambda表达式直接定义,而循环则可借助于递归来刻画。递归可以通过描述性质来说明一个实体,特别的是在实体的描述中可以出现实体的名字。这种定义本来不属于lambda表达式的范畴。但如果从数学的角度看,定义的实体就是满足等式的解。柯里和图灵分别给出了不动点算子,结果就是,只要给出等式,等式的解就可使用纯lambda表达式表示。自此,程序员就可以自由地使用递归来编写函数、描述数据对象。特别函数的参数和计算结果也可以是函数,这和一台图灵机的输入可以是另一台图灵机的编码一样。但语言也会对编程思维带来限制,举一个例子,对于集合,一般使用递归定义(构造)的表,但要对集合的某个元素进行处理,则不能随意,只能逐一选取(析构)。也就是语言会引入某种人为的非问题本身具有的顺序性,进而限制了自由处理实体的编程期望。目前lambda表达式在许多高级语言如Java、C++、Python等的最新版本都有所支持。

国家863项目的提出,是受日本五代机计划和欧洲智能机计划的影响。日本五代机计划的核心是Prolog语言及其推理机。Prolog是一种逻辑式语言,也称为描述性语言,用户只要给出已知的实体间关系的描述,给出观察的事实,系统就可解答询问的目标是否为真或给出使目标为真的变量的取值。重要的是问题求解过程无需由程序员描述,完全由推理机自动进行。显然,这让程序员的思维习惯从描述求解问题的详尽过程转向了如何准确给出实体间的实质关系。推理机其实就是自动定理证明器。但逻辑系统本身有很多,有自然推理系统、Gentzen序贯(矢列)演算、Hilbert公理系统等等,那证明器应该使用什么样的逻辑系统呢?如果进一步观察,就会发现由于对称性,对于每个逻辑连接符都会有两组(条)规则,一组对应连接符的引入,一组对应连接符的消去,显然推理的每步都会面临多种选择。那有没有只有一条推理规则但是正确且完备的逻辑系统呢?要创造出这样的系统,首先必须消去所有给定公式(对目标需先取非,即进行反驳)的连接符,化归为子句形式,而子句上的运算,真的只有一条规则,即归结法。进一步,为了使得推理更加有效,可进一步对子句的形式进行限定,比如限制为Horn子句,这时程序员发现他要给出的实体间的关系就可简化为类似于“如果…则…”这样的形式,程序员的思维习惯再次受到所使用的语言的影响。

随着计算机的推广应用,程序变得越来越庞大,对程序复杂度的控制越来越受到重视,面向对象等程序语言也因此得到了普及,而程序员的思维习惯再次受到了影响。

今日,构造软件的基本单元不再是简单的一条或一段程序代码,他可能是实现某个功能的模块,也可能是运行于远程机器的服务,云计算的出现也进一步刷新了人们的思维习惯。

目前互联网以及通过它连接起来的各种软硬件基础设施,为信息资源的广泛共享和利用提供了可能,也为计算机软件技术的应用和发展提供了更为广阔的空间,随着应用模式向“网络为中心的环境和面向服务的体系结构”发展,基于网络的软件系统正运行于一个开放、动态、多变的环境之中,软件系统的能力得以延伸,而软件系统的可信性问题也进一步得到了关注。

目前我们和北京大学合作进行体系结构驱动的可信软件构造方法的研究,探索基于构件和面向服务的网络软件系统的设计方法,这里的基本模块是软件构件和网络上运行的服务,要研究的是如何由其通过编程组合为软件系统,编程关注的最小单元就不再是运行于机器的指令了。那是否软件系统(或系统)本身可以作为构件,对其进行“编程”,得到“系统的系统(SoS)”,最近我们和东南大学和人民大学等得到了国家自然科学重点基金课题的资助,正在进行“系统的系统”的软件机理和机制方面的研究。SoS是通过集成多个已有系统,从而构建一个在功能上强于已有系统的一种复合系统,显然已有的思维习惯必需打破,而新的思维应该是什么?她是个人思维还是群体思维?还需进一步探索。

计算思维及其教学

计算技术的发展日新月异,已经渗入到各个学科,深入到社会的方方面面,然而计算机教育的进展却差强人意,进入新的世纪,国外和国内一样,一方面各个专业对计算机专业人才的需求不断增加,另一方面选择计算机科学作为职业的学生却不断减少。为了吸引学生,一些高校不断对计算机教学方案进行调整和改革。而有一些人则认为,既然计算已和各行各业以及个人生活紧密相关,那么计算就是人们必须掌握的技能之一,其非计算机专业所独有的知识,要做的就是研究计算的本质,告诉所有有着计算需求的人们该如何去驾驶计算。

2006年,美国卡内基·梅隆大学的Jeannette M. Wing(周以真)教授首先提出计算思维(Computational Thinking)的概念,她将计算思维定义为是运用计算机科学的基础概念进行问题求解、系统设计、以及理解人类行为等的一系列思维活动。她认为源自数学思维和工程思维的计算机思维,与阅读、写作与算术能力一样,也应成为人类的基本技能。她特别强调:计算思维是“人的,不是计算机的思维”,而且,“计算思维是人类求解问题的一条途径,但决非试图使人类像计算机那样去思考”。

计算思维的提出使人们开始反思,开始认识到原先的那种试图教使人们像机器那样去思考并形成如同机器那样去解决问题的方式存在着严重的缺陷。为什么我们要“thinking in X”(X是某一种程序设计语言),为什么思想要被某种体系结构或某种程序设计语言所限制,为什么不能以解决问题的自然方式进行思考。为此许多计算机教育工作者开始整理、归纳计算机学科数十年来形成的解决问题的有效方法,在计算机科学教育中进行尝试,以促使计算思维技能的教学早日成熟。

最近2年,计算思维的概念也波及国内计算机科学的教育,中科院王飞跃教授首先建议西安交大软件学院开设《计算思维与计算文化》讲座课,最近陈国良院士和李国杰院士也多次倡导在我国开展计算思维的教育。

2009年,由于工作需要,我接手《程序设计思想与方法》通识课程的建设,课程组有近10个老师,想不到的是开学后只有寥寥几个非电子信息与电气工程学院学生报名,派去上课的教师非常尴尬。学院、系负责教学的领导得知情况后十分关注,多次组织教学小组教师分析问题。在广泛听取教师学生意见,并经过多次讨论后,教学小组提出了基于计算思维并结合学科特色的通识课程教学方案并向学校教务处汇报,教务处主管通识课程教育的领导非常重视,经过多次质询,教务处最终同意在新学期试教。

2010年,我到美国加州访问,顺访了加州大学Berkeley分校和斯坦福大学,并了解了国外一些学校的计算机教学情况,比如Berkeley注重于学习的趣味性,通过展示计算之美来讲授计算思维;Purdue大学则侧重于计算在其他学科中的应用,通过邀请其他学科的学者共同讲授课程,促进学生计算思维技能的发展;MIT则通过程序设计的讲授引导学生了解计算机科学,帮助学生获得通过编程解决实际问题的能力,树立自信心。

通过吸收国外教学经验,在国内同行的鼓励和学校教务处、院系的支持下,《程序设计思想与方法》课程组在国内首先开设出基于计算思维的大学计算机通识课程,实施问题驱动、任务导向的教学方法,以培养能解决不同领域问题、具备计算思维能力的创新复合型人才为目标,建设以计算思维为核心的大学计算机通识课程体系为导向,探索不同领域的学科知识与计算思维概念的有机融合,为国内计算思维课程的建设提供了参考。

学者小传

黄林鹏,上海交通大学电子信息与电气工程学院计算机科学与工程系教授,博士生导师。中国计算机学会高级会员,开放式系统、软件工程、服务计算专业委员会会员,上海市高等学校计算机等级考试委员会委员,全国高等院校计算机教育研究会理事,上海市计算机基础教育协会常务理事,农工党上海交通大学委员会副主委,长期从事程序设计语言的教学和可靠分布式系统的研究,曾获得上海市高校优秀青年教师称号,曾主持国家自然科学基金面上项目2项、国家863高科技项目2项。目前作为上海交通大学方项目组负责人参与国家自然科学基金重点项目《体系结构驱动的可信软件构造方法与技术研究》和《基于服务组合的“系统的系统”软件机理与方法》的研究,负责的上海交大核心通识课程《程序设计思想与方法》2011年获得上海市教委重点课程项目立项资助。申请专利18项,在国内外学术刊物会议发表论文80余篇,翻译包括Knuth的《计算机程序设计艺术》在内的专著和教材10册,主持起草地方标准1项。

1984年在浙江大学获得学士学位,1989年和1992年在上海交通大学获得硕士和博士学位。1994年、1997年在香港中文大学进修访问,1999年到2000年在美国哈佛大学访问进修一学年。1984年-1986年在福建师范大学数学系任教,1992年在上海交通大学任教至今。

上一条:蒋丹:图学教育的变革与启示 下一条:范秀敏:在比较中学习与反思

关闭