计算与认知《计算模拟与认知的强等价性》

这本书的精华可以浓缩为一个定义，即作者对计算过程的强等价性的定义：恒定的计算复杂性与固定的资源使用（原文如此，实际上按照作者后面的定义，两者是从属关系，不能并列使用）。作者提出，直觉上的“相同算法”的概念是次要的，复杂性等价才是评价一个模拟过程（即计算模拟）与有机体（即人类认知）的第一标准。弱等价在此书中语焉不详。

不同程序之间的某些差别之于复杂性等价是无关紧要的，因为只要两个不同程序之间存在拓朴对应关系，它们可以被看做是复杂性等价的。只要每一个操作所需要的步骤（归根到底还是时间）和时间是独立于输入的，这些操作也是复杂性等价的。

使用的资源量也是评价复杂性等价的重要指标（空间上的）。这个概念包括机器使用的基本周期、时间长度（又与前面的概念交叉了，时间也是一种资源，没错，但我觉得作者最好将空间资源与时间资源的概念区分）、用到的存储量。

以前人们谈论计算的复杂性往往是从时间复杂性的角度。例如，排序算法的效率通常是用多项式函数的阶数表示，给n个项目排序有许多不同的算法，数量与nlogn成正比，从它们的时间复杂性角度看，它们是等价的算法，但它们却不是作者所定义的复杂性等价。因为它们使用的资源量是随着排序元素的分散度（维度）变化的，或随着被排序表中的元素的增加而变化。

注意：计算的复杂性等价只是强等价的必要条件，而非充分条件。