In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly work as computational (...) models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order (classical) systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

Following Marr’s famous three-level distinction between explanations in cognitive science, it is often accepted that focus on modeling cognitive tasks should be on the computational level rather than the algorithmic level. When it comes to mathematical problem solving, this approach suggests that the complexity of the task of solving a problem can be characterized by the computational complexity of that problem. In this paper, I argue that human cognizers use heuristic and didactic tools and thus engage in cognitive processes that (...) make their problem solving algorithms computationally suboptimal, in contrast with the optimal algorithms studied in the computational approach. Therefore, in order to accurately model the human cognitive tasks involved in mathematical problem solving, we need to expand our methodology to also include aspects relevant to the algorithmic level. This allows us to study algorithms that are cognitively optimal for human problem solvers. Since problem solving methods are not universal, I propose that they should be studied in the framework of enculturation, which can explain the expected cultural variance in the humanly optimal algorithms. While mathematical problem solving is used as the case study, the considerations in this paper concern modeling of cognitive tasks in general. (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)

By reviewing most of the neurobiology of consciousness, this article highlights some major reasons why a successful emulation of the dynamics of human consciousness by artificial intelligence is unlikely. The analysis provided leads to conclude that human consciousness is epigenetically determined and experience and context-dependent at the individual level. It is subject to changes in time that are essentially unpredictable. If cracking the code to human consciousness were possible, the result would most likely have to consist of a temporal pattern (...) code simulating long-distance signal reverberation and de-correlation of all spatial signal contents from temporal signals. In the light of the massive evidence for complex interactions between implicit (non-conscious) and explicit (conscious) contents of representation, the code would have to be capable of making implicit (non-conscious) processes explicit. It would have to be capable of a progressively less and less arbitrary selection of temporal activity patterns in a continuously developing neural network structure identical to that of the human brain, from the synaptic level to that of higher cognitive functions. The code’s activation thresholds would depend on specific temporal signal coincidence probabilities, vary considerably with time and across individual experience data, and would therefore require dynamically adaptive computations capable of emulating the properties of individual human experience. No known machine or neural network learning approach has such potential. (shrink)

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)

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)

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)

Images of mindis an exciting book, well-written and wellorganized, but many of the connections the authors draw between PET scan results and more general psychological issues are somewhat strained.

Research reported by Posner & Raichle may be usefully applied to the rehabilitation of persons with brain damage. Their findings are related to the “dual premotorsystems hypothesis” that reciprocally interactive medial and lateral brain systems are involved in attention and learning. Recent studies show that “brain healing” occurs through dynamic reorganization involving attentional networks postulated by Posner & Raichle.

On the basis of neuroiinaging studies, Posner & Raichle summarily report that the prefrontal cortex is involved in executive functioning and attention. In contrast to that superficial view, we briefly describe a testable model of the kinds of representations that are stored in prefrontal cortex, which, when activated, are expressed via plans, actions, thematic knowledge, and schemas.

A methodological problem may distort the implications derived from the metabolism scans of the brain, but Posner & Raichle may have found neural networks which underlie the analytical and synthetical hemispheric data processing mechanism. This methodological problem is that a large regional consumption of energy, detected by the PET technique, is not necessarily related to more data processing. It may be related to the inefficiency of the neural system at this region.

Encoding articulate speech is widely accepted as the principal (or sole) role of the frontal operculum. Clinical observations of speech apraxia have been confirmed by brain-imaging studies of speech production. We present evidence that the frontal operculum also programs limb movements. We argue that this area is a ventral counterpart of the dorsal premotor area. The two are functionally distinguished by specialization for somatic and visual space, respectively.

The approach adopted by Posner & Raichle in this book, with its strong emphasis on the cognitive level of description, is ideally suited to the study of psychotic illnesses. However, their discussion of depression and schizophrenia is based on a very small number of studies and involves ad hoc arguments derived largely from neuroanatomy. Their conclusions are almost certainly wrong.

In interpreting measurements of brain processes it is necessary to make the model used explicit. A concept such as attention cannot be used in the description of brain activities without a model of the relation of mental and neural processes.

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)

Pictures of normal brain activity during human thought can be worth a great deal. Electrophysiology and functional neuroimaging together allow both temporal and spatial dimensions of neurocognitive functions to be explored. Although these techniqueshave their limitations, the Cognitive Neuroscience approach is well-suited to pursuing questions about how words are perceived, understood, and remembered.

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 authors ofImages of mindhave been highly successful in unravelling the neural basis of complex brain functions. Their emphasis on top-down processingin experimental neuroscience is especially important and, it is hoped, influential. Tracking brain activation accurately botli in space and in time would benefit from studiesofindividual subjects without relying on grand average data.

Posner & Raichle'sImages of mindis an excellent educational book and very well written. Some flaws as a scientific publication are: (a) the accuracy of the linear subtraction method used in PET is subject to scrutiny by further research at finer spatial-temporal resolutions; (b) lack of accuracy of the experimental paradigm used for EEG complementary studies.

Posner & Raichle illustrate how neuroimaging blends profitably with neuropsychology and electrophysiology to advance cognitive theory. Recognizing that there are limitations to each of these techniques, we nonetheless argue that their confluence has fundamentally changed the way cognitive psychologists think about problems of the mind.

This is an excellent book but it lacks a detailed presentation and formulation of images of memory. Positron emission tomography (PET) findings sometimes raise more enigmatic questions than they answer, with differences between studies and differences with established lesion evidence. Perhaps the book could have been more critical in its analysis of these enigmas, covering more of the basic issues and assumptions underlying PET research.

PET detects changes in metabolism between task periods and is thus insensitive to areas that are activated during all or most of cognition. Depth-recorded, evokedpotentials indicate that many multimodal and limbic cortical areas may be activated during most cognitive tasks. Thus, PET may be insensitive to some core processes of awareness that are difficult to eliminate from the control periods.

This article describes an implemented architecture for intermediate vision. By integrating a variety of Intermediate visual mechanisms and putting them to use in support of concrete activity, the implementation demonstrates their utility. The sytem, SIVS, models psychophysical discoveries about visual attention and search. It is designed to be efficiently implementable in slow, massively parallel, locally connected hardware, such as that of the brain.SIVS addresses five fundamental problems. Visual attention is required to restrict processing to task-relevant locations in the image. Visual (...) search finds such locations. Visual routines are a means for nonuniform processing based on task demands. Intermediate objects keep track of intermediate results of this processing. Visual operators are a set of relatively abstract, general-purpose primitives for spatial analysis, out of which visual routines are assembled. (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.

We offer an ecological (Gibsonian) alternative to cognitive (im)penetrability. Whereas Pylyshyn explains cognitive (im)penetrability by focusing solely on computations carried out by the nervous system, according to the ecological approach the perceiver as a knowing agent influences the entire animal-environmental system: in the determination of what constitutes the environment (affordances), what constitutes information, what information is detected and, thus, what is perceived.

Posner & Raichle's (1994) exciting, wonderfully illustrated book describes the past successes and future potential of the relatively noninvasive imaging of the nervous systems of living people. The focus has been on cognitive processes but there is no reason why emotional and motivational systems cannot also be tapped. Although the authors do not formally address such contentious issues as consciousness and the private experience of other species, imaging methods may hold promise for helping us to understand these phenomena, as well (...) as to integrate psychological processes into ethological and phylogenetic research in general. (shrink)