6 结 构

6.1 引言：基本概念

本章主要介绍和说明一些经典的数字计算组织或“结构”，并对其进行分类。说计算机如何组织，就是说信息如何存储，以及什么决定了信息如何在系统中运作等等，并不关注计算机由何构成（继电器、真空管、转换器等），也不关注计算机运行了什么程序。有点像计算机的设计或蓝图，就像建筑的蓝图一样，并不关心材料细节和居住者的信息。但在我们开始研究计算机结构之前，首先需要弄清两组重要概念的区别。

算法/有效步骤与程序

我们首先需要对“算法”或“有效步骤”与“程序”作出严格区分。算法（或有效步骤）的本质是确保获得某一结果的一系列步骤。更精确地说，它是一组预先定义好的有限步骤序列，每一个步骤只占用有限的存储和时间完成，根据任何有限的输入得到某一结果。程序是指某种（编程）语言的有限指令列表。程序通常用于编码算法，可以认为程序能够运行算法。因此，任何运行程序的设备都能执行有限数目的指令，每个指令占用有限内存和有限时间，然后最终达到某一结果终止（实际上，它当然可以像文字处理器一样，等待其他指令的输入）。算法与程序之间的关系就像数（number）与数字（numerals）的关系。一个数可以由多种数字表示（如阿拉伯数字、罗马数字以及二进制数字），125就像简单算法可以由不同的编程语言（如Basic，pascal，prolog）编写为多种不同程序一样。也可以这样认为，程序与算法之间的关系可以比作词语（声音、形状）与其意义之间的关系——不同语言中不同的词语可以具有相同的意义（如cat，katy，chat）。所以，某个程序有缺陷并不意味着算法有缺陷，很可能是编译它的语言出现了问题。

弱等价与强等价

我们还要区分两种算法“等价”的不同情形。说两种算法“弱等价”是指，给两个算法相同的输入会得到相同的输出。例如，有两种有关乘的算法，输入32*17，都会输出544。如果所有输入都会得到相同的输出，那么就可以说两种算法“弱等价”。但两个有关乘的算法得出结果的过程却可能不同。例如，第一种算法可能是32自身相加17次得到——可由一个加法器和一个计数器实现，这种算法称为连续增加法。

首先是2乘7，向左进1位，然后3乘7加1，得到224。然后是32乘1得到32，最后224百十位加上32得到554，如上所示。我们注意到，这个方法首先是用32乘以17的一部分即7，然后再乘以17的另一部分即10，然后把这两个部分的结果加和得到最终结果，显然把这种方法称为部分乘积加和法是非常合适的。这种方法和连续增加法得出相同的结果——弱等价，即用不同方法得出相同答案。两种（或更多）算法强等价是指，不仅相同输入得到相同结果，而且它们的处理过程也是一样的，也就是说它们所有的中间步骤是一样的。显然，（1）如果一台机器运行的步骤另一台机器没有，那么可以直接说它们不是强等价。间接地，（2）也可从“复杂特性”中得出两台计算机的不同。例如，两台计算机都计算数量级较大的数的乘积，数字逐渐变大时，其中一台计算机处理的时间成比例增加，而另一台计算机处理时间并不成比例增加。或者从它们占用内存的大小或出现错误的次数判断两台机器的不同（参见pylyshyn，1979）。我们将会看到，强等价和弱等价的区别对于评估认知功能的计算模型在心理学上的可行性具有重要意义。我们想要得到某个模型，并不仅仅看它的认知功能能够做什么，还要看它的认知功能发挥作用的方式。心理实验就是典型地通过测量反应时和错误率，对某些认知功能及其模型的强等价测试。