Tractability and the computational mind

In Mark Sprevak & Matteo Colombo (eds.), The Routledge Handbook of the Computational Mind. Oxford, UK: pp. 339-353 (2018)

Abstract

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition.

Download options

PhilArchive

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2019-02-06

Downloads
278 (#40,191)

6 months
42 (#20,160)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Jakub Szymanik
University of Amsterdam

References found in this work

Aspects of the Theory of Syntax.Noam Chomsky - 1965 - Cambridge, MA, USA: MIT Press.
Aspects of the Theory of Syntax.Ann S. Ferebee - 1965 - Journal of Symbolic Logic 35 (1):167.
Syntactic Structures.J. F. Staal - 1966 - Journal of Symbolic Logic 31 (2):245-251.

View all 46 references / Add more references

Similar books and articles

Computational Model Theory: An Overview.M. Vardi - 1998 - Logic Journal of the IGPL 6 (4):601-624.
Why Philosophers Should Care About Computational Complexity.Scott Aaronson - 2013 - Computability: Turing, Gödel, Church, and Beyond:261--328.
Tractable Competence.Marcello Frixione - 2001 - Minds and Machines 11 (3):379-397.
Computation and Automata.Arto Salomaa - 1985 - Cambridge University Press.
Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.
Elementary Arithmetic.Geoffrey E. Ostrin & Stanley S. Wainer - 2005 - Annals of Pure and Applied Logic 133 (1):275-292.
Computational Complexity on Computable Metric Spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.