The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance theTractable 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 theP‐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 theFPT‐Cognition thesisas 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)

The general problem of visual search can be shown to be computationally intractable in a formal, complexity-theoretic sense, yet visual search is extensively involved in everyday perception, and biological systems manage to perform it remarkably well. Complexity level analysis may resolve this contradiction. Visual search can be reshaped into tractability through approximations and by optimizing the resources devoted to visual processing. Architectural constraints can be derived using the minimum cost principle to rule out a large class of potential solutions. The (...) evidence speaks strongly against bottom-up approaches to vision. In particular, the constraints suggest an attentional mechanism that exploits knowledge of the specific problem being solved. This analysis of visual search performance in terms of attentional influences on visual information processing and complexity satisfaction allows a large body of neurophysiological and psychological evidence to be tied together. (shrink)

The general problem of visual search can be shown to be computationally intractable in a formal, complexity-theoretic sense, yet visual search is extensively involved in everyday perception, and biological systems manage to perform it remarkably well. Complexity level analysis may resolve this contradiction. Visual search can be reshaped into tractability through approximations and by optimizing the resources devoted to visual processing. Architectural constraints can be derived using the minimum cost principle to rule out a large class of potential solutions. The (...) evidence speaks strongly against bottom-up approaches to vision. In particular, the constraints suggest an attentional mechanism that exploits knowledge of the specific problem being solved. This analysis of visual search performance in terms of attentional influences on visual information processing and complexity satisfaction allows a large body of neurophysiological and psychological evidence to be tied together. (shrink)

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.

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (shrink)

According to Aristotle, humans are the rational animal. The borderline between rationality and irrationality is fundamental to many aspects of human life including the law, mental health, and language interpretation. But what is it to be rational? One answer, deeply embedded in the Western intellectual tradition since ancient Greece, is that rationality concerns reasoning according to the rules of logic – the formal theory that specifies the inferential connections that hold with certainty between propositions. Piaget viewed logical reasoning as defining (...) the end-point of cognitive development; and contemporary psychology of reasoning has focussed on comparing human reasoning against logical standards. (shrink)

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a more (...) mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable. (shrink)

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)

This paper explores the difference between Connectionist proposals for cognitive a r c h i t e c t u r e a n d t h e s o r t s o f m o d e l s t hat have traditionally been assum e d i n c o g n i t i v e s c i e n c e . W e c l a i m t h a t t h (...) e m a j o r d i s t i n c t i o n i s t h a t , w h i l e b o t h Connectionist and Classical architectures postulate representational mental states, the latter but not the former are committed to a symbol-level of representation, or to a ‘language of thought’: i.e., to representational states that have combinatorial syntactic and semantic structure. Several arguments for combinatorial structure in mental representations are then reviewed. These include arguments based on the ‘systematicity’ of mental representation: i.e., on the fact that cognitive capacities always exhibit certain symmetries, so that the ability to entertain a given thought implies the ability to entertain thoughts with semantically related contents. We claim that such arguments make a powerful case that mind/brain architecture is not Connectionist at the cognitive level. We then consider the possibility that Connectionism may provide an account of the neural (or ‘abstract neurological’) structures in which Classical cognitive architecture is implemented. We survey a n u m b e r o f t h e s t a n d a r d a r g u m e n t s t h a t h a v e b e e n o f f e r e d i n f a v o r o f Connectionism, and conclude that they are coherent only on this interpretation. (shrink)

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

Rational analysis (Anderson 1990, 1991a) is an empiricalprogram of attempting to explain why the cognitive system isadaptive, with respect to its goals and the structure of itsenvironment. We argue that rational analysis has two importantimplications for philosophical debate concerning rationality. First,rational analysis provides a model for the relationship betweenformal principles of rationality (such as probability or decisiontheory) and everyday rationality, in the sense of successfulthought and action in daily life. Second, applying the program ofrational analysis to research on human reasoning (...) leads to a radicalreinterpretation of empirical results which are typically viewed asdemonstrating human irrationality. (shrink)

Remarkable progress in the mathematics and computer science of probability has led to a revolution in the scope of probabilistic models. In particular, ‘sophisticated’ probabilistic methods apply to structured relational systems such as graphs and grammars, of immediate relevance to the cognitive sciences. This Special Issue outlines progress in this rapidly developing field, which provides a potentially unifying perspective across a wide range of domains and levels of explanation. Here, we introduce the historical and conceptual foundations of the approach, explore (...) how the approach relates to studies of explicit probabilistic reasoning, and give a brief overview of the field as it stands today. (shrink)

British psychologists have been at the forefront of research into human reasoning for 40 years. This article describes some past research milestones within this tradition before outlining the major theoretical positions developed in the UK. Most British reasoning researchers have contributed to one or more of these positions. We identify a common theme that is emerging in all these approaches, that is, the problem of explaining how prior general knowledge affects reasoning. In our concluding comments we outline the challenges for (...) future research posed by this problem. (shrink)

Much research on judgment and decision making has focussed on the adequacy of classical rationality as a description of human reasoning. But more recently it has been argued that classical rationality should also be rejected even as normative standards for human reasoning. For example, Gigerenzer and Goldstein and Gigerenzer and Todd argue that reasoning involves “fast and frugal” algorithms which are not justified by rational norms, but which succeed in the environment. They provide three lines of argument for this view, (...) based on: the importance of the environment; the existence of cognitive limitations; and the fact that an algorithm with no apparent rational basis, Take-the-Best, succeeds in an judgment task. We reconsider –, arguing that standard patterns of explanation in psychology and the social and biological sciences, use rational norms to explain why simple cognitive algorithms can succeed. We also present new computer simulations that compare Take-the-Best with other cognitive models. Although Take-the-Best still performs well, it does not perform noticeably better than the other models. We conclude that these results provide no strong reason to prefer Take-the-Best over alternative cognitive models. (shrink)

Can the output of human cognition be predicted from the assumption that it is an optimal response to the information-processing demands of the environment? A methodology called rational analysis is described for deriving predictions about cognitive phenomena using optimization assumptions. The predictions flow from the statistical structure of the environment and not the assumed structure of the mind. Bayesian inference is used, assuming that people start with a weak prior model of the world which they integrate with experience to develop (...) stronger models of specific aspects of the world. Cognitive performance maximizes the difference between the expected gain and cost of mental effort. Memory performance can be predicted on the assumption that retrieval seeks a maximal trade-off between the probability of finding the relevant memories and the effort required to do so; in categorization performance there is a similar trade-off between accuracy in predicting object features and the cost of hypothesis formation; in casual inference the trade-off is between accuracy in predicting future events and the cost of hypothesis formation; and in problem solving it is between the probability of achieving goals and the cost of both external and mental problem-solving search. The implemention of these rational prescriptions in neurally plausible architecture is also discussed. (shrink)

'The Probabilistic Mind' is a follow-up to the influential and highly cited 'Rational Models of Cognition'. It brings together developments in understanding how, and how far, high-level cognitive processes can be understood in rational terms, and particularly using probabilistic Bayesian methods.

This book offers a philosophy for error-prone humans trying to understand messy systems in the real world.

The vivid terms, "Top-down" and "Bottom-up" have become popular in several different contexts in cognitive science. My task today is to sort out some different meanings and comment on the relations between them, and their implications for cognitive science.