二十一世纪是信息时代，以计算机科学为基础的信息技术特别强调算法的重要意义。算法是一种有关自然、人类和计算机的共同语言。因而掌握和应用算法就成为我们的一个必要的任务。我国著名数学家吴文俊院士曾在中国科学院研究生院做过一场精彩的讲演，题为“计算机时代的中国数学”。当主持人最后请吴老用一句话告诉大家，计算机和信息时代的中国数学会怎样时，吴老答到：“用中国的方式来压倒外国的那种方式。”随即引起异乎寻常的热烈掌声。那么什么是“中国的方式”呢？我们说就是算法！

一、什么是算法？

所谓算法就是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类中的每一个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。算法的这些特征，使得计算不仅可以由人，而且可以由计算机来完成。用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。

中国古代数学就引入了利用算筹进行计算的算法，称为“术”。中国古代数学的主要成就多是用算法（术）表述的，如《九章算术》中的“正负术”（在世界上最早引入负数及其运算规则），“方程术”（以线性方程组解实用问题，求线性方程组数值解的算法）；刘徽的“割圆术”（引入了极限观念，求圆周率的算法）；《数书九章》中的“大衍求一术”（求一次同余式组解的算法）和“正负开方术”（求一元高次方程数值解的算法）等等。尤其后两个术已经给出了比较复杂的算法。它们已经具备了前面所说的那些算法的特征。后来的中国珠算的口诀也可以说是一种简易的算法，所解决的问题类是算术运算。现在被称为欧几里得算法的求两数最大公约数的辗转相除法，欧几里得在《几何原本》中只给出这一算法的思想，并没有以算法的形式表述出来。《九章算术》中的“约分术”以明确的算法形式表述出求两数最大公约数的方法。

中国古代早就有“算术”、“算法”等概念，但其含义是指当时的全部数学知识和计算技能，与现代算法的含义不尽相同。英文algorithm一词也经历了一个演变过程，最初写法为algorism或algoritmi，原意为用阿拉伯数字进行计算的过程。这个词源于公元9世纪阿拉伯数学家花拉子米的名字。

古代的计算一般是数值计算。现代计算已远远突破了数值计算的范围，包括了大量的非数值计算，例如检索、表格处理、判断、决策、形式逻辑演绎等。

二、周易中的成卦法极其演算

朱熹注释的《周易本义》（上海古籍出版社，1987年版，第60-61页）给出了要比《九章算术》更早的一段筮法。这段筮法共分三部分，一、成卦法、二、释卦法、三、变卦法。但与数学有关的是成卦法：

大衍之数五十，其用四十有九。分而为二以象两，卦一以象三，揲之以四以象 四时；归奇于扐以象闰，五岁再闰，故再扐而后卦。乾之策二百一十有六，坤之策百四十有四，凡三百有六十。当期之日。二篇之策，万有一千五百二十，当万物之数也。是故四营而成《易》，十有八变而成卦, 八卦而小成……

所谓成卦法，实质上就是通过数字变演决定阴阳爻（用现代术语就是0与1的交替）。将五十根蓍草取出一根不用，其余四十九根名为“用策”。“用策”经二变而二十一演决定一爻，十八变得六爻而成卦。现在来逐步分析：

第一变

第一演 将“用策”四十九任意分为a、b两组。
第二演 从a组取出一策，即所谓“挂一”。
第三演 将a － 1策四、四数之，即“揲之以四”。
第四演 取出第三演之余策，或一、或二、或三、或四。
第五演 将b组取四、四数之，亦即“揲之以四”。
第六演 取出第五演之余策，或一、或二、或三、或四。
第七演 将第二演、第四演、第六演取出之策（一挂二扐之策）合在一起（非五即九）弃之不用，其余之策合在一起（非四十四即四十）以备下一变之用。

第二变

第八演 如第一演。
第九演 如第二演。
第十演 如第三演。
第十一演 如第四演。
第十二演 如第五演。
第十三演 如第六演。
第十四演 如第七演。
第二变弃去之策非四即八，余下备用之策或四十，或三十六，或三十二。

第三变

第十五演 如第一演。
第十六演 如第二演。
第十七演 如第三演。
第十八演 如第四演。
第十九演 如第五演。
第二十演 如第六演。
第二十一演 如第七演。

第三变弃去之策非四即八，所余之策或三或三十六，或三十二，或二十八，或二十四。

