Despite their success in describing and predicting cognitive behavior, the plausibility of so-called ‘rational explanations’ is often contested on the grounds of computational intractability. Several cognitive scientists have argued that such intractability is an orthogonal pseudoproblem, however, since rational explanations account for the ‘why’ of cognition but are agnostic about the ‘how’. Their central premise is that humans do not actually perform the rational calculations posited by their models, but only act as if they do. Whether or not the problem (...) of intractability is solved by recourse to ‘as if’ explanations critically depends, inter alia, on the semantics of the ‘as if’ connective. We examine the five most sensible explications in the literature, and conclude that none of them circumvents the problem. As a result, rational ‘as if’ explanations must obey the minimal computational constraint of tractability. (shrink)

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. (shrink)

Leech et al. present a connectionist algorithm as a model of (the development) of analogizing, but they do not specify the algorithm's associated computational-level theory, nor its computational complexity. We argue that doing so may be essential for connectionist cognitive models to have full explanatory power and transparency, as well as for assessing their scalability to real-world input domains.

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)

Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking. To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking.’ We prove that (...) theory of mind reasoning, so formalized, indeed is intractable. Using parameterized complexity we prove, however, that the ‘order parameter’ is not a source of intractability. We furthermore consider a set of alternative parameters and investigate which of them are sources of intractability. We discuss the implications of these results for the understanding of theory of mind. (shrink)

Posner & Raichle (1994) is a nice addition to the Scientific American Library and the average reader will both enjoy the book and learn a great deal. As an activeresearcher, however, I find the book disappointing in many respects. My two major disappointments are in the illusion of computation that is created throughout the volume and in the inadequate perspective of the presentation on visual attention.

We examine the verification of simple quantifiers in natural language from a computational model perspective. We refer to previous neuropsychological investigations of the same problem and suggest extending their experimental setting. Moreover, we give some direct empirical evidence linking computational complexity predictions with cognitive reality.<br>In the empirical study we compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and push-down automata is psychologically relevant. Our research improves upon hypothesis and (...) explanatory power of recent neuroimaging studies as well as provides<br>evidence. (shrink)

The authors ofImages of the Mindhave made a significant contribution to our understanding of the brain through imaging technology. The book is well written, timely, beautifully illustrated and conveys a sense of history. It will appeal to alay audience as well as a professional audience.

There are methodological problems with the new techniques reviewed by Posner & Raichle. Some brain mechanisms are not detected by the temporal and spatial resolution. Questions are also raised by the stimulation paradigms.

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.

Images of mindsuperbly summarizes work on cognitive neuroscienee using PET scanning. Some of the data emphasized suggests that parietal cortex is involved in the disengagement of attention. We have discovered neurons in awake monkeys which could perform this function. Another point of emphasis is the concept of neutral cues. Although an appealing concept, it is extremely difficult to define what is actually neutral.

Experiments are presented showing that visual search for Mueller-Lyer (ML) stimuli is based on complete configurations, rather than component segments. Segments easily detected in isolation were difficult to detect when embedded in a configuration, indicating preemption by low-level groups. This preemption—which caused stimulus components to become inaccessible to rapid search—was an all-or-nothing effect, and so could serve as a powerful test of grouping. It is shown that these effects are unlikely to be due to blurring by simple spatial filters at (...) early visual levels. It is proposed instead that they are due to more sophisticated processes that rapidly bind contour fragments into spatially-extended assemblies. These results support the view that rapid visual search cannot access the primitives formed at the earliest stages of visual processing; rather, it can access only higher-level, more ecologically-relevant structures. (shrink)

This volume explores how functional brain imaging techniques like positron emission tomography have influenced cognitive studies. The first chapter outlines efforts to relate human thought and cognition in terms of great books from the late 1800s through the present. Chapter 2 describes mental operations as they are measured in cognitive science studies. It develops a framework for relating mental operations to activity in nerve cells. In Chapter 3, the PET method is reviewed and studies are presented that use PET to (...) map the striate cortex and to activate extrastriate motion, color, and form areas. Chapter 4 shows how top down processes involving attention can lead to activation of these same areas in the detection of targets, visual search, and visual imagery. This chapter reveals complex networks of activations. Chapters 5 and 6 deal with the presentation of words. Chapter 5 illustrates PET studies of the anatomy of visual word processing and shows how the circuitry used for generating novel uses of words changes as the task becomes automated. Chapter 6 applies high density electrical recording to explore these activations in real time and to show how a constant anatomy can be reprogrammed by task instructions to produce and perform different cognitive tasks. Chapter 7 shows how studies of brain lesions and PET converge on common networks underlying attentional functions such as visual orienting, target detection, and maintenance of the alert state. Chapters 8 and 9 apply the network approach to examine normal development of attention in infants and pathological conditions resulting from brain damage, and psychiatric pathologies of depression, schizophrenia, and attention deficit disorder. In Chapter 10, new developments such as functional MRI are discussed in terms of future developments and integration of cognitive neuroscience. (shrink)

We divided the many diverse comments on our book into categories. These are: theory, scope and goals of our project, methods, comments on specific anatomical areas, the concept of attention, consciousness and cognitive control, and finally other issues. Although many of the points of the critics are certainly well taken, we believe studies that have emerged since our book provide strong evidence that the general approach taken in our book is now yielding important new data on the relation of cognitive (...) processes to underlying brain activity. (shrink)

PET studies in domains like vision and attention have been successful because the experiments are the product of highly articulated theories. In contrast, the results of PET studies investigating language processing are difficult to interpret. We suggest that this difficulty is due to the more tentative connection of these experiments with the insights of psycholinguistics and linguistic theory.

In Posner & Raichle's (1994) book, two essential and strictly related limitations of cognitive neurophysiology are not sufficiently enhanced: (1) The problem of “coding,” namely the capability of a natural brain to redefine its own “basic symbols” as a function of a changing environment; (2) the inadequacy of a Hebbian rule to reckon with complex computational problems such as those solved by real brains.

The emperor's new mind (hereafter Emperor) is an attempt to put forward a scientific alternative to the viewpoint of according to which mental activity is merely the acting out of some algorithmic procedure. John Searle and other thinkers have likewise argued that mere calculation does not, of itself, evoke conscious mental attributes, such as understanding or intentionality, but they are still prepared to accept the action the brain, like that of any other physical object, could in principle be simulated by (...) a computer. In Emperor I go further than this and suggest that the outward manifestations ofconscious mental activity cannot even be properly simulated by calculation. To support this view, I use various arguments to show that the results of mathematical insight, in particular, do not seem to be obtained algorithmically. The main thrust ofthis work, however, is to present an overview ofthe present state of physical understanding and to show that an important gap exists at the point where, quantum and classical physics meet, as well as to speculate on how the conscious brain might be taking advantage ofwhatever new physics is needed to fill this gap to achieve its nonalgorithmic effects. (shrink)