Three Challenges to Chalmers on Computational Implementation*
 Author: Sprevak Mark
 Publish: Journal of Cognitive Science Volume 13, Issue2, p107~143, June 2012

ABSTRACT
The notion of computational implementation is foundational to modern scientific practice, and in particular, to explanation in cognitive science. However, there is remarkably little in the way of theoretical understanding of what computational implementation involves. In a series of papers, David Chalmers has given one of our most influential and thorough accounts of computational implementation (Chalmers, 1995, 1996, 2012). In this paper, I do three things. First, I outline three important desiderata that an adequate account of computational implementation should meet. Second, I analyse Chalmers’ theory of computational implementation and how it attempts to meet these desiderata. Third, I argue that despite its virtues, Chalmers’ account has three shortcomings. argue that Chalmers’ account is (i) not sufficiently general; (ii) leaves certain key relations unclear; (iii) does not block the triviality arguments.

KEYWORD
Physical Computation , Implementation , Chalmers , Computational Explanation

1. Introduction
What does it mean for a physical system (e.g. a brain, a desktop computer) to implement a computation? The first step in answering this question is usually to talk about a special relation—
implementation —between abstract mathematical computations and physical systems. Implementation is understood as the bridge between the realm of abstract mathematical computations and the nuts and bolts of concrete physical systems. But what is the implementation relation, and how does it work? What are the necessary and sufficient conditions for computational implementation to obtain? Is computational implementation a matter of objective fact, or is it only something that is in the eye of the beholder? Despite our widespread use of the notion of computational implementation in explanation, and despite its foundational role in cognitive science, the concept has received remarkably little attention. Often computational implementation is treated as an explanatory primitive: other things are explained in terms of it, but it itself remains unexplained. In a series of papers, David Chalmers has done more than anyone else to provide an account of what computational implementation involves (Chalmers, 1995, 1996, 2012).In this paper, I aim to do three things. First, I outline three desiderata that an account of computational implementation should meet. Second, I describe Chalmers’ theory of computational implementation and how it attempts to meet those desiderata. Third, I argue that despite the virtues of Chalmers’ account, there are three challenges that it faces. I argue that Chalmers’ account is (i) not sufficiently general; (ii) leaves certain key relations unclear; (iii) does not block the triviality arguments. These critical remarks should not take away from the spectacular progress that Chalmers has achieved in articulating the notion of computational implementation. My claim is only that, as it stands, Chalmers’ account falls short of a complete account. Some distance has yet to be travelled before we reach an adequate account of implementation, and in particular, before we have a clear view of the metaphysical commitments involved in using computational implementation in explanations in cognitive science.
2. What is at stake in a theory of implementation?
Before starting, it is worth pausing to consider what is at stake when one gives an account of computational implementation. As noted above, the notion of computational implementation is often treated as an unanalysed explanatory primitive. This is particularly evident in the daytoday practice of cognitive science where the notion rarely receives explicit articulation. Over the past forty years, cognitive science has scored spectacular explanatory and predictive successes without explicitly articulating the notion of computational implementation, and cognitive science appears to have the potential to score plenty more successes in the future. So one might wonder why one should even bother looking for a theory of computational implementation. If many cognitive scientists have not found the nature of computational implementation a particularly pressing problem, why should we?
There are at least three interrelated issues which jointly motivate a theory of computational implementation.
(R1), (R2), and (R3) are three major motivations for a theory of computational implementation. (R1), (R2), and (R3) also provide three desiderata for such a theory to serve the needs of cognitive science. A notion of computational implementation that is adequate to the needs of cognitive science should at least be: (D1) clear, (D2) avoid the triviality arguments, and (D3) provide a naturalistic foundation. If an account of implementation falls short in any one of these areas, then we have reason to complain.
Chalmers achieves a great deal of progress in all three areas. However, I argue that his account does not fully satisfy all three desiderata. It falls short in three main areas: (i) it is not sufficiently general and leaves certain features of the implementation relation unclear (D1), (ii) it does not block the triviality worry (D2), and (iii) it does not secure naturalistic foundations for cognitive science (D3). Chalmers makes a major step forward in explaining the nature of computational implementation, but the resulting account is not complete.
Before assessing Chalmers’ account of implementation, it is important to have two other pieces in play. In Section 3, I describe the account on which Chalmers builds: what I will call the Standard Position on computational implementation. In Section 4, I describe the triviality arguments that render the Standard Position untenable, and which motivate Chalmers’ position.
1For examples of the pull of antirealism about computation, see Bringsjord (1995); Hardcastle (1996); Putnam (1988); Searle (1992).
3. The Standard Position on implementation
Despite the widespread use of computational implementation as an explanatory primitive, it would not be right to say that there are no widelyheld theoretical beliefs about the nature of computational implementation. On those occasions when computational implementation is called into question, practitioners tend to produce a prototheory—a theory that is almost certainly correct in many respects. The prototheory says that computational implementation involves a
mirroring relation between anabstract mathematical formalism and thephysical states and transitions of a physical system. Chalmers provides a nice statement of the view:I will call this the
Standard Position (SP) on computational implementation. SP provides a plausible starting point for a theory of computational implementation. Chalmers’ account can be understood as a sophisticated elaboration of SP.How does SP apply to a particular case? Chalmers applies SP to finite state automata (FSAs):
A physical system implements an FSA just in case the formal structure of that FSA is mirrored in the physical structure of that system. The notion of mirroring is identified with that of a
structurepreserving mapping , a move which I take to be part and parcel of the Standard Position. Physical states of physical systemP are paired (mapped) to each formal state of the FSAM . IfP ’s physical states follow the same sequence of transitions as the counterpart formal states ofM to which they are mapped, thenP implementsM . In other words, if a mapping exists betweenP andM that preserves the structure of the statetransitions ofM , thenP implementsM .Straight off one can see that SP meets two of the desiderata on a theory of implementation:
clarity (D1) andnaturalistic foundations (D3). SP appears to give clear conditions for computational implementation. It explains computational implementation in terms of other concepts, primarily that of a structurepreserving mapping. At the very least, this unifies computational implementation with other notions involving structurepreserving mappings:measurement (Dresner, 2010), andmodeltheoretic interpretation (Copeland, 1996).SP also secures
naturalistic foundations for cognitive science. Whether a physical system implements a computation depends only on whether a structurepreserving mappingexists between the physical system and the formal computation. It does not depend, for example, on whether someonejudges such a mapping to exist, or whether itsuits their interests to look for such mapping, or whether the mapping appears to themperspicuous . SP does not require reference to any subject or agent at all. Computational implementation is a purely objective matter: either a mapping between the computational formalism and the physical system obtains, or it does not.Unfortunately, SP spectacularly fails to meet the third desideratum:
blocking the triviality results (D2). Chalmers’ theory of computational implementation can be seen as a way of revising SP to get around this problem while keeping the other two virtues. Before considering the way in which Chalmers revises SP, it is important to get the triviality arguments clearly in view.4. Triviality arguments
There are two major triviality arguments: an informal argument from Searle (1992) and a formal argument from Putnam (1988).
4.1 Searle’s informal triviality argument
Searle (1992) asks one to imagine one’s desktop computer running Microsoft Word. What is happening? There are many physical state transitions inside the desktop computer: transitions in electrical activity, transitions in thermal activity, transitions in vibrational activity, transitions in gravitational activity. According to SP, the computer implements Microsoft Word because one of these patterns of activity—the pattern of electrical activity—has the right structure. If one were to build another physical system, perhaps made out of different materials (e.g. brass wheels and cogs), which had physical transitions with the same structure, then it too would implement Microsoft Word. Now consider a brick wall behind the computer. Despite its static appearance, on a microscopic level a brick wall is teeming with physical state transitions. Within the wall there are physical transitions of vibrational activity, electromagnetic activity, atoms changing state, subatomic particles moving around—a typical wall contains more than 10^{25} atoms, which for one thing are all in microscopic motion. Searle claims there is
so much physical activity inside a brick wall that there is almost certain to be at least one pattern of activity with the same structure as that inside the desktop computer. Therefore, according to SP, a brick wall implements Microsoft Word.Similar reasoning appears to show that almost any macrosize physical system implements any computation one likes. Chalmers (2012) identifies two important computational theses in cognitive science:
computational sufficiency andcomputational explanation. Computational sufficiency claims that implementing the right computation is a sufficient condition to possess a mind. If the triviality argument is right, then computational sufficiency would entail an absurdly strong form of panpsychism: brick walls would have minds just as much as we do.Computational explanation describes the methodology above: one explains why we have the particular cognitive processes we do by appeal to the fact that our brains implement particular computations.2 If the triviality argument is right, then this explanatory methodology has to be abandoned. One could not explain our distinctive cognitive processes in terms of the brain implementing particular computations because the brain, like every macrosized physical system, trivially implements almost every computation.4.2 Putnam’s triviality argument
One might have two immediate concerns about Searle’s argument. First, one might be unmoved by his claim that a brick wall contains some pattern of physical transitions with the same structure as Microsoft Word. One might reasonably insist that the burden of proof is on Searle to demonstrate that such a pattern exists. Second, one might think that his triviality argument only applies to macrosized physical systems. Perhaps if one restricts attention to smaller or simpler physical systems, one can regain a nontrivial form of computational implementation.
Putnam (1988) presents a triviality argument that neatly scotches both of these worries. Putnam offers an argument that finds the relevant pattern of physical transitions that mirror almost any computation one likes in almost any physical system one likes.
Putnam states his argument in terms of finite state automata (FSAs). Pick an arbitrary FSA. Putnam chooses a simple FSA,
M , which transits between two computational states,A andB , with the following formal transitions,A →B →A →B . Pick an arbitrary open physical system (say, a rock), and a finite time interval,t _{0} tot _{n}. For Putnam’s argument, an open physical system is a physical system that is not shielded from, and so remains in causal interaction with, its environment. Almost all physical systems in which we are interested are open in this sense. Next, consider thephase space of the rock over time. The phase space is the space of every possible value of every one of the rock’s physical parameters. Over time, and even though the rock may appear to our eyes to be unchanging, the rock will trace a path through its phase space as its microscopic physical parameters evolve. Its microscopic physical parameters will evolve both due to endogenous physical factors (internal atoms changing state, vibrations, atomic decay, etc.), and because of external causal influences (gravitational, electromagnetic, vibrational influences, etc.) Putnam argues that among these external influences are external ‘clocks’: causal influences that cause the rock never to return toprecisely the same set of values of its microphysical parameters in the course of its evolution.Consider the rock’s trajectory through its phase space from
t _{0} tot _{n}. Since the rock will not revisit precisely the same point in phase space, its trajectory from t0 to tn will not contain loops. Putnam divides the rock’s path through its phase space into a journey through four regions, labelledr _{1},r _{2},r _{3},r _{4}. These regions pick out the set of the rock’s physical state in four time intervals betweent _{0} andt _{n}. Since the rock’s physical state is entirely characterised by its position in phase space, regions in phase space provide an ideal description of the physical state of the rock. We can say that in the first time interval, the rock is in physical stater _{1}, in the second, it is physical stater _{2}, in the third, in physical stater _{3}, and in the fourth, in physical stater _{4}.We can now ask about the physical
transitions that the rock exhibits over he interval. One sequence of physical transitions that the rock exhibits is:r _{1} →r _{2} →r _{3} →r _{4}. But, Putnam observes, this isnot the only sequence of ransitions exhibited by the rock. The rock also exhibits the pattern:r _{1} ∨r _{3} →r _{2} ∨r _{4} →r _{1} ∨r _{3} →r _{2} ∨r _{4}. In other words, as well moving between our regions of phase space (r _{1},r _{2},r _{3},r _{4}), the rock also oscillates between wo disjoined regions of phase space (r _{1} ∨r _{3} andr _{2} ∨r _{4}). In principle, here is nothing wrong with identifying a physical state with a disjunction f unconnected regions of phase space. That is how many perfectly legitimate hysical states types are characterised, e.g. net thermal energy and lectric charge of the rock. It is also how the physical states of many electronic Cs are characterised, e.g. as disjunctions of electrical signals occurring n various electronic components in different internal locations.3 Now ap physical stater _{1} ∨r _{3} to computational stateA , and map physical stater _{2} ∨r _{4} to computational stateB . Putnam has demonstrated a structurepreserving apping between the physical transitions of the rock and the ormal transitions of FSA M. The physical transitions in the rock mirror the ormal transitions:A →B →A →B . Therefore, according to SP, the rock implements FSAM . Putnam’s mapping trick could be repeated for other FSAs and other open physical systems. Therefore, an unvarnished version f SP appears to commit one to the claim that every open physical system mplements every FSA.2Computational sufficiency, although once an important principle of AI, has now fallen into the background. However, computational explanation remains utterly central to explanation in cognitive science. 3An anonymous referee helpfully points out that many objections to Putnam’s argument hinge on objecting to taking disjunctions of phase space regions. The point above is only that there is nothing wrong in taking disjunctions per se. The objections are rather that some disjunctions are legitimate bases for computational implementation, while others are not. In Section 6, I consider an objection of this kind based around an element of Chalmers’ account that I call the INDEPENDENTCOMPONENTS condition.
5. Chalmers’ solution
The two triviality arguments above show that SP in its bare form cannot be right. Computational implementation must involve more than just a simple mirroring between formal transitions and physical transitions. Chalmers revises SP to block the triviality result while aiming to keep SP’s virtues of clarity (D1) and naturalistic foundations (D3).
It is helpful to divide Chalmers’ revision of SP into three steps.
5.1 Step 1: Transitions must support counterfactuals
One feature of the triviality arguments is that they assume that mirroring a pattern of actual physical activity is sufficient for computational implementation. Putnam’s argument identifies a structurepreserving mapping between the actual evolution of physical states between
t _{0} andt_{n} and the evolution of an FSA. But what if the physical state of the rock had been slightly different: e.g. the rock had been hit by one photon extra att _{0}, or its temperature one trillionth of a degree warmer, or the Sun 1 cm further away? Putnam’s construction is silent about whether the mapping toM would still obtain, and there appears to be no reason to assume that it would. We appear to have identified a potential weakness in the triviality arguments: they exploitaccidental , notcounterfactually robust , patterns of physical activity.Chalmers argues that we should introduce two counterfactual requirements into SP.
First, in order for a physical system to implement a computation, the relevant physical transitions should be
reliable . The transitions should not be at the mercy of small physical changes. If an extra photon arrives that should not disrupt the mirroring between physical states and formal states. Some work would need to go into spelling this out—for example, what counts as reliable is likely to vary with context—but a reliability condition of some sort is clearly required. Second, it should be true that certain physical transitionswould have occurred even if, as a matter of contingent fact, they did not. For example, for a physical system to be anadder , it is not enough that it gives the right answer to every pair of numbers it isin fact asked. It should also be true thatwere it to have been asked a different sum, itwould have given the correct answer. In the case of FSAs, even if certain formal transitions do not figure in the actual history of the system, they should be mirrored in counterfactuals about what the physical system would have done.Initially, Chalmers presented these counterfactual requirements as doing ‘all the work’ in blocking triviality arguments (Chalmers, 2012, p. 331; Chalmers, 1995, p. 398). This was a view that enjoyed widespread currency in the literatureat the time: it was generally assumed that counterfactual conditionals deal a knockdown blow to the triviality arguments (for example, see Block (1995) and Maudlin (1989)). Interestingly, Chalmers later showed that these kind of considerations
cannot block the triviality arguments. Even if SP is strengthened with the counterfactual conditions above, a similar triviality result still obtains (Chalmers, 1996, pp. 316?319). Beefing up one’s account of computational implementation to include counterfactual conditionals is not a silver bullet to deal with triviality worries. It is instructive to see why.In the revised argument, Chalmers (1996) defines a ‘clock’ as a physical component that reliably transits through a sequence of physical states over the time interval. He defines a ‘dial’ as a physical component with an arbitrary number of physical states such that when it is put into one of those states it stays in that state during the time interval. The triviality result for the counterfactuallystrengthened version of SP is that every physical system with a clock and a dial implements every FSA.
The argument involves a similar construction to Putnam’s, but over possible, not actual, trajectories in phase space. In one respect the construction is simpler, since the only states that need to be considered are the physical system’s clock and dial; the other physical states can be safely ignored. Chalmers’ strategy is to identify a mapping between each formal FSA state and a disjunction of physical states [
i ,j ] of the implementing system, wherei corresponds to a numbered clock state, andj to a numbered dial state, and the relevant physical states stand in the right counterfactual relations to each other. Here is the argument.Suppose the system starts in physical state [1,
j ], then it will reliably transit to [2,j ], [3,j ], and so on, as the clock progresses. Suppose, without loss of generality, that the system starts its actual run in dial state 1. The start state of the FSA can then be mapped to [1, 1], and the subsequent formal states in the evolution of the FSA to [2, 1], [3, 1], and so on. At the end of this mapping process, if some FSA states have not come up, then choose one of those formal states as the new start state of the FSA and map [1, 2] to it. Then pair physical states [2, 2], [3, 2], and so on with the formal states that follow in the evolution of the FSA. Continue until all of the unmanifested states of the FSA have been covered. Now, for each formal state of the FSA, we will have a nonempty set of associated physical states {[i _{1},j _{1}], [i _{2},j _{2}], . . ., [i_{n} ,j_{n} ]}. Assign the disjunction of these states to each FSA state. The resulting mapping between formal and physical states satisfies the counterfactuallystrengthened version of SP.It is worth noting that almost all physical systems in which we are interested will have a clock and a dial. A clock could simply be any lawlike sequence of physical changes inside the system. A dial could be the entire trajectory of phase space through which the system travels on a particular run. As Chalmers notes, a clock and a dial could also be easily added just by placing a wristwatch inside the physical system. Clearly, some extra condition needs to be added to solve the triviality problem.
5.2 Step 2: Add input and output constraints
Another striking feature of the triviality arguments is that the computations they consider lack inputs and outputs. Chalmers argues that the triviality results can be avoided, or at least attenuated, if inputs or outputs are added. SP should require that a physical system not only mirror the internal states of the formal computation, but also have appropriate inputs and outputs. There is a
weak andstrong way of reading the inputoutput condition.On the
weak reading, all that it means to have appropriate inputs and outputs is thatthere exists a structurepreserving mapping between the inputs and outputs of the physical system and the inputs and outputs of the formal FSA. Just as a structurepreserving mapping is sufficient to implement internal formal states, a structurepreserving mapping is also sufficient to implement formal inputs and outputs. It is not hard to see that this reading of the condition would do almost nothing to solve the triviality problem. Consider a thin spatial boundary around the implementing physical system. This boundary itself is an open physical system, and it will trace its own (nonlooping) trajectory through phase space over the time interval. As before, one can map disjunctions of regions of its phase space to formal inputs and outputs. It is not hard to construct a similar triviality result.The
strong reading of the inputoutput condition requires more than the existence of a structurepreserving mapping. It also requires that the physical inputs and outputs be of acertain physical type . For example, an implementation of a word processor should take physical key strokes as input, and yield written physical text as output—something a brick wall clearly fails to do. An implementation of a calculator should take buttonpresses as input, and yield written physical numerals as output. The strong reading, unlike the weak reading, does appear to provide defence against a Putnamstyle construction. As a matter of brute fact, a brick wall does not have the right type of physical input and output to be an implementation of Microsoft Word, regardless of the mappings that might obtain.Nevertheless, even on the strong reading, a triviality result still obtains. This triviality result is that any physical system that implements
some FSA with a certain inputoutput behaviour, will implementevery FSA with that behaviour. We must distinguish between physical systems with differentinternal computational structures . Two physical systems may have the same (counterfactuallyrobust) pattern of inputoutput behaviour, but different computational methods for achieving that behaviour. Internal structure matters a great deal to cognitive science. Disagreements often concern the internal computational structure of cognitive processes (classical, connectionist, etc.), rather than their inputs and outputs. A strong inputoutput condition constrains implementation only up to the level of inputs and outputs. It places no constraints on internal structure, leaving it open to Putnam’s attack. As Putnam observes, the inputoutput response would, in effect, collapse cognitive science into a form of behaviourism. Therefore, even on the strong reading, the inputoutput condition still leaves us with the meat of the triviality challenge intact.45.3 Step 3: Move to CSA architecture
The final revision to SP proposed by Chalmers is to replace the FSA architecture with a more complex computational architecture. Chalmers claims that the triviality arguments can be resisted for a type of formal architecture that he calls
combinatorial state automata (CSAs). He claims that once we refocus attention on CSAs, nontrivial conditions on implementation can be obtained.Chalmers concedes that Putnam is right that the implementation conditions of FSAs are trivial in the ways described above.5 Nevertheless, this would be tolerable if nontrivial implementation are secured
for all computational architectures relevant to cognitive science . It was originally a worry about cognitive science that motivated a theory of implementation satisfying (D1), (D2), (D3). If this worry could be dealt with, then much of the heat would go out of the debate. It would then be a further question whether the same desiderata need to be met in other contexts where we rely on computational explanation (arguably, (D3) in many cases would not). Consequently, Chalmers claims that CSAs cover all those computational architectures relevant to cognitive science.6Combinatorial state automata are just like finite state automata except that their states have a combinatorial structure rather than a monadic state structure. Instead of having a single internal state,
S , the internal state of a CSA is a vector of substates, [S _{1},S _{2}, . . .,S_{n} ], where the ith component of the state vector is the ith substate of the system. The state transitions of a CSA are defined by specifying, for each component of the state vector, how its new value depends on the old state vector and an input vector.Chalmers claims that a physical system implements a CSA when the following conditions are met:
This completes Chalmers’ account of computational implementation. Call it SPC. Chalmers claims that SPC meets the three desiderata: it is clear (D1), blocks the triviality arguments (D2), and it provides naturalistic foundations for cognitive science (D3).
4Chalmers (1996, pp. 320–323) claims that SP should be supplemented with the additional condition that inputs would reliably cause the right internal states, even if they do not actually cause such states (effectively combining Step 1 + Step 2). He argues that this allows the inputoutput condition to get a toehold on constraining internal structure, and helps defend it from Putnam’s attack. However, Chalmers goes on to show that a similar triviality result still obtains: any physical system with an input memory and a dial implements any FSA with a given inputoutput behaviour. An input memory is a physical component that goes into a unique physical state for every sequence of inputs. Having an input memory is again not hard to satisfy (Chalmers gives the example of adding a tape recorder to the system). See GodfreySmith (2009, Section 2) for a more detailed discussion of how a triviality result for a combined Step 1 + Step 2 condition obtains under even less exacting conditions. A combined Step 1 + Step 2 condition therefore does not by itself solve the triviality problem. 5Chalmers (1995), pp. 394–395; Chalmers (2012), p. 334. 6Ibid.; Chalmers (1996), p. 324.
6. Three challenges to Chalmers
I will argue that there are three problems with Chalmers’ theory of computational implementation, SPC. These problems are: (i) SPC does not cover all architectures relevant to cognitive science; (ii) SPC leaves certain key features of implementation unclear; (iii) SPC does not block the triviality arguments. I argue that SPC cannot simultaneously satisfy (D1), (D2), (D3).
6.1 SPC does not cover all architectures relevant to cognitive science
Chalmers observes that CSA architectures are
more relevant to explanations in cognitive science than FSAs: FSAs have unstructured internal states, which seem poor formal analogues of human cognitive states (Chalmers, 1996, p. 326).7 However, even if CSAs arebetter models of human cognition than FSAs, that does not show that CSAs are theonly , or thebest , computational architectures for cognitive science. The possibility appears to be open that there are other computational architectures, which are equally, ormore , relevant to cognitive science than CSAs, and for which (nontrivial) implementation conditions have not yet been secured.Chalmers attempts to guard against this worry by claiming that the CSA formalism is capable of accurately describing
any computational architecture. SPC is therefore a perfectly general account of computational implementation. According to Chalmers, it is possible totranslate any other computational formalism into the CSA formalism. SPC can then be applied to that CSA translation, yielding the implementation conditions of the original architecture:It is worth emphasising that Chalmers’ claim is not the relatively modest claim that the CSA formalism can reproduce the
inputoutput behaviour of any other computational formalism.8 Chalmers’ claim is stronger: that theinternal workings of any of computational formalismcan be adequately expressed in the CSA formalism . Call the former claimweakequivalence , and the latter claimstrongequivalence .The weakequivalence claim concerns
what function a given machine computes: the machine’s inputoutput behaviour. The strongequivalence claim concernshow that function is computed: the mechanism by which the machine moves from input to output.9 The weakequivalence claim says that, for any computational architecture, there is some CSA which has the same inputoutput behaviour—that solves the same overall computational task—as the original architecture. Typically, weakequivalence claims are justified by the kind of evidence that Chalmers provides: translation rules, which involve a finite number of steps, that take one from the original architecture to some CSA. Weakequivalence proofs (often called ‘simulation’ or ‘computational equivalence’ proofs) play a major role in mathematical computation theory.Weakequivalence is one thing, strongequivalence is another. The strongequivalence claim requires that at least one of the CSAs which ‘solves the same computational task’ also accurately describes—without loss or distortion in its algorithmic description—
how that task was solved. For architectures to be strongly equivalent, it is crucial that the CSA description accurately captures all computationallyrelevant properties of the original formalism. As discussed above, cognitive science not only cares about the inputoutput behaviour, but also about the method by which the system gets from input to output. Therefore, a weakequivalence proof alone would not be sufficient to justify SPC as a general theory of computational implementation. One would also need to show that the CSA formalism describes, without loss or distortion, the internal computational mechanism by which the original architecture operates. After all, if asked for the implementation conditions of a computerX , it would be no good to reply with the implementation of adifferent (albeit inputoutput equivalent) computerY . We want to know what are the implementation conditionsof a machine that works like X , not the implementation conditions of another computer that solves the same problem in a different way.Whether SPC succeeds as a general account of computational implementation hinges on the truth of the strongequivalence claim: on whether translation of any computational method into a CSA is an accurate description (without loss or distortion) of that computational method. I think that there are good reasons for doubting this claim.
Let us start by examining Chalmers’ postercase of strongequivalence: CSAs and Turing machines.10 Chalmers argues that a Turing machine can be redescribed, without loss or distortion, as a CSA. In the quotation above, he gives a number of translation rules that take one from a Turing machine to an equivalent CSA. For example, the state of the
head of the Turing machine is mapped to the state of some of the elements of a CSA’s state vector. The state of thetape of the Turing machine is mapped to the state of other elements of the CSA’s state vector. Thetransition table of the Turing machine (how the head acts on the tape) is mapped to how some of the state of some of the CSA’s statevector elements depend on the state of other elements inside the CSA’s transition table. Using Chalmers’ translation rules, it seems possible to construct a weakequivalence proof for CSAs and Turing machines. But do the translation rules also establishstrongequivalence? Does the specified CSA accurately capture, without loss or distortion, all the computationallysignificant features of the original Turing machine? Arguably not.There are a number of computationallysignificant features of Turing machines that are lost in the CSA translation. One such feature is a distinction between
data andcontrol . The Turing machine formalism separates data from control: the formalism marks a distinction between the data on which the computer operates (tape states), and the control states that govern changes to that data (head states). The distinction between data and control plays a major role in theoretical and engineering computer science. This distinction is one of reasons why the Turing machine formalism (rather than a purely statebased formalism such as a CSA) is often used to express and categorise different computational methods. Different computational methods are categorised, at a first pass, by the different ways in which they manage data and control. A touchstone of engineering practice that there are tradeoffs between investment of computational resources in control mechanisms versus data structures. These tradeoffs can take subtle forms. But a crude example would be that a Turing machine with a handful of head states could ‘offload’ control information onto data on its tape, thereby performing its computation with a very simple control structure but rich data representations. In contrast, a Turing machine with a large number of head states could do more computational work in the head and get away with sparser and simpler data representations on the tape. Computer science treats these two kinds of Turing machine as imposing different demands on implementation. Data and control structures are assumed to governdistinct physical features of the implementing system. Changes to one may involve modifying the physical logic unit (e.g. the CPU), the other the physical memory bank (e.g. the RAM). They are assumed to involve qualitatively distinct physical components in the system. In short, it is important to both theoretical and engineering computer science to keep data and control elements in the Turing machine formalism distinct, and that this distinction should be reflected in the implementation.Pylyshyn argues that a distinction between data and control is also important to cognitive science:
The distinction between data and control is a
computationallysignificant feature of Turing machines that matters to both computer science and cognitive science.The fundamental idea expressed by SP is that
formal structure should be mirrored in physical structure . Computationallysignificant distinctions and similarities in the computational formalism should be mirrored by physically significant distinctions and similarities in the implementation. What we saw above was that a distinction betweentape states andhead states is a computationallysignificant distinction for a Turing machine:tape states andhead states are treated as formally distinct from each other, but similar amongst themselves. An implementation of a Turing machine should therefore have itstape states andhead states implemented in ways that are physically distinct from each other, but physically similar amongst themselves. For example, the head and tape states should be implemented by distincttypes of physical component . A physical system only implements a Turing machine if it works like a Turing machine. And a physical system only works like a Turing machine if its head states and tape states are implemented in distinct physical ways that are physically similar amongst themselves.The problem is that the distinction between data and control is entirely lost in the CSA translation. Both head states and tape states are just substates alike of a giant undifferentiated state vector. SPC places no constraints that head states and tape states be implemented in distinct physical ways that are physically similar amongst themselves. Indeed, SPC does not even have the resources to state such a condition, since the distinction between a Turing machine’s data and control elements disappears in the CSA translation. Strongequivalence—the claim that the CSA translation captures
every computationallysignificant feature of the original Turing machine formalism—appears to be false. The CSA translation does not preserve a critically important feature of Turing machine formalism: its distinction between data and control.A natural response would be to augment the CSA architecture so that it encodes the distinction between the data and control elements of the original Turing machine. For example, one might introduce within the CSA formalism a distinction between two types of substate of a CSA:
data substates andcontrol substates. The monolithic state vector of the CSA [s _{1},s _{2}, . . .,s_{n} ] would then contain certain ‘highlighted’ elements, which are marked out within the CSA formalism as ‘data’ elements or ‘control’ elements. SPC could then be supplemented with a condition that requires that the ‘data’ and ‘control’ elements of a CSA’s state vector be implemented in distinct physical ways, e.g. by distinct types of physical component.This response is good as far as it goes, but other computationallysignificant differences still threaten a strongequivalence claim. One such feature that a Turing machine’s data is not
random access : if the Turing machine’s head is on square 1, and the machine wishes to read square 15,000, then it must read the state of all intermediate squares first. Nonrandom access memory is a computationallysignificant feature of Turing machines that marks out their computational methods from, say, those of a von Neumann machine. This formal property—nonrandom access memory—does not hold true of CSAs. A CSA’s subsequent state vector can beimmediately determined by any of its current substates without stepping through ‘intermediate’ elements first.A natural response again would be to require that a CSA translation of a Turing machine step through a sequence of intermediate ‘data reading’ states—each corresponding to the original Turing machine reading an intermediate tape square—before the CSA reaches the state that corresponds to the Turing machine ‘reading’ the desired square. This would not be the most efficient way for a CSA to operate, but it would appear to replicate the nonrandomaccess property of the Turing machine inside the CSA formalism.
The problem is that this response locates the formal property—nonrandom access memory—in the wrong place: it locates the formal property in the CSA’s
control element (its contingent rules and transition table), not in thefunctional architecture of the computer. This reveals a wider problem with the CSA translation method described above: it collapses the difference between two qualitatively distinct aspects of the CSA—those that encode thetransition table of the Turing machine, and those are used to simulate the Turing machine’s backgroundfunctional architecture . Just as the CSA’s state vector collapsed the distinction between the Turing machine’s head state and tape state, so the CSA’s transition table collapses the distinction between the Turing machine’s transition table and its background functional architecture. Both are merely features alike of the CSA’s undifferentiated transition table. But the difference between the two matters, both to computer science and cognitive science. For something to implement a Turing machine, it should work like a Turing machine. And for something to work like a Turing machine, there should be a distinction between itscontrol element (its transition table), and its backgroundfunctional architecture . The implementation conditions of a Turing machine should require that the Turing machine’s transition table and its background architectural features be implemented in physically distinct ways that are physically similar amongst themselves. These two properties of Turing machines—functional architecture and control element—are treated as formally distinct but similar among themselves in the formalism, and they should be treated as physically distinct but physically similar among themselves in the implementation. However, there is no way SPC can require this to be true. The difference between these two elements of a Turing machine—functional architecture and control element—simply disappears in the CSA formalism.A natural way to respond is to repeat the ‘highlighting’ trick above. One could augment the CSA formalism to encode a distinction between transitions within the giant CSA transition table. For example, one might explicitly distinguish between
simulation transitions andtarget transitions. Asimulation transition is one that is needed to reproduce some aspect of the Turing machine’s background functional architecture (e.g. to reproduce properties like nonrandomaccess memory as above). Atarget transition would be a transition of that encodes the Turing machine’s transition table (i.e. its control element). A condition could then be added to SPC that these different types of transitions should be implemented in physically distinct ways that are physically similar among themselves (e.g. by different types of physical mechanism). The properties of the physical implementation would then mirror, and preserve the relevant difference between, computationallysignificant features of the Turing machine formalism.This fixes two translation problems, but plenty more remain. There are no shortage of computationallysignificant features of Turing machines that are lost or distorted in the CSA translation: what counts as an atomic operation, what can happen synchronously, and at what stages input or output is permitted. All of these matter to way in which Turing machines work. All characterise the distinctive methods by which Turing machines achieve their behaviour. All should be preserved and reflected in the implementation conditions of Turing machines. And all are distorted or lost in the CSA translation.
A hardheaded solution would be to keep replaying the ‘highlighting’ trick above, augmenting the CSA formalism to capture each and every computationallysignificant feature of Turing machines until all of the relevant formal distinctions and similarities of the Turing machine formalism are captured in an enriched CSA formalism. Conceivably, at the end of this procedure one would represent the computational methods of a Turing machine within an enriched CSA formalism without loss or distortion. SPC could then be revised in light of this CSA formalism, and appropriate constraints placed on physical implementation. We would then have achieved our goal of stating the implementation conditions of a Turing machine using the CSA formalism—albeit a heavily modified and augmented version of the CSA formalism.
But all this has a serious cost.
First, it loses the simplicity and generality of Chalmers’ original proposal. The only way to capture the computationallysignificant features of Turing machines appears to be to revise the CSA formalism to such an extent as to effectively recreate the Turing machine formalism inside it. It appears that there is little or no redundancy lurking in the Turing machine formalism for the original CSA formalism to exploit. But if this is so, then it appears that the strongequivalence claim as originally proposed is not, in any interesting sense, true.
Second and more seriously, the CSA formalism was claimed to be capable of expressing without loss or distortion the computational methods, not just of Turing machines, but of
any computational architecture. We have seen that the CSA architecture needed major revision to capture the computational properties of the Turing machine formalism. However, the translation problems encountered in the case of Turing machines are nothing in comparison to those of other computational architectures.As a first step, consider switching from the original Turing machine architecture to a multihead Turing machine architecture, or a multitape Turing machine architecture. The CSA formalism and SPC would need to be revised again. Different features of the target formalism will need to be ‘highlighted’ in the CSA translation. For example, the distinction between different heads and tapes in a multihead/multitape Turing machine will need to preserved in the CSA translation and reflected in the implementation conditions. Each head and tape should be implemented by a distinct type of physical component that is similar amongst themselves (
heads ), and different in kind again from the others (tapes ). More highlighting and tweaks to the CSA formalism and SPC would be required.Now consider moving to an architecture that departs more dramatically from that of Turing machines: register machines, Church’s λcalculus, quantum computers, dataflow computers, billiardball computers, enzymatic computers. These formalisms have radically different ways of splitting control and data, different clocking paradigms, different parallelisms, different synchronous natures, different atomic operations, and different ways of handling input and output. They differ from CSAs, Turing machines, and each other, in major and often incompatible ways. They employ different computational methods, and introduce new and incompatible computationally significant properties. Accurately translating each formalism, without loss or distortion, to the CSA formalism would require the CSA formalism ‘highlight’ the computationallysignificant properties of that particular architecture. Given the
openended nature of the list of possible alternative architectures, and theincompatible nature of the decisions they make about computationallysignificant properties, it is hard to see how this could be done. Tweaking the CSA formalism to achieve strongequivalence withall such architectures simultaneously without that formalism becoming massively disjunctive and openended seems impossible. Moreover, the brunt of the work of a theory of implementation seems to be done by how the CSA formalism should be modified in each case, not by what the CSA formalism itself says.Therefore, replaying the ‘highlighting’ trick—hardwiring the desired formalism inside the CSA formalism—may achieve strongequivalence between CSAs and Turing machines, but it would be a shortsighted move. Indeed, tailoring the CSA architecture to Turing machines has the cost that it moves us
further away from accurately modelling other computational architectures. As the CSA formalism becomes a better model of Turing machines, it becomes a worse model for other architectures (register machines, Church’s λcalculus, quantum computers, dataflow computers, enzymatic computers). The hardwired modifications proposed to the CSA architecture to model Turing machines—a Turing machinestyle control/ data split, nonrandom access memory, atomic operations, etc.—are precisely the wrong sorts of modifications to the CSA formalism to accurately represent other architectures.This worry has particular bite in the case of the computational models in cognitive science. Contemporary computational models in cognitive science have little resemblance to
either CSAsor Turing machines. It is worth bearing in mind just how distant they are, and the incompatible nature of the decisions they make about computationallysignificant properties. They help to bring into sharp focus the magnitude of the challenge faced by a strongequivalence claim for cognitive science.For example, Marr (1982)’s computational architecture for the early visual system is a series of discrete nested computational filters that pass signals to each other in serial or parallel. Marr’s formal architecture differs in numerous ways from both Turing machines and CSAs. It differs in terms of its control/data split, atomic operations, introduction of nesting relations between filters, requirements on what can happen synchronously, and at what stages input and output are permitted. Neither the original CSA formalism nor the modified CSA formalism above accurately capture the computationallysignificant properties of Marr’s formal architecture. Anderson (2007)’s ACTR architecture is different, but just as challenging for a CSA architecture to model. ACTR is tailored to explain different cognitive capacities from Marr’s architecture and has different computationallysignificant properties: a difference between declarative and procedural data, a difference between chunks and buffers, an organisation into modules, a productiondriven rather than statedriven control system. Again, CSAs seem a poor model: they would fold all these properties into the workings of a giant transition table and state vector, with no guarantee that the relevant distinctions and similarities in the original architecture would be preserved by distinctions and similarities in kind between the components of the implementation. Wolpert & Kawato (1998)’s MOSAIC architecture is different again, and requires different formal distinctions. MOSAIC has a highly modularised structure, it has continuous dependence of output on input, it has computational relations that are best described by differential equations, it has error comparison and error summation operations as atomic steps, it is fully asynchronous, it uses probabilistic generative models among its basic representations, and it has a radically different way of managing control to traditional computers (Wolpert, Doya & Kawato, 2003). The CSA formalism does not appear capable of expressing the methods of the MOSIAC architecture without loss or distortion. If strongequivalence between Turing machines and the original CSA architecture was hard to achieve, strongequivalence with the computational models in cognitive science appears even harder. And if one tries to secure strongequivalence by departing from the original CSA formalism by using the highlighting trick, then one faces the problem that different models depart from the CSA formalism in openended and incompatible ways.
There is a claim that is closely related to strongequivalence which is almost certainly true, and which may be the source of possible resistance to the concerns above. It is almost certainly true that a physical system that is described as, say, a MOSIAC system can
also be described as a CSA. If Chalmers (2012) is right, almost any physical system can be described as a CSA merely in virtue of having a causal structure of some kind or other (p. 341). But the fact that two computational descriptions are simultaneously true of the physical system does not establish that a MOSIAC formalism and a CSA are the same (or stronglyequivalent) computational formalisms. Just as a quantum mechanical description and molecular biological description of a cat can both be true of the same physical system does not establish that the two descriptions express the same information. It is often the case that multiple distinct computational descriptions are satisfied by the same physical system. The same physical system (e.g. an electronic PC)may simultaneously implement an FSA, a CSA, a Turing machine, a register machine, and Microsoft Word. But this in no way shows that all these computational descriptions are stronglyequivalent. Just as a cat’s quantum mechanical description and the molecular description have neither the same content nor the same satisfaction conditions, so a CSA and MOSAIC computational description have neither the same content nor the same implementation conditions, even if both are (nonaccidentally) satisfied by the same physical system.
Finally, it is worth wondering why, if strongequivalence
were true, we would feel the need for talking about different architectures at all. If strongequivalence were true, why would computer science even bother using other computational architectures? Pragmatic factors may provide part of the answer: some formalisms are simply easier for humans to manipulate than others. But pragmatic factors only go so far, and a plausible deeper explanation, which fits with the assertions made in computer science, lies at hand. We have such a rich variety of computational formalisms because of their differentexpressive resources . Different architectures allow us to describe different computational methods for solving problems. The same overall effect may be achievable with another formalism, but not in the same way. We pick our architecture with an eye to its control structure, basic operations, data structures, whether it is synchronous or asynchronous, etc. These choices enable different computational tricks, distinctive twists and turns in moving from input to output. This is seen in the differences between algorithms that are enabled by von Neumann machines, λcalculus, quantum computers, DNA computers, enzymatic computers.11 Strongequivalence would render these other architectures superfluous: there is no method that cannot be expressed without loss or distortion in the CSA formalism. But why then does computer science and cognitive science place such a premium on the resources offered by a switch in architecture? Isn’t the point of such a switch to open up a space for expressing new computational methods?6.2 What is SPC’s mapping relation?
The first problem with SPC is that it is not sufficiently general as a theory of implementation, and in particular, that SPC does not secure the implementation conditions of computational models in cognitive science. The second problem concerns the mapping relation between physical states and abstract machine states—the relation that SPC inherits from SP. So far we have treated this mapping relation as an explanatory primitive. We also said that SP satisfied (D1) on clarity because it unified computational implementation with modeltheoretic interpretation and measurement. But what is this mapping relation? What metaphysical commitments does it bring with it?
This may seem like a strange question, but it should be pressed. SP’s mapping relation plays an absolutely central role in computational implementation. One of the desiderata for a theory of computational implementation is that it provide a naturalistic foundation for cognitive science (D3). We saw that, to a first approximation, this means that computational implementation has to be explicable in wholly nonmental terms. But then it looks like SP is hostage to the fortunes of the mapping relation. If the mapping relation turns out to be
minddependent , then this will infect computational implementation too. And it is not clear whether the mapping relation is innocent in this regard. Indeed, it is far from clear what the mapping relation is, and what commitments it introduces into computational implementation.One might claim that the mapping relation is an
internal relation and hence does not introduce any extra commitments over and above the metaphysical commitments brought by its relata. There are two problems with this response. First, it is not obvious that the mapping relation is an internal relation. Merely claiming that it is does not settle it; stipulations cannot make it so. Second, an internal relation requires the existence of its relata. Therefore, in order for a mapping relation to obtain,both the physical state and the abstract mathematical formalism that is the CSA need to exist. But this appears to commit one to the existence of mathematical objects, which is far from uncontroversial. Explaining the mapping relation in terms of other relations such ascorrespondence or pairing between individuals runs into similar problems. Either move seems to commit one to the existence, not only of individual physical objects, but also of abstract objects described in the mathematical formalism.One might object that this is a general problem, not one that is specific to SP.12 The mapping relation that SP employs is shared by other domains, not just computational implementation. If the nature of the mapping relation introduces worrisome commitments, or is unclear, then that is a problem not just for SP, but for a wide range of other areas. However, the general nature of the worries should not blunt their force. A parallel can be drawn with the treatment of the representation relation. Chalmers (2012) argues that the representation relation should not figure in an account of computational implementation because it is obscure and poorly understood (violating (D1)).13 Searle (1992) argues that the representation relation should not figure because it introduces illicit minddependency (violating (D3)). One might take issue with either of these claims, but both employ general concerns about the representation relation to place constraints on computational implementation. If general worries about representation justify keeping it out of an account of implementation, then general worries about the mapping relation should have force too.
6.3 SPC does not escape the triviality result
A final problem for SPC is that, even for the specific case of CSA computations, SPC does not block Putnamstyle triviality arguments. We saw in Section 5 that Step 1 and Step 2 of SPC were neither individually nor jointly sufficient to block the triviality arguments. The work of blocking the triviality arguments therefore falls almost entirely on Step 3. The problem is that it is not clear how Step 3—switching from an FSA to a CSA architecture— helps to solve the triviality problem at all.
One worry is that CSAs immediately fall prey to Putnam’s triviality argument. Formally, it is easy to translate between CSAs and FSAs. If one is persuaded by the line of reasoning that Chalmers gives to justify strongequivalence above, one might be inclined to think that CSAs and FSAs are not genuinely different formalisms, but just notational variants.
Without loss of generality, denote the substates that the elements of the CSA state vector can take,
S _{1},S _{2}, . . .,S_{n} , with numerical values (1, 2, 3, etc.). Now consider an FSA with statesS = 2^{S1}3^{S2}. . .p_{n}^{Sn} for every possible substateS_{i} , wherep_{i} is the ith prime number, and transitionsS →S ′ iff [S _{1}, . . .,S_{n} ] → [S _{1}′, . . .,S_{n} ′]. The FSA so defined is a statebased automaton with exactly the same states and transitions. The only difference is that FSA states are described by a scalar and the CSA states are described by a vector. Both CSA and FSA descriptions appear to identify the same statebased automata, just with different notations. If as Putnam argues, the implementation conditions of FSAs are trivial (which Chalmers admits), then so too are the implementation conditions of CSAs.Chalmers is of course aware of this problem. He knows that an extra constraint must be added to avoid collapsing the CSA case into the FSA case. The key move is to flag the vectorial nature of the CSA notation as
computationallysignificant with specific implications for implementation, which differ from those of a scalar notation. Chalmers does this by proposing that ‘each element of the [CSA] vector corresponds to anindependent element of the physical system ’ (Chalmers, 1996, p. 325, my italics). Call this the INDEPENDENTCOMPONENTS condition. To my mind, the INDEPENDENTCOMPONENTS condition is the single most important element of SPC. It does the lion’s share of the work in blocking the triviality arguments. Without this condition, it is unclear how switching to a CSA architecture offers any gain in blocking the triviality arguments over SP.Given the amount of work that the INDEPENDENTCOMPONENTS condition does, it is frustrating that it is not easier to spell out the content of the condition. What does it mean for something to be an
independent element of the physical system? One answer can be ruled out straightaway: ‘independent element’ cannot meantreated as independent by us , or some such, since that would immediately concede antirealism about computation, and lose us naturalistic foundations for cognitive science (D3). There must be an objective, naturalistic, answer to what makes something anindependent element of the physical system . But it is not obvious what this is. Any candidate proposal has to strike a delicate balance. It has to be strict enough to block the Putnamstyle triviality arguments. But it also has to be liberal enough to accommodate the vast number of legitimate way of dividing up and deploying physical properties in genuine computations.Chalmers proposes an answer that attempts to strike this balance: each component of the state vector of a CSA should correspond to a
distinct physical region of the implementing system.14 Call this the SPATIALREGIONS proposal. SPATIALREGIONS aims to spell out the content of the INDEPENDENTCOMPONENTS condition. The SPATIALREGIONS proposal has the virtue of being clear (D1) and naturalistic (D3), but unfortunately it is neither necessary nor sufficient for computational implementation of CSAs.The SPATIALREGIONS proposal is not necessary because a system could implement a CSA even if its substates occupy the same spatial regions. There are many ways in which this could happen. First, a system could use
properties to encode its substates, and distinct properties can be instantiated at the same spatial location. For example, a system might use different vibrational frequencies (e.g. different electromagnetic frequencies) to implement different elements of its state vector, even if those frequencies are instantiated in the same spatial locations (as in AM radio). Second, a system might usepulses that travel back and forth over the same spatial regions, but which are individuated by theirdelays to implement different elements of its state vector (for example, as in a mercury delay line (Eckert, 1997)). Finally, as Chalmers suggests, the substates of a CSA could change their implemented spatial region over time as part of the computation. Two substates could swap over to occupy each other’s spatial regions. An example would be the use of pointers in PCs which allow the physical memory location of data to be changed without affecting the computation (Chalmers, 1996, pp. 329?330).Perhaps more worrying is that the SPATIALREGIONS condition is not sufficient for implementation. Even with the SPATIALREGIONS condition in place, a triviality result for CSAs still obtains. Choose an open physical system
P and pick within itn spatial regions,e _{1}, . . .,e _{n}, which are (i) spatially distinct and (ii) share some spatial border with each other (say, via a connective region). Each spatial region is itself an open physical system. Hence, by Putnam’s result, each spatial regione_{i} implements any FSA. Therefore, at any moment in time, each regione_{i} can be associated with an arbitrary stateS_{j} of any FSA. The spatial regionse _{1}, . . .,e_{n} share common borders. Define the borders of these connective regions as the weak inputs and outputs to each spatial regione_{i} . A weak input or output merely requires that there exists a structurepreserving mapping between the physical inputs and outputs and the inputs and outputs of the abstract FSA. As we saw above, weak inputs and outputs impose almost no constraints on implementation. Since the regionse_{i} implement any FSA, they implement any FSA with weak inputs and outputs so defined. Therefore, physical systemP implements a group ofn FSAs such that if those FSAs are in statesS _{1}, . . .,S _{n} at one moment, they will be in statesS _{1}′, . . .,S_{n} ′ at the next moment, with the transition governed by all the previousS_{i} states via the interregion weak inputs and outputs. Therefore, the physical system as a whole implements the state transitions [S _{1}, . . .,S _{n}] → [S _{1}′, . . .,S_{n} ′]. Modifying the result so that it also accepts overall input and output (Step 2), and its transitions have modal force (Step 1) is not hard. Similarly, the requirement that there be at leastn distinct spatial regions that border with each other inside the physical system is easy to meet.Even if one were to reject SPATIALREGIONS, the INDEPENDENTCOMPONENTS condition still seems to be a fundamentally correct thought about the nature of computational implementation. The basic idea of INDEPENDENTCOMPONENTS also generalises beyond the specifics of the CSA formalism (as we saw in Section 6.1). That idea is that
distinct computational elements in the abstract computational formalism should be implemented byindependent physical components in the physical system. This is an instance of the general idea explored in Section 6.1 that computationallysignificant differences and similarities in the abstract formalism should be mirrored by physicallysignificant differences and similarities in the implementation. The INDEPENDENTCOMPONENTS condition appears to offer the seed of a response to the triviality arguments. Presumably, not just any physical system has physical components that are independent in the right sense and wired up in the right ways. However, to make good on this, one must spell out the content of the INDEPENDENTCOMPONENTS condition. In particular, one must give a naturalistic, objective characterisation of the conditions under which two physical features are independent components that strikes the correct balance above between being too liberal and too strict. In the absence of such an account, using the INDEPENDENTCOMPONENTS condition to block the triviality arguments remains a promissory note.If INDEPENDENTCOMPONENTS cannot be spelt out as SPATIALREGIONS, how should it be understood? My own view is that INDEPENDENTCOMPONENTS should be understood as placing constraints on what various physical features represent. This brings extra resources into play, and I believe allows one to strike the right balance described above. However, this representational approach to implementation differs significantly from that of Chalmers, and it brings further challenges, which I will not discuss here.
7Nevertheless, see Brooks (1991) for an argument that cognition should be modelled via a series of nested FSAs. If Brooks is right, then FSAs, and their implementation conditions, matter a great deal to cognitive science. 8Like Chalmers, I will restrict attention to computational architectures with finite storage (e.g. Turing machines with finite tape). As Chalmers notes, finite storage architectures are the ones most relevant to modelling human cognition. Chalmers sketches how SPC can be extended to apply to architectures with unbounded storage, but will do not need to consider his extension here. 9Cf. Pylyshyn (1984), Ch. 4. 10Again, restricting attention to Turing machines with finite storage. 11See Backus (1978) for how formal architecture determines the available computational methods. 12Thanks to an anonymous referee for pressing this point. 13Chalmers (1995), pp. 399?400; Chalmers (2012), p. 334. 14Chalmers (1996), p. 325, Chalmers (2012), p. 328.
7. Conclusion
We identified three desiderata on an account of computational implementation. These were that an account should be (D1) clear, (D2) avoid the triviality arguments, and (D3) provide naturalistic foundations for cognitive science. Chalmers’ account of implementation, which I have called SPC, can be understood as an attempt to meet these three desiderata.
I raised three challenges to SPC. These were that SPC is (i) not sufficiently general, (ii) leaves certain key relations unclear, (iii) does not block the triviality arguments. We saw a tradeoff between meeting the desiderata. Individually, each desideratum is easy to meet. Even if one gives up one of the three desiderata, meeting the other two is relatively easy. For example, a common way to block the triviality arguments (D2) and keep clarity (D1) is to allow nonnaturalistic factors into the facts that determine computational implementation (e.g. our
judgements ,interests , andattitudes concerning the merits of different mappings) (giving up (D3)). Meeting all three desiderata simultaneously is hard. Chalmers’ account provides the best attempt to do so, but even his proposal falls short. In each of the three challenges above (i)(iii), we saw some or other tradeoff was pressed on us—either giving up clarity (D1), the response to the triviality arguments (D2), or naturalistic foundations (D3).Even if one is convinced by the challenges above, Chalmers’ account remains of absolutely central importance. Chalmers’ account presents insightful and plausible necessary conditions on computational implementation. What I have called Chalmers’ INDEPENDENTCOMPONENTS condition expresses an important insight: that different elements of the computational formalism should be implemented by
independent physical components . Tantalisingly, this thought appears to contain the seeds of an answer that meets all three desiderata. Cashing out whatindependent physical component means in the context of an account of computational implementation is one of the major challenges facing future work on implementation.