1.1.3 计算的需要及其局限性
几乎在整个历史进程中，人类都主要是依靠大脑来进行计算的。分析一下采用纸和笔进行手工计算的过程，如图1.1所示。纸相当于存储部件，其基本目的是信息存储。在纸上的信息，可以包括进行计算时应当遵循的一系列指令（即算法和程序），以及所用的数据，计算过程的中间结果和最终结果都记录在纸上，必要的计算过程在大脑中进行，大脑可以被称为处理器，完成两种主要功能：控制功能（即解释指令并保证以正确的顺序执行）和执行功能即进行诸如加法、减法、乘法和除法等具体的计算）。但是，随着计算的规模和复杂程度的不断增长，这种计算存在着严重的不足：计算速度有限，计算容易出错。因此，人类借助于计算机来完成更快、更精确、更复杂的计算，其计算过程如图1.2所示。这里，存储部件（M）相当于手工计算所用的纸，用来存放指令和数据；中央处理部件（CPU）由程序控制部件（PCU）和算术逻辑部件（ALU）构成，相当于人的大脑，程序控制部件解释指令并按顺序排好，算术逻辑部件执行指令。比较手工计算和借助计算机计算的过程，人们不难发现，其最显著的差别是信息的表示方式不同。人类使用的是有着大量符号的正常语言，通常又以十进制的形式表示数。而在计算机中，信息的存储和处理均以二进制形式进行，只用0和1两个符号表示。为了在机器和用户之间提供通信，就需要在计算机语言与人类语言之间提供信息转换的手段，这就是图1.2中输入/输出（I/O）设备的主要功能。
图1.1 人工计算过程
图1.2 计算机计算过程
通过上述分析，可以把计算理解为求某个函数f（x）的值，这里x是给予的输入数据，z=f（x）是要求输出的数据。x，z，f均可给予广泛的解释，x，z可以代表数、词句、信息文件等等，f可以是数值计算、定理证明、文件更新规程等等。为了用一特定计算机求f（x），必须能将f表达成一串函数f1，f2，…，n，这些函数可以由计算机指令系统来确定。指令系统就是计算机能够执行基本功能的集合。f1，f2，…，fn就可以理解为对f（x）求值的程序。基本操作的序列：
y1=f2（x）
y2=f3（x）
︙
yn-2=fn-1（x）
z=fn（yn-1）
可以作为计算的一个形式定义。
那么，所有的问题是否都可以计算呢？
1936年，英国数学家图灵提出了计算机抽象模型——Turing机。人们在对Turing机研究的基础上，得到了如下的概念和认识：
①任何给定的x，如果f（x）可以由Turing机在有限步内完成计算，则称函数是有效的或可计算的。实际上，很多计算机应用问题都是可计算的。
②存在不可计算的函数。例如，没有经验的程序员可能会编出一个在一定输入条件下无法停止的程序。又如，编写一个能测定任何程序是否停止的调试程序，这几乎是不可能的，因为只有当这个程序应用到全部可能的程序类时，这个说法才成立。这两个问题都属于不可解问题或不可计算的。
③即使问题是可解的，但也有难处理的或不现实的。例如，计算机不能实现任意大的二进制数的乘法计算。有大量的“困难”问题在实际中很重要，但在计算过程中其需要的存储空间太大以及计算时间太长，以致没有一台实际的计算机能够解它们。这样的结论，实际上是基于下面两个理由：一是计算机不可能存放所有可能的问题的答案；二是计算机处理信息的速度是有限的。
例如，Hanoi塔问题。在一个基座上竖立着3根轴A，B和C，轴A上套着n（n=64）个圆盘，按直径的递减顺序由下而上叠放在一起，如图1.3所示。要求一次一个地把这些圆盘从A移到B，但在任何情况下都不允许把大的圆盘叠放在小的圆盘上面，在移动过程中可以借助C轴来暂时存放圆盘。
图1.3 Hanoi塔
这个移动过程是一个规模为n个圆盘的移动，可以进一步分解为规模为两次n-1的移动和一次规模为1个圆盘的移动，而每个规模为n-1的移动规则与规模为n的移动规则相同。移动过程可以描述为如下算法：
这个过程实际上是一个递归算法，用数学归纳法不难证明这个算法的正确性。但这里关心的是计算机是否能够解决一个任意大小的n的Hanoi塔问题。为了回答这个问题，不妨把上面的移动过程中的移动次数表示为如下的递归方程：
然后解这个递归方程，可以得到移动次数为：
T（n）=2×T（n-1）+1
=2×（2×T（n-2）+1）+1
=22×（2×T（n-3）+1）+21+20
=23×T（n-3）+22+21+20
…
=2n-1+2n-2+…+22+21+20
=2n-1-1
通过计算可得，64个盘的移动次数为：264-1=18446744073709551615次。假设一台计算机1μs可移动一次圆盘.那么把这个算法转换成计算机程序来完成移动64个圆盘所需的时间将近60万年。
显然Hanoi塔问题虽然有解决算法，但是属于难解问题，即使计算机的速度由于技术的改进有所增长，解决类似问题仍然存在着局限性。
这就给出一个启示，单纯依靠提高计算机的速度是不能从根本上解决这类问题。也就是说，在运用计算机解决实际问题的过程中，不仅要考虑计算机硬件技术的应用，更重要的是要考虑计算机软件方面的技术方法和过程的应用，应该从系统的角度考虑问题解决的途径。