Foundations Of Cognitive Science

Relative Complexity Evidence

One of the key goals of cognitive science is to develop theories that are strongly equivalent with respect to to-be-explained systems. This requires that evidence be collected to defend the claim that the model and the to-be-explained system are carrying out the same procedures to compute a function.

One type of evidence that can be used to defend this claim is called relative complexity evidence. Imagine that someone is proposing that a Turing machine is a strongly equivalent model of how children do mental arithmetic. To collect relative complexity evidence concerning this claim, we could present a number of different addition problems to the Turing machine, and then rank order them in terms of the number of processing steps that each problem required. We could then present the same problems to a group of children, and rank order the difficulty they caused the children on the basis of reaction time taken to solve the problems. If the two systems are strongly equivalent, then we would expect the same rank-orderings to be obtained for both the Turing machine and the children. If they are not strongly equivalent (as we would expect in this example), then differen rank-orderings would emerge because different procedures are used to solve the problems.


  1. Pylyshyn, Z.W. (1984). Computation and cognition. Cambridge, MA: MIT Press.