Abstract
This paper deals with the question: what are the key requirements for a physical system to perform digital computation? Time and again cognitive scientists are quick to employ the notion of computation simpliciter when asserting basically that cognitive activities are computational. They employ this notion as if there was or is a consensus on just what it takes for a physical system to perform computation, and in particular digital computation. Some cognitive scientists in referring to digital computation simply adhere to Turing’s notion of computability. Classical computability theory studies what functions on the natural numbers are computable and what mathematical problems are undecidable. Whilst a mathematical formalism of computability may perform a methodological function of evaluating computational theories of certain cognitive capacities, concrete computation in physical systems seems to be required for explaining cognition as an embodied phenomenon. There are many non-equivalent accounts of digital computation in physical systems. I examine only a handful of those in this paper: (1) Turing’s account; (2) The triviality “account”; (3) Reconstructing Smith’s account of participatory computation; (4) The Algorithm Execution account. My goal in this paper is twofold. First, it is to identify and clarify some of the underlying key requirements mandated by these accounts. I argue that these differing requirements justify a demand that one commits to a particular account when employing the notion of computation in regard to physical systems. Second, it is to argue that despite the informative role that mathematical formalisms of computability may play in cognitive science, they do not specify the relationship between abstract and concrete computation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agassi, J. (unpublished). The Turing Test.
Bell P., Staines P. J., Mitchell J. (2001) Evaluating, doing and writing research in psychology. Sage publication, London
Block N. (2002) Searle’s arguments against cognitive science. In: Preston J., Bishop M. (eds) Views into the Chinese room. Oxford University Press, Oxford, pp 70–79
Buechner J. (2008) Gödel, Putnam, and functionalism. MIT Press, Cambridge
Chalmers D. (1994) 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
Chrisley R. L. (1995) Why everything doesn’t realize every computation. Minds and Machines 4: 403–420
Copeland B. J. (1996) What is computation?. Synthese 108: 335–359
Copeland B. J. (1997) The broad conception of computation. The American Behavioral Scientist 40: 690–716
Copeland B. J. (2003) Computation. In: Floridi L. (eds) The Blackwell guide to the philosophy of computing and information. Wiley-Blackwell, Oxford, pp 3–17
Copeland B. J., Shagrir O. (2007) Physical computation: How general are Gandy’s principles for mechanisms?. Minds and Machines 17: 217–231
Cummins R. (1977) Programs in the explanation of behaviour. Philosophy of Science 44: 269–287
Cummins R. (1989) Meaning and mental representation. MIT Press, Cambridge
Cummins R. (1996) Systematicity. The Journal of Philosophy 93: 591–614
Davis M. (1958) Computability and unsolvability. McGraw-Hill, NY
Dennett C. D. (1998) Brainchildren: Essays on designing minds. MIT Press, Cambridge
Fodor J. A. (1975) The language of thought. Harvard University Press, Cambridge
Fresco N. (2008) An analysis of the criteria for evaluating adequate theories of computation. Minds and Machines 18: 379–401
Fresco N. (2010) Explaining computation without semantics: Keeping it simple. Minds and Machines 20: 165–181
Gandy R. (1980) Church’s thesis and principles for mechanisms. In: Barwise J., Keisler H. J., Kunen K. (eds) The Kleene symposium. Amsterdam, North-Holland
Hopcroft J. E., Motwani R., Ullman J. D. (2001) Introduction to automata theory, languages and computation. 2nd edn. Addison Wesley, Reading
Israel D. (2002) Reflections on Gödel’s and Gandy’s reflections on Turing’s thesis. Minds and Machines 12: 181–201
Karp R. M. (1972) Reducibility among combinatorial problems. In: Miller R., Thatcher J. (eds) Complexity of computer computations. Plenum, New York, pp 85–104
Kleene S. C. (2002) Mathematical logic. Dover, New York
Marr D. (1982) Vision: A computational investigation into the human representation and processing visual information. Freeman & Company, NY
Nelson R. J. (1982) The logic of mind. Reidel, Dordrecht
Newell A., Simon H. A. (1976) Computer science as an empirical enquiry: Symbols and search. Communications of the ACM 19: 113–126
Parikh R. (1998) Church’s theorem and the decision problem. In: Craig E. (eds) Routledge encyclopedia of philosophy. Routledge, London, pp 349–351
Penrose R. (1989) The Emperor’s new mind. Oxford University Press, London
Piccinini G. (2007) Computing mechanisms. Philosophy of Science 74: 501–526
Piccinini G. (2008a) Computation without representation. Philosophical studies 137: 205–241
Piccinini G. (2008b) Computers. Pacific Philosophical Quarterly 89: 32–73
Piccinini G., Scarantino A. (2011) Information processing, computation, and cognition. Journal of Biological Physics 37: 1–38
Putnam H. (1988) Representation and reality. The MIT Press, Cambridge
Pylyshyn Z. W. (1984) Computation and cognition: Toward a foundation for cognitive science. MIT Press, Cambridge, MA
Searle J. R. (1990) Is the brain a digital computer?. Proceedings and Addresses of the American Philosophical Association 64: 21–37
Seligman J. (2002) The scope of Turing’s analysis of effective procedures. Minds and Machines 12: 203–220
Shagrir O. (1999) What is computer science about?. The Monist 82: 131–149
Shagrir O. (2010) Marr on computational-level theories. Philosophy of Science 77: 477–500
Sieg, W. (2008). Church without dogma: Axioms for computability. In S. B. Cooper, B. Löwe, & S. Andrea (Eds.) New computational paradigms (pp. 139–152).
Smith B. C. (1996) On the origins of objects. MIT Press, Cambridge, MA
Smith B. C. (2002) The foundations of computing. In: Scheutz M. (eds) Computationalism: New directions. MIT Press, Cambridge, pp 23–58
Smith, B. C. (2008). Rehabilitating representation. Paper presented at the Spring 2008 Colloquia at the Center for Cognitive Science, University at Buffalo, State University of New York.
Smith, B. C. (2010). Age of significance: Introduction. Retrieved May 3, 2010, from http://www.ageofsignificance.org.
Smith, B. C. (unpublished). Formal symbol manipulation: Ontological critique. Expected to be published in 2011 at http://www.ageofsignificance.org.
Soare R. (1996) Computability and recursion. The Bulletin of Symbolic Logic 2: 284–321
Soare R. (2009) Turing oracle machines, online computing, and three displacements in computability theory. Annals of Pure and Applied Logic 160: 368–399
Thelen E., Smith L. B. (1994) A dynamical systems approach to the development of cognition and action. MIT press, Cambridge
Turing A. M. (1936) On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 42(2): 230–265
Van Gelder T., Port R. F. (1995) It’s about time: An overview of the dynamical approach to cognition. In: Gelder T., Port R. F. (eds) Mind as motion. MIT Press, Cambridge, pp 23–58
van Rooij I. (2008) The tractable cognition thesis. Cognitive Science 32: 939–984
Wells A. J. (1998) Turing’s analysis of computation and theories of cognitive architecture. Cognitive Science 22: 269–294
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fresco, N. Concrete Digital Computation: What Does it Take for a Physical System to Compute?. J of Log Lang and Inf 20, 513–537 (2011). https://doi.org/10.1007/s10849-011-9147-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10849-011-9147-8