1.1 计算

计算可以说无处不在，从日常生活费、购房费及装修成本的规划和结算到我们熟知的卫星云图、天气预报的运用都涉及计算。如今学科繁多，涉及面广，每个学科都需要进行大量的计算，与古代结绳计数不同的是，当今的计算是指使用计算机来进行大量的统计、处理、转换操作：天文学研究组织需要计算机来分析太空脉冲（pulse）及星位移动；生物学家需要计算机来模拟蛋白质的折叠（Protein Folding）过程，以发现基因组的奥秘；药物学家想要研制抵抗癌症或各类细菌与病毒的药物、医学家想找出防止衰老的新办法；数学家想计算最大的质数和圆周率的更精确值；经济学家要用计算机分析计算在几万种因素考虑下某个企业、城市、国家的发展方向，从而给出正确的宏观调控建议；工业界需要准确计算生产过程中的材料和能源的耗费量，加工与时间配置的最佳方案。由此可见，人类未来的科学，时时刻刻离不开计算。

1.1.1 什么是计算

早在2500年前，古希腊数学家、哲学家毕达哥拉斯（Pythagoras，约公元前572—公元前501）就说过“凡物皆数”，意思是万物的本源是数、数的规律统治万物。很早以前我国学者认为，对于一个数学问题只有当确定了其可用算盘解算它的规则时，这个问题才算可解。这也是古代中国的算法化思想。它蕴含着中国古代学者对计算的根本问题——能行性问题的理解。这种理解对现代计算学科的研究仍有重要的意义。

由此看来，计算的概念由来已久，但在大众的脑海中“计算”是一个数学概念，人类很早就学会了加、减、乘、除等运算，但直到20世纪30年代，由于哥德尔、邱奇和图灵等人的工作，人们才对计算的本质有了清楚的理解，进而形成了一个专门的数学分支，即递归论和可计算理论，并因此导致计算机科学的诞生。

简单地说，计算就是依据一定的法则对有关符号串进行变换的过程。进一步理解：从一个已知符号开始，按照一定的规则，一步一步地改变符号串，经过有限步骤，最后得到一个满足预先规定的字符串，这种变换过程就是计算。例如，1+1=2，就是一个数值计算；两字母和汉字均用二进制数来表示，这种运算称为非数值计算。以汉字“保“为例，通常汉字的转换过程是“输入码（bao）-国标码（3123H）-机内码（B1A3H）-字形码（保的字形编码）”。首先键盘输入拼音“bao”，然后经过变换会得到预先规定的汉字“保”，这就是一个非数值计算。类似地，文字识别、图形图像处理等也都是计算，因为它们都是一种符号变换过程。

1.1.2 什么是计算的本质

根据图灵的研究，直观地说，计算就是计算者（人或机器）一步步改变一条两端可无限延长的纸带上的一串0和1的执行指令，在经过有限步骤后，得到一个满足预先规定的符号串的变换过程。图灵用形式化的方法成功地表述了计算的本质。

抽象地说，计算的本质就是递归。数学家们已经证明，凡是可以从某些初始符号串开始在有限步骤内得到计算结果的函数都是一般递归函数。或者说，凡是可计算的函数都是一般递归函数（计算机科学中，递归函数是一类从自然数到自然数的函数，其在某种直觉意义上是“可计算的”）。至此，人们才弄清楚计算的本质，以及什么是可计算的、什么是不可计算的等根本性问题。例如，若m和n是两个正整数，并且m≥n，则求m和n的最大公因子的欧几里德算法，可表示为如下步骤。

① 求余数。以m除n得余数r。

② 判断余数r是否为0。若r=0，计算结束，n即为答案；否则转到步骤3。

③ 互换（递推）。把n的值变为m，r的值变为n，重复上述步骤。

依照以上三个步骤，可计算出任何两个正整数的最大公因子。这时可以把计算过程看成执行这些步骤的序列。可以看出，计算过程是有穷的，而且计算的每一步都是能够机械实现的（机械性）。因此，可以认定：任何两个正整数的最大公因子是可通过计算获得的。

1.1.3 计算与算法

在进行可计算问题研究时，需要用到一个与计算紧密联系的概念，那就是算法。算法也称为能行方法或能行过程，是求解某类问题的方法和步骤，由一组定义明确且能机械执行的规则组成。计算的目的由算法实现，算法的执行由计算完成。也就是说，计算过程就是执行算法的过程，而算法的过程正好是可以在计算机上执行的过程。从算法的角度讲，一个问题是不是可计算的，与该问题是不是具有相应的算法的答案是完全一致的。

总之，计算或算法的观念在当今已经渗透到宇宙学、物理学、生物学、经济学和社会学等诸多领域。计算已经不仅是人们认识自然、生命、思维和社会的一种普适的观念和方法，还是一种新的世界观。