Many cognitive scientists, having discovered that some computational-level characterization f of a cognitive capacity φ is intractable, invoke heuristics as algorithmic-level explanations of how cognizers compute f. We argue that such explanations are actually dysfunctional, and rebut five possible objections. We then propose computational-level theory revision as a principled and workable alternative.

Bayesian models are often criticized for postulating computations that are computationally intractable (e.g., NP-hard) and therefore implausibly performed by our resource-bounded minds/brains. Our letter is motivated by the observation that Bayesian modelers have been claiming that they can counter this charge of “intractability” by proposing that Bayesian computations can be tractably approximated. We would like to make the cognitive science community aware of the problematic nature of such claims. We cite mathematical proofs from the computer science literature that show intractable (...) Bayesian computations, such as postulated in existing Bayesian models, cannot be tractably approximated. This does not mean that human brains do not (or cannot) implement the type of algorithms that Bayesian modelers are advancing, but it does mean that proposing that they do by itself does nothing to parry the charge of intractability, because the postulated algorithms are as intractable (i.e., require exponential time) as the computations they try to approximate. Besides our negative message for the community, our letter also makes a positive contribution by referring to a methodology that Bayesian modelers can use to try and parry the charge of intractability in a mathematically sound way. (shrink)

Neural networks usually work adequately on small problems but can run into trouble when they are scaled up to problems involving large amounts of input data. Circuit Complexity and Neural Networks addresses the important question of how well neural networks scale - that is, how fast the computation time and number of neurons grow as the problem size increases. It surveys recent research in circuit complexity (a robust branch of theoretical computer science) and applies this work to a theoretical understanding (...) of the problem of scalability. Most research in neural networks focuses on learning, yet it is important to understand the physical limitations of the network before the resources needed to solve a certain problem can be calculated. One of the aims of this book is to compare the complexity of neural networks and the complexity of conventional computers, looking at the computational ability and resources (neurons and time) that are a necessary part of the foundations of neural network learning. Circuit Complexity and Neural Networks contains a significant amount of background material on conventional complexity theory that will enable neural network scientists to learn about how complexity theory applies to their discipline, and allow complexity theorists to see how their discipline applies to neural networks. (shrink)

The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance the Tractable Cognition thesis: Human cognitive capacities are constrained by computational tractability. This thesis, if true, serves cognitive psychology by constraining the space of computational‐level theories of cognition. To utilize this constraint, a precise and workable definition of “computational tractability” is needed. Following computer science tradition, many cognitive scientists and psychologists define computational tractability as polynomial‐time computability, leading to the P‐Cognition thesis. (...) This article explains how and why the P‐Cognition thesis may be overly restrictive, risking the exclusion of veridical computational‐level theories from scientific investigation. An argument is made to replace the P‐Cognition thesis by the FPT‐Cognition thesis as an alternative formalization of the Tractable Cognition thesis (here, FPT stands for fixed‐parameter tractable). Possible objections to the Tractable Cognition thesis, and its proposed formalization, are discussed, and existing misconceptions are clarified. (shrink)

This paper provides a computational characterization of coherence that applies to a wide range of philosophical problems and psychological phenomena. Maximizing coherence is a matter of maximizing satisfaction of a set of positive and negative constraints. After comparing five algorithms for maximizing coherence, we show how our characterization of coherence overcomes traditional philosophical objections about circularity and truth.

This study addresses the dynamical nature of a “representation‐hungry” cognitive task involving an imagined action. In our experiment, participants were handed rods that systematically increased or decreased in length on subsequent trials. Participants were asked to judge whether or not they thought they could reach for a distant object with the hand‐held rod. The results are in agreement with a dynamical model, extended from Tuller, Case, Ding, and Kelso (1994). The dynamical effects observed in this study suggest that predictive judgments (...) regarding the possibility or impossibility of a certain action can be understood in terms of dynamically evolving basins of attraction instead of as depending on representational structures. (shrink)

The complex systems approach to cognitive science invites a new understanding of extended cognitive systems. According to this understanding, extended cognitive systems are heterogenous, composed of brain, body, and niche, non-linearly coupled to one another. This view of cognitive systems, as non-linearly coupled brain–body–niche systems, promises conceptual and methodological advances. In this article we focus on two of these. First, the fundamental interdependence among brain, body, and niche makes it possible to explain extended cognition without invoking representations or computation. Second, (...) cognition and conscious experience can be understood as a single phenomenon, eliminating fruitless philosophical discussion of qualia and the so-called hard problem of consciousness. What we call “extended phenomenological-cognitive systems” are relational and dynamical entities, with interactions among heterogeneous parts at multiple spatial and temporal scales. (shrink)

In some areas of cognitive science we are confronted with ultrafast cognition, exquisite context sensitivity, and scale-free variation in measured cognitive activities. To move forward, we suggest a need to embrace this complexity, equipping cognitive science with tools and concepts used in the study of complex dynamical systems. The science of movement coordination has benefited already from this change, successfully circumventing analogous paradoxes by treating human activities as phenomena of self-organization. Therein, action and cognition are seen to be emergent in (...) ultrafast symmetry breaking across the brain and body; exquisitely constituted of the otherwise trivial details of history, context, and environment; and exhibiting the characteristic scale-free signature of self-organization. (shrink)

How do people decide what to say in context? Many theories of pragmatics assume that people have specialized knowledge that drives them to utter certain words in different situations. But these theories are mostly unable to explain both the regularity and variability in people’s speech behaviors. Our purpose in this article is to advance a view of pragmatics based on complexity theory, which specifically explains the pragmatic choices speakers make in conversations. The concept of self-organized criticality sheds light on how (...) a history of utterances and subtle details of a situation surrounding a conversation may directly specify language behavior. Under this view, pragmatic choice in discourse does not reflect the output of any dedicated pragmatic module but arises from a complex coordination or coupling between speakers and their varying communicative tasks. (shrink)

The complex-systems approach to cognitive science seeks to move beyond the formalism of information exchange and to situate cognition within the broader formalism of energy flow. Changes in cognitive performance exhibit a fractal (i.e., power-law) relationship between size and time scale. These fractal fluctuations reflect the flow of energy at all scales governing cognition. Information transfer, as traditionally understood in the cognitive sciences, may be a subset of this multiscale energy flow. The cognitive system exhibits not just a single power-law (...) relationship between fluctuation size and time scale but actually exhibits many power-law relationships, whether over time or space. This change in fractal scaling, that is, multifractality, provides new insights into changes in energy flow through the cognitive system. We survey recent findings demonstrating the role of multifractality in (a) understanding atypical developmental outcomes, and (b) predicting cognitive change. We propose that multifractality provides insights into energy flows driving the emergence of cognitive structure. (shrink)