Tractability and the computational mind

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