Tractability and the computational mind

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

Authors
Jakub Szymanik
University of Amsterdam
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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Aspects of the Theory of Syntax.Ann S. Ferebee & Noam Chomsky - 1965 - Journal of Symbolic Logic 35 (1):167.

View all 39 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Computational Model Theory: An Overview.M. Vardi - 1998 - Logic Journal of the IGPL 6 (4):601-624.
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.

Analytics

Added to PP index
2019-02-06

Total views
35 ( #230,203 of 2,244,032 )

Recent downloads (6 months)
35 ( #19,819 of 2,244,032 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature