Abstract
I articulate and defend a new theory of what it is for a physical system to implement an abstract computational model. According to my descriptivist theory, a physical system implements a computational model just in case the model accurately describes the system. Specifically, the system must reliably transit between computational states in accord with mechanical instructions encoded by the model. I contrast my theory with an influential approach to computational implementation espoused by Chalmers, Putnam, and others. I deploy my theory to illuminate the relation between computation and representation. I also rebut arguments, propounded by Putnam and Searle, that computational implementation is trivial.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Cleland (2002) also emphasizes that conformity to instructions underlies our intuitive notion of computation. However, she does not exploit this observation to offer a theory of implementation for abstract computational models. Instead, she uses it to attack the standard view that abstract models are central to elucidating physical computation. In contrast, I accept the standard emphasis on abstract models.
High-level programming languages furnish additional examples in the same vein. As (Chalmers (2012), p. 222) notes, there is usually slack between a program couched in a high-level programming language and a more explicit description in terms of states and state-transitions.
Cleland (2002) makes a similar point.
Why does the definition include a privileged set of final states F? So that we can model “language acceptance.” An FSM accepts a string of symbols just in case sequentially inputting that string to the FSM produces a final state belonging to F. Relations between formal languages and FSMs play a central role in automata theory, but they will not figure in my exposition. For all the FSMs I consider in this paper, we may simply set \(\hbox {F}=\hbox {Q}\).
And familiar also from Wittgenstein’s later writings: “The arrow points only in the application that a living being makes of it” (1953, §454).
There are affinities between structuralism about computational implementation and broadly “structuralist” views within philosophy of science more generally. The intuitive idea behind such views is that scientific theories represent only “structural” features of the world (Bueno and French 2011; van Fraassen 2008). However, structuralists within general philosophy of science need not endorse structuralism about computational implementation. Their position concerns the representational import of scientific theories, not the implementation relation between computational models and physical systems. To derive a structuralist view of computational implementation, one requires an additional premise linking representational import and implementation conditions, a premise that structuralist philosophers of science might well reject.
Chalmers introduces complex state automata (CSAs), which abstract away from idiosyncratic features of particular computational formalisms. He delineates precise structuralist implementation conditions for CSAs, and he specifies a computational model’s implementation condition by translating the model into an appropriate CSA. Thus, CSAs play a role within Chalmers’s account analogous to the role that canonical state space descriptions play within my account. There are various relatively minor differences between CSAs and canonical state space descriptions, but the major difference reflects Chalmers’s structuralist commitments. The states composing a CSA are abstract states with no inherent natures beyond their role in a formal structure determined by the CSA. Implementing a CSA simply requires that a physical system’s causal structure mirror the CSA’s formal structure. In contrast, the states that compose a canonical state space description can involve non-functional properties (such as being located on the first floor) that outstrip any relevant formal or causal structure.
Chalmers (2011) proposes his structuralist theory of computational implementation as a philosophical foundation for cognitive science. His proposal is an example of functionalism about the mind, first espoused by Putnam (1975). If Chalmers’s proposal were correct, then it would vindicate the centrality of \(\hbox {implementation}_{2}\) to cognitive science. However, Burge (2007, pp. 376–377) argues that functionalism is “far removed from any explanation that goes on in science.” In (Rescorla 2012), I critique Chalmers’s structuralist approach to mental computation. I argue that Chalmers’s approach finds no basis within contemporary cognitive science.
The register machine formalism assumes that each memory register can represent any natural number of arbitrary size. As already noted, infinite discrete memory capacity may be physically impossible. If so, then the Euclidean algorithm register machine is not physically realizable. We can circumvent this issue by employing a modified register machine formalism that assumes large but finite memory capacity. (To a first approximation, modern computers are physical realizations of such a formalism.) Programs couched within the modified register machine formalism can still individuate register states through representational relations to (sufficiently small) numbers.
More cautiously, stipulate that \(R_{10}\) implements an analogue to the Euclidean algorithm register machine, couched within the modified formalism from note 10. I henceforth ignore this caveat, since it does not affect my argument.
In (Rescorla forthcoming), I rebut numerous additional possible structuralist rejoinders to the Euclidean algorithm register machine counterexample. I also argue that such cases militate against bounded structuralism.
Chalmers (2011, 2012) holds that every physical system implements a trivial FSM containing a single abstract machine state. On this basis, he endorses pancomputationalism, i.e. the thesis that every physical system implements a computational model. He notes that the resulting pancomputationalist position does not trivialize computational implementation, so long as we deny that every physical system realizes every computational model. Chalmers’s discussion of these points strikes me as quite convincing.
See Piccinini (2010) for a survey of prior theories. The positions that Piccinini calls the simple mapping account, the causal account, the counterfactual account, and the dispositional account are versions of what I call structuralism and bounded structuralism. The position that Piccinini calls the semantic account entails the position that I call the semantic view. The position that Piccinini calls the syntactic account does not allow representational properties to inform implementation conditions. As I argued in Sect. 5, no such theory can accommodate the Euclidean algorithm register machine, among numerous additional computational models that figure prominently within contemporary CS. The only remaining position discussed by Piccinini is the one that he himself espouses, which he calls the mechanistic account. Certain aspects of the mechanistic account are congenial to descriptivism. However, Piccinini’s version of the mechanistic account does not allow representational properties to inform implementation conditions (Piccinini 2008).
Chalmers’s own theory is less reductive than it may initially appear. As discussed in note 7, Chalmers specifies a computational model’s implementation condition by translating the model into a suitable CSA. Chalmers says nothing to elucidate the “translation” relation between computational models and CSAs. So the “translation” relation plays an unreduced role within Chalmers’s account similar to the unreduced role that the “inducement” relation plays within my account.
References
Abelson, H., Sussman, G., & Sussman, J. (1996). The structure and interpretation of computer programs. Cambridge: MIT Press.
Bueno, O., & French, S. (2011). How theories represent. British Journal for the Philosophy of Science, 62, 857–894.
Burge, T. (2007). Foundations of mind. Oxford: Clarendon Press.
Chalmers, D. (1995). On implementing a computation. Minds and Machines, 4, 391–402.
Chalmers, D. (1996). Does a rock implement every finite state automaton? Synthese, 108, 309–333.
Chalmers, D. (2011). A computational foundation for the study of cognition. The Journal of Cognitive Science, 12, 323–357.
Chalmers, D. (2012). The varieties of computation: A reply. The Journal of Cognitive Science, 13, 211–248.
Chrisley, R. (1994). Why everything doesn’t realize every computation. Minds and Machines, 4:403–420.
Cleland, C. (2002). On effective procedures. Minds and Machines, 12, 159–179.
Copeland, J. (1996). What is computation? Synthese, 108, 335–359.
Dietrich, E. (1989). Semantics and the computational paradigm in cognitive psychology. Synthese, 79, 119–141.
Dresner, E. (2010). Measurement-theoretic representation and computation-theoretic realization. The Journal of Philosophy, 107, 275–292.
Feferman, S. (2006). Turing’s thesis. Notices of the American Mathematical Society, 53, 2–8.
Fodor, J. (1998). Concepts. Oxford: Oxford University Press.
Godfrey-Smith, P. (2009). Triviality arguments against functionalism. Philosophical Studies, 145, 273–295.
Hopcroft, J., & Ullman, J. (1979). Introduction to automata theory, languages, and computation. Menlo Park: Addison-Wesley.
Klein, C. (2008). Dispositional implementation solves the superfluous structure problem. Synthese, 165, 141–153.
Knuth, D. (1968). The art of computer programming (Vol. 1). Reading: Addison-Wesley.
Ladyman, J. (2009). What does it mean to say that a physical system implements a computation? Theoretical Computer Science, 410, 376–383.
Lewis, D. (1973). Counterfactuals. Malden: Blackwell.
Minsky, M. (1967). Computation: Finite and infinite machines. Englewood Cliffs: Prentice-Hall.
Montemerlo, M., et al. (2009). Junior: The Stanford entry in the urban challenge. In M. Buehler, K. Iagnemma, & S. Singh (Eds.), The DARPA urban challenge. Berlin: Springer.
Mozgovoy, M. (2010). Algorithms, languages, compilers, and automata. Sudbury: Jones and Bartlett.
Murphy, R. (2000). Introduction to AI robotics. Cambridge: MIT Press.
Patterson, D., & Hennessy, J. (2005). Computer organization and design (3rd ed.). New York: Elsevier.
Piccinini, G. (2008). Computation without representation. Philosophical Studies, 137, 205–241.
Piccinini, G. (2010). Computation in physical systems. In E. Zalta (Ed.), The Stanford encyclopedia of philosophy (Fall 2010 edition).
Putnam, H. (1975). Philosophical papers (Vol. 2). Cambridge: Cambridge University Press.
Putnam, H. (1988). Representation and reality. Cambridge: MIT Press.
Rescorla, M. (2012). How to integrate representation into computational modeling, and why we should. The Journal of Cognitive Science, 13, 1–38.
Rescorla, M. (forthcoming). Against structuralist theories of computational implementation. British Journal for the Philosophy of Science.
Scheutz, M. (2001). Computational versus causal complexity. Minds and Machines, 11, 544–566.
Searle, J. (1990). Is the brain a digital computer? Proceedings and Addresses of the American Philosophical Association, 64, 21–37.
Shagrir, O. (2006). Why we view the brain as a computer. Synthese, 153, 393–416.
Shepherdson, J., & Sturgis, H. E. (1963). Computability of recursive functions. Journal of the Association of Computing Machinery, 10, 217–255.
Sprevak, M. (2010). Computation, individuation, and the received view on representation. Studies in History and Philosophy of Science, 41, 260–270.
Vahid, F., & Givargis, T. (2002). Embedded system design. New York: Wiley.
van Fraassen, B. (2008). Scientific representation. Oxford: Clarendon Press.
Wittgenstein, L. (1953). In G. E. M. Anscombe & R. Rhees (Eds.), Philosophical investigations (G. E. M. Anscombe, Trans.). Oxford: Blackwell.
Woodward, J. (2000). Explanation and invariance in the special sciences. British Journal for the Philosophy of Science, 51, 197–254.
Acknowledgments
I am indebted to David Chalmers, Peter Godfrey-Smith, Gualtiero Piccinini, Eric Rescorla, Mark Sprevak, and two anonymous referees for helpful feedback that greatly improved this paper. My research was supported by a fellowship from the National Endowment for the Humanities. Any views, findings, conclusions, or recommendations expressed in this publication do not necessarily reflect those of the National Endowment for the Humanities.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rescorla, M. A theory of computational implementation. Synthese 191, 1277–1307 (2014). https://doi.org/10.1007/s11229-013-0324-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11229-013-0324-y