关键词：计算理论；计算思维；能力培养；创新模式
0引言
前一段时间网上流传中国科学院研制“龙芯”的胡伟武老师的一个视频，其中提到中国能够开发Java虚拟机的人才很少的问题，该问题的出现引人思考。我国计算机类专业的学生包括研究生毕业后做底层开发的人才很少，绝大多数人是把国外公司开发出来的编程语言拿过来直接使用，编程时直接调用软件包中的函数，至于这些函数是如何实现的并没有几个人认真思考。久而久之，学生（包括一些教师与软件开发人员）也很少思考或研究这一问题，突然遇到这样的问题就会束手无策、无从下手。所谓万丈高楼平地起，没有基本的思维训练很难做到基础性创新思维的能力培养。中兴事件给我们国家的原始创新问题敲响了警钟，有人在网上提出“假如微软、谷歌不让我们使用其操作系统怎么办”的问题，说明应用与创新缺一不可，只有应用的火热而没有创新就会受制于人。计算理论课程是从本质上介绍计算机科学的课程，是计算机学科发展的基石。为了计算机学科更好地发展，将计算理论作为一门必修课，作为培养高年级本科生或研究生计算思维和创新思维的重要一环是非常必要的，这是开设此门课程的现实选择，也是必然选择。
1计算理论在研究生教学中的重要性
“计算机科学技术日新月异，新东西层出不穷，旧的东西迅速被淘汰，但是作为一门科学，它有其自身的理论基础，这些思想精华长久地、甚至永恒地放射光芒，这些理论在应用开发中好像是‘无用的’，但实际上，对于每一位从事计算机科学与技术的研究与开发的人来说，它们都是不可缺少的，就像能量守恒之类的物理定律对于每一位自然科学工作者和工程技术人员那样”[1]。“通过这些要点，我们对计算机科学的重要基石有了一些新的认知，有些之前我们认为可能比较新颖的东西（比如层次化存储），实际上在计算机诞生初期就被提出甚至进行了量化分析，每年顶级会议上出现的一些新成果都是这些思想的实现；有些之前我们认为可能比较陈旧的东西（比如虚拟化），实际上换一个角度可能是一种新的研究思路。真正具有本质的重要性的东西，无所谓“新”与“旧”，应该在历史发展中传承和保持下来”[2]。上述两段话充分说明计算理论在现代计算机科学与技术研究生教学中的核心意义。从科学基础理论角度来讲，可计算性理论是计算机科学最核心的基础理论，如果没有可计算性理论，计算机将难以称为计算机科学，这是学科发展需要，也是开设这门课程的根本原因。为创新能力的培养与思维训练过程，这一系列过程从低到高不断升华，可逐步培养学生的计算思维与创新能力。在本科教学中，学生养成了“老师教什么，学生就记忆复述什么”的学习习惯，一般很少对教师讲授的内容提出异议和新的见解。只是在离散的抽象代数部分才开始涉及基本的运算系统，但由于过于抽象，一般学生也是一知半解。在研究生教学中，教师教什么、学生就记忆复述什么的学习习惯一定要打破，学生要养成“老师讲授的不一定是唯一的、最好的解决问题方法”的思想意识，教师要以“没有最好，只有更好，优化优化再优化”为教学理念。学生要勇于向老师提出问题，敢于向课本内容提出挑战，给出新的见解。研究生接受计算理论学位课程的学习已经不仅是为了掌握知识获得学分，还是对计算系统的了解逐步向更高级的计算系统（它的运算呈现出模型化的特征）过渡，并由此学会一种思维方式、一种创新能力，这种思维方式与创新能力对于从事任何工作都是受益终身的。作为一门研究生素养训练的学位课程，计算理论课程的教学改革必须跟上国家创新人才培养的时代步伐，精心设计、合理安排、科学谋划，这是计算机学科发展的需要，是国家积极推进培养创新人才赋予我们的使命与任务。
2计算理论课程的教学内容
人工智能、大数据、云计算、边缘计算等领域正在蓬勃发展，越来越多的经验在实践中累积，但是理论基础都相对薄弱，需要构建各自领域中有较强针对性的基础理论[2]。面对新形势、新需求，计算理论要讲述的内容包括以下几方面。1）以5条基本指令x=x+1、x=x-1、TOAIFx≠0、TOA和y=x为基础的元语言程序描述可计算函数。使用5条基本指令的元语言程序教学过程，就是训练学生使用最基本的指令编程实现复杂的可计算函数的抽象思维能力过程。近年来出现的Python语言是一个比较流行的易学易用的编程语言，其创始人Guido也是从编写Python的编译器开始，将其逐步演化成今天的流行语言。程序员中流行的“人生苦短，我用python”也说明其受欢迎的程度，但火热程度的背后是Guido及团队成员不懈努力的结果，没有开发人员的默默付出，将从底层搭建出来的结果呈现给我们，就没有今天的Python。对热议的中兴事件引起的处理器芯片设计问题来说，将指令集和程序区分开，可以以不变的少量指令构成万变的应用程序。指令集（如x86、MIPS、RISC-V）中不同类型的指令都是有限的，但可以编写的不同程序的数量极其庞大，这样硬件上的固定性与软件上的任意性矛盾就得到解决[2]。2）从初始函数S(x)=x+1、n(x)=0和Ui(x1,x2,xn)=xi出发，通过利用复合、递归算子得到的原始递归函数以及利用复合、递归与取极小算子得到的部分递归函数与递归函数描述可计算函数。递归函数是计算理论的核心概念，因为图灵可计算函数类就是递归函数类，两者完全等价。递归函数是构造更为复杂函数的基础，现代以神经网络为代表的机器学习是一个黑箱算法，可解释性不足，需要一个可被证明的理论作为基础。从递归函数解读深度学习过程，即一层神经网络的输出是下一层神经网络的输入，通过不断地复合与递归层层深入最后得到深度学习训练的结果[3]，递归可以构造出更复杂的函数，从而解决更复杂的计算机科学与工程问题。3）使用两符号与多符号的波斯特图灵机、四元组图灵机、五元组图灵机、整理图灵机描述可计算函数。此处的两符号（0和1）波斯特图灵机接近于我们熟悉的汇编语言，而两符号与我们现在所使用的计算机底层操作的符号是对应的；多符号波斯特图灵机是两符号图灵机的一种推广。现代计算机可以处理的数字、图像、音频、视频等各种形式的数据，其实质也是0和1两符号推广到多符号的扩展形式，形式语言与自动机理论也产生于此。四元组和五元组图灵机是以元组形式描述的产生式规则，其中的状态相当于现代编程语言中的环境；每个产生式的前提（也称为前件）和效果（也称为后件），相当于在不同状态下采取不同的动作需要的前提和产生的效果。整理图灵机是进行各种计算的元语言程序，可以完成各种计算操作，但其存在局限性，如计算机病毒作为一种具有特定功能的算法，同样可以用图灵机或整理图灵机进行描述，整理图灵机模型只限于分析一种单一的算法或程序，如果要分析两个或更多的算法和程序之间的联系，这种模型显然不够。文献[4]从计算机的基础理论模型——图灵机模型出发，提出一种扩展的整理图灵机模型EUTM，极大地简化了计算机病毒传染机制的形式化描述，开辟了计算机病毒传染特性和可传播性形式化描述的新领域，有助于正确地理解计算机病毒。4）使用元语言程序描述不可判定性问题。图灵机根据机器的程序处理初始格局，有的初始格局可能导致停机，有的则导致无限的格局序列，引出停机问题。图灵机停机问题的实质：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机。图灵已经证明，这样的算法是不存在的，即停机问题是不可判定的。停机问题是研究许多不可判定问题的基础，人们往往把一个问题的判定归结为停机问题：“如果问题X可判定，则停机问题可判定”，从而证明问题X的不可判定性。停机问题有多种不同的叙述方式和证明方法，分别适用于具有不同特征的问题，如对于目前人们使用的智能手机，经常会出现某APP运行了计算模型上没有进行定义的操作的现象，导致手机对用户的任何操作都无法作出反应，我们称为“死机”。对于这种“死机”行为，手机开发商设计一个检测软件进行监控处理就是一个停机问题的现实反映。显然，根据上述论述，这样的软件是设计不出来的。5）以产生式规则为基础的图厄系统描述可计算函数。这一部分主要讲述图厄系统识别符号串。在形式语义学中图厄系统实际上被称为文法，在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言实现其编译方法的基础，同时也是形式语义学的基础。形式语义学在自然语言处理、程序语言设计、网络搜索引擎以及计算复杂性上都有重要的影响，如通过设计类似于产生式系统的图厄系统识别需要的符号串，可联想到在网络搜索引擎的文本检索中常常涉及的问题[5]：给定一个单词集合，查找包含一个（或全部）单词的所有文档。搜索引擎是这一过程的通俗示例，搜索引擎使用一种称为“倒排索引”的特殊技术，对网络上出现的每个单词（有1亿种不同的单词）所有出现之处的列表进行保存，有非常大的主存的机器保持这些列表的最常见部分随处可见，允许许多人在瞬间搜索到这些文档。此外，图厄系统还是计算机文法的基础，对于语言的语法分析等也起着重要的基础性作用。6）以单带与多带图灵机描述可计算函数。单带图灵机由3部分组成：一条带、一个读写头和一个控制器。图灵机的格局由当前状态、当前带内容、读写头的当前位置组成。图灵机开始运行后，根据转移函数所描述的规则进行计算，图灵机就从一个格局到另一个格局进行转换。图灵机本质上是一个程序或算法的高度抽象，当给定一个输入x以后，就可以计算出f(x)。除了前面描述的计算模型外，人们还研究了图灵机的各种变型，如非确定的图灵机、多道图灵机、多带图灵机、多维图灵机、多头图灵机、带外部信息源的图灵机等，这些图灵机变型对今天的计算机体系结构设计仍具有重要的指导作用。除极个别情形外，这些变型并未扩展图灵机的计算能力，它们计算的函数类与基本图灵机是相同的，但为研究不同类型的问题提供了方便的理论模型。上述图灵机的组合变型演化出当今的计算机硬盘存储表示形式（通过磁头、磁道、扇区等参数），而多带图灵机是研究计算复杂性理论的重要计算模型。人们还在图灵机的基础上提出不同程度的近似于现代计算机的抽象机器，如具有随机访问存储器的程序机器等。
3计算理论启发式案例教学
计算理论课程讲述多种模型，一方面是为了让学生了解与掌握计算理论知识并证明它们的等价性，因而论证Church-Turing问题；另一方面也是为了训练学生创新思维，打破思维框架束缚，培养学生从不同角度解决问题的能力。各种模型具有不同的特点，针对不同的问题各有其价值。不同研究者在解决同一科学问题时，会给出不同的算法：这些算法或者演化于某些著名学者提出的基本方法，或者是自己提出的一个不同于常人的方法（这也相当于一个个小的具有针对性的计算模型）。之所以有脍炙人口的三国演义产生，就在于有陈寿的三国志，三国志相当于我们上述描述的某一“计算模型”，而三国演义就在此“计算模型”下加上民间传说在罗贯中的笔下演化而来的，妙笔生花（从计算机科学角度看就是组合新的理论与方法到原有模型中用于解决新的问题）更加接地气。以具体案例对启发式案例教学作进一步说明如下。案例1：在递归函数的谓词递归性证明中，首先通过使用真值表分析法得到证明过程的特征函数，进一步引入广义德摩根律，并通过启发使少部分学生给出不同于原有教案上的证明方法。案例2：在讲授四元组、五元组图灵机过程中，引入三国演义中的刘备东吴招亲、诸葛亮授赵云3条锦囊妙计的故事展开图灵机的状态变化与操作过程，将深奥的教学内容与大家熟悉的故事巧妙结合，达到寓教于乐的目的。计算理论的讲述一方面可以使学生了解这些计算模型的知识，看到它们的现代应用演化。在教学中，注重启发学生将这种“演化”方法融入自己的科学研究中，利用自己所研究领域先驱学者提出的原创方法加上其他方法及所解决问题的特性解决问题，把“共性”+“特性”解决问题的思想融进计算思维与创新能力的培养过程中。另一方面，在各章不同计算模型讲授过程中，以问题启发学生思考，问题可以是：这些计算模型有什么区别？共同点又是什么？在不同讲述内容中可计算是如何定义的？通过学生思考与教师释疑，学生可意识到同样的问题有不同的解决方法，学会从不同角度思考问题，勇于探索并打破思维框架的束缚，寻求问题新的解决方案，这是创新能力培养的必要过程；同时，学生可在这个过程中充分理解和掌握计算机科学先驱们对问题的定义、方法的描述、性质的验证或证明，这也是今后从事科学研究的研究生应该掌握的必要方法与思维方式。
4结语
关键词：中国古算具图灵机计算思维
中图分类号：TP3-4文献标识码：A文章编号：1672-3791（2013）06（a）-0211-01
在20世纪80年代，我国著名科学家钱学森教授结合我国科学技术发展现状和特点，在人类高级抽象思维领域，尤其是形象思维、辩证思维、创造性思维等方面进行了科学的分析，提出了“思维学”的理念。计算科学是一个与数学模型构建、定量分析方法以及利用计算机来分析和解决科学问题相关的研究领域，它不同于计算机科学（面向计算机和信息处理的研究），也异于传统科学方法——实验和理论。思维科学中形象思维学和逻辑思维学与计算科学联系尤为密切，站在思维科学和计算科学相结合的高度去认识计算思维：计算思维是面向计算学科的思维。
1“中国古算具”时期的计算思维
计算思维不是一个新生事物，也不是随着计算机的出现而出现的，这一理念早已存在于我国古代的数学之中。中国的古算具如算筹和算盘等就是体现计算思维这一思想的典型实例。在中国古代，古算具用途仅限于数学计算。人们通过熟记相关口诀，然后以古算具为工具，来进行一些简单的数学计算。这个阶段的计算思维被称之为中国古代计算思维。我国古算具是我国先民们智慧的结晶。十进制计数制是我国古人在计算理论方面的重要发明之一。在世界数学史上，我国是最早使用十进位制的国家，早在商代时就已形成了完善的十进制记数系统。这种记数方法后来逐渐发展成为筹算和珠算中“逢十进一”的十进位计数制，并在秦汉时期形成了完整的十进位计数制，这是计算领域的革命性创造和发明。马克思在其撰写的《数学手稿》中称十进位计数法为“最妙的发明之一”。唐朝末年出现的算盘结合了十进制计数法和珠算口诀，在计算复杂问题和计算速度以及便携性上都有不可比拟的优势，并一直沿用至今。吴文俊院士认为：“数学机械化思想来源于中国古算”。对筹算而言，珠算可以更加突出我国古代数学算法机械化特色。珠算充分利用汉语单字发音特点，将几个计算步骤概括为若干字一句的珠算口诀，计算时呼出口诀即可拨出计算结果，整个计算过程类似于计算机通过已编好的程序来执行计算的过程，所以吴文俊教授将算盘算筹称为“没有存储设备的简易计算机”。我们把中国古代计算思维认为是处于萌芽时期的计算思维，这个阶段的计算思维仅仅应用于解决数值计算问题，还未涉及到逻辑计算等其他计算问题，而且还未建立起系统的理论和方法体系。
2“图灵机”时期的计算思维
英国科学家艾伦·麦迪森·图灵（AlanMathisonTuring）是现代计算机科学和人工智能的奠基者。1936年，图灵发表了奠定电子计算机模型和理论的文章——《论可计算数及其在判定问题中的应用》，提出了著名的理论计算机的抽象模型——“图灵机”（TuringMachine）和图灵机理论。图灵机是一个逻辑计算机的整理模型，它可以通过编写有限的指令序列完成各种演算过程。整理图灵机正是现代数字计算机的理论原型。图灵证明，凡是图灵机能求解的计算问题便是可计算性问题，实际计算机才能解决；图灵机不能求解的计算问题便是不可计算的问题，即使是大型计算机也无法求解。这就是著名的“可计算性理论”。可计算性理论是现代计算机科学的基础理论之一。“判定问题”是数理逻辑中的一个重要问题，它是判断是否存在一种有效可行算法能求解某一类问题中的任何具体问题的研究课题。现代解决不可判定问题的理论，来源于图灵对图灵机“停机问题”的不可判定性证明。1936年图灵证明，解决“停机问题”的整理算法是不存在的，即不存在一个整理图灵机可以判定任意给定的图灵机对任意输入是否会停机。此外，“判定问题”与“可计算性理论”之间关系密切：可计算的问题，一定可判定；可判定的问题未必可计算。图灵所描绘的“整理图灵机”是现代计算机的雏形。相比中国古算具而言，图灵机首次实现了用机器来模拟人类思维进行数值计算的过程，实现了手工计算向机器自动机械化计算的跨越式发展。算筹和算盘等古算具是将“程序”放入到演算者的大脑中，然后手工完成整个计算过程的。图灵机是将预先编好的程序存储于控制器内存，将其成为计算机自身的一部分，然后在程序的控制下自动完成计算过程，这是两者之间最重要的区别。此外，中国古算具所能执行的计算任务非常有限，而图灵机的工作过程虽是符号逻辑推理过程，如将存储磁带上的符号换为数字，那整个过程便是数值计算过程。所有的计算和算法都可以通过图灵机来完成。此外，图灵机和中国古算具，体现了一种共同的计算思维方式：面对复杂问题，先将问题数值化，转化为可计算问题，然后寻求有效可行的算法并编写程序，在程序控制下由“计算机”进行运算并在有限步骤内得出最终结果。
3计算思维的传承与发展
从中国古算具的算法化思想到20世纪30年代问世的图灵机和图灵理论，我们可以看出：计算思维不是计算机思维，它不是计算机的产物，更不是一个新概念，而是千百年来计算学科在发展过程中一直遵循传承的一种科学思维方法。在历史的长河中，计算思维必将经历一个由低级到高级逐步成熟完善的过程。从古至今，计算思维是人人都具备的一种技能，并且在实际生产和生活中，人们早已能够利用计算思维去分析问题和解决问题，只不过这种计算思维是无意识的，所以在很长的一段历史时期内，计算思维“深藏闺中无人识”，并未受到人们的重视。直到2006年3月，美国卡内基·梅隆大学周以真（JeannetteM.Wing）教授在美国计算机权威杂志ACM《CommunicationoftheACM》上对计算思维概念进行了清晰系统的阐述，这一概念才引起人们的关注。在国内，中国科学院自动化所王飞跃教授率先将“计算思维”引入国内，提出我们应借“计算思维”之东风，尽快把中国世故人情的“算计文化”转化成为科学理性的“计算文化”。当前，国内外关于计算思维的研究已积极开展并获得了一定的成果，但是对于计算思维的一些基本理论和方法，比如计算思维的概念、特征、原理以及方法等等，这些问题都还没有达成共识，甚至一些研究领域：计算思维课程理论、计算思维能力培养方法理论、计算思维与创新教育理论等问题，还没引起广大学者的关注和重视，一些研究工作有待进一步深入。
参考文献
[1]维基百科：计算科学定义[EB/OL].http：///wiki/计算科学.