第三变结果的四种可能的策数分别是四的九、八、七、六倍。这四个数通常称为“四营数”。三变毕若得营数九、七，则成阳爻，九为老阳，七为少阳；若得营数八、六则成阴爻，八为少阴，六为老阴。于是初爻成。二、三、四、五、上各爻皆依成初爻之法，各经三变二十一演而得。六爻具得而成卦。每卦六爻，每爻需经三变，故得成一卦需经十八变。

上述成卦法为朱熹《易学启蒙》定式。另外，其后的秦九韶在其《数书九章》中所述的演法与朱熹所载的大不相同。秦九韶的演法：总策五十，用策四十九，任意分用策为两组，取其中一组用于演卦，先一、一数之、再二、二，三、三，四、四更新数之。一、一数之自然余一，其他三种数法其余数亦只能是一、二、三、四这四个数字。秦九韶在这里把“揲之以四”理解为一、一数之，二、二数之，三、三数之，四、四数之。因为揲一必余一，不必数，径直“挂一”称揲二、揲三、揲四三次重数为“三变”。关于如何确定爻之阴阳，秦氏说得不甚清楚。最简单的方法是视四揲的总余数的奇偶决定爻之阴阳，偶数得阴爻，奇数得阳爻。或将四揲总余数数四、四数之，所余必为一、二、三、四。若余一，得老阳；若余二、得少阴；若余三，得少阳；若余四，得老阴。

三、现代的算法

在20世纪以前，人们普遍认为，所有的问题类都是有算法的，正是为了得到判定一切科学命题，起码是一切数学命题真假的算法，莱布尼茨开始了数理逻辑的创立工作。但是20世纪初，人们发现有些问题虽经过长期的研究，仍然找不到解决它们的算法。例如希尔伯特第10问题，半群上的字的问题，谓词演算中的任一闭合公式是否为一定理的问题等等。因此，人们怀疑这些问题找不到解决它们的算法。为了证明解这些问题的算法不存在，就要求把算法概念予以精确化，使其能作为数学对象来处理。但是在这之前数学界对算法只有朴素的直观概念，并无精确的定义，因此产生了建立算法的精确的数学定义的问题。20世纪30年代这个问题才得到解决，先后出现了算法的几个等价的数学定义，其中最重要的是递归函数、图灵机、正规算法等。

1934年，哥德尔最先提出算法的数学定义（一般递归函数定义），克林把它具体化，建立了等式演算，从而定义了递归函数，不久就证明了递归函数与丘奇提出的λ-可定义函数（1933年）的等价性。同时，图灵也引进了著名的图灵机来描述算法，继而也证明了图灵机可计算函数与递归函数的等价性。丘奇在知道图灵机以前就认为递归函数或λ-可定义函数是算法可计算函数的精确的数学描述，但无法证明它们的等价性，因而丘奇建立了一个不能证明的论题：一切算法可计算函数都是递归函数，即二者是等价的。后来称之为“丘奇论题”。克林曾怀疑存在非递归的算法可计算函数，但他无法构造出反例，也就接受了丘奇论题。1936年图灵也独立地提出了丘奇论题的观点，次年证明了图灵机可计算函数与λ-可定义函数的等价性。由图灵机可计算函数与递归函数及λ-可定义函数的等价性，丘奇论题亦可表述为：一切算法可计算函数都是递归函数或图灵机可计算函数或λ-可定义函数。由于图灵机的定义很符合人们对算法的直观经验，因此哥德尔在见到图灵机后也接受了丘奇论题。

丘奇论题为什么不能证明？因为“算法可计算”（“能行可计算”）是一个未经严格数学定义的概念，而“递归函数，’（以及图灵机，λ-可定义函数）却是精确定义了的数学概念，因此无法证明它们的一致。而事实上，丘奇论题的功能正在于对“算法可计算”这个含混的概念精确化、严格化，而且至今也没有发现反例，所以人们仍然接受它。后来马尔可夫提出了“正规算法”（1947年），波斯特提出了“首尾算法”（1943年），它们也是常用的算法定义，并且也都与递归函数定义等价。随着计算机科学的发展，人们开始要求在符号串上直接定义算法。20世纪60年代初出现了几个等价的定义，其中中国数理逻辑学家胡世华于1956年在《数学学报》上发表的“一种递归式的原始递归性”，最早给出了“递归算法”定义。

现在我已经证明了成卦法与图灵机具有等价性。