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)

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 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)

This book aims to lay bare the logical foundations of tractable reasoning. It draws on Marvin Minsky's seminal work on frames, which has been highly influential in computer science and, to a lesser extent, in cognitive science. Only very few people have explored ideas about frames in logic, which is why the investigation in this book breaks new ground. The apparent intractability of dynamic, inferential reasoning is an unsolved problem in both cognitive science and logic-oriented artificial intelligence. By means (...) of a logical investigation of frames and frame concepts, Andreas devises a novel logic of tractable reasoning, called frame logic. Moreover, he devises a novel belief revision scheme, which is tractable for frame logic. These tractability results shed new light on our logical and cognitive means to carry out dynamic, inferential reasoning. Modularity remains central for tractability, and so the author sets forth a logical variant of the massive modularity hypothesis in cognitive science. (shrink)

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred (...) interpretation, provides evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred (...) interpretation, provides evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

Perception solves computationally demanding problems at lightning fast speed. It recovers sophisticated representations of the world from degraded inputs, often in a matter of milliseconds. Any theory of perception must be able to explain how this is possible; in other words, it must be able to explain perception's computational tractability. One of the few attempts to move toward such an explanation has been the information encapsulation hypothesis, which posits that perception can be fast because it keeps computational costs low by (...) forgoing access to information stored in cognition. I argue that we have no compelling reason to believe that encapsulation explains (or even contributes to an explanation of) perceptual tractability, and much reason to doubt it. This is because there exist much deeper computational challenges for perception than information access, and these threaten to make the costs of access irrelevant. If this is right, it undermines a core computational motivation for encapsulation and sends us back to the drawing board for explanations of perceptual 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)

In the study of cognitive processes, limitations on computational resources (computing time and memory space) are usually considered to be beyond the scope of a theory of competence, and to be exclusively relevant to the study of performance. Starting from considerations derived from the theory of computational complexity, in this paper I argue that there are good reasons for claiming that some aspects of resource limitations pertain to the domain of a theory of competence.

Perception solves computationally demanding problems at lightning fast speed. It recovers sophisticated representations of the world from degraded inputs, often in a matter of milliseconds. Any theory of perception must be able to explain how this is possible; in other words, it must be able to explain perception’s computational tractability. One of the few attempts to move toward such an explanation is the information encapsulation hypothesis, which posits that perception can be fast because it keeps computational costs low by forgoing (...) access to information stored in cognition. I argue that we have no compelling reason to believe that encapsulation explains (or even contributes to an explanation of) perceptual tractability, and much reason to doubt it. This is because there exist much deeper computational challenges for perception than information access, and these threaten to make the costs of access irrelevant. If this is right, it undermines a core computational motivation for encapsulation and sends us back to the drawing board for explanations of perceptual tractability. (shrink)

Figure 1: A pr ototyp ical exa mple of a three-layer feed forward network, used by Plunkett and M archm an (1 991 ) to simulate learning the past-tense of En glish verbs. The inpu t units encode representations of the three phonemes of the present tense of the artificial words used in this simulation. Th e netwo rk is trained to produce a representation of the phonemes employed in the past tense form and the suffix (/d/, /ed/, or /t/) (...) used on regular verbs. To run the network, each input unit is assigned an activation value o f 0 or 1 , dep ending on whethe r the featu re is present or not. Eac h input unit is conne cted to each of the 30 hidden units by a we ighted conn ection and p rovid es an inp ut to each hidden unit equal to the product of the input unit's activation and the weight. Each hidd en unit's activation is then determined by summing ov er the va lues co ming fro m each inp ut unit to deter mine a netinput, and then applying a non-linear function (e.g., the logistic function 1/(1+e^netinput). Th is whole proced ure is. (shrink)

Intractability is a growing concern across the cognitive sciences: while many models of cognition can describe and predict human behavior in the lab, it remains unclear how these models can scale to situations of real-world complexity. Cognition and Intractability is the first book to provide an accessible introduction to computational complexity analysis and its application to questions of intractability in cognitive science. Covering both classical and parameterized complexity analysis, it introduces the mathematical concepts and proof techniques that can (...) be used to test one's intuition of tractability. It also describes how these tools can be applied to cognitive modeling to deal with intractability, and its ramifications, in a systematic way. Aimed at students and researchers in philosophy, cognitive neuroscience, psychology, artificial intelligence, and linguistics who want to build a firm understanding of intractability and its implications in their modeling work, it is an ideal resource for teaching or self-study. (shrink)

In recent decades, a new scientific approach to understand, explain, and predict many features of religion has emerged. The cognitive science of religion has amassed research on the forces that shape the tendency for humans to be religious and on what forms belief takes. It suggests that religion, like language or music, naturally emerges in humans with tractable similarities. This new approach has profound implications for how we understand religion, including why it appears so easily, and why people are (...) willing to fight-and die for it. Yet it is not without its critics, and some fear that scholars are explaining the ineffable mystery of religion away, or by showing that religion is natural proves or disproves the existence of God. An Introduction to the Cognitive Science of Religion offers students and general readers an accessible introduction to the approach, providing an overview of key findings and the debates that shape it. The volume includes a glossary of key terms, and each chapter includes suggestions for further thought and further reading as well as chapter summaries highlighting key points. This book is an indispensable resource for introductory courses on religion and a much-needed option for advanced courses. (shrink)

Ownership is universal and ubiquitous in human societies, yet the psychology underpinning ownership intuitions is generally not described in a coherent and computationally tractable manner. Ownership intuitions are commonly assumed to derive from culturally transmitted social norms, or from a mentally represented implicit theory. While the social norms account is entirelyad hoc, the mental theory requires prior assumptions about possession and ownership that must be explained. Here I propose such an explanation, arguing that the intuitions result from the interaction (...) of two cognitive systems. One of these handles competitive interactions for the possession of resources observed in many species including humans. The other handles mutually beneficial cooperation between agents, as observed in communal sharing, collective action and trade. Together, these systems attend to specific cues in the environment, and produce definite intuitions such as “this is hers,” “that is not mine.” This computational model provides an explanation for ownership intuitions, not just in straightforward cases of property, but also in disputed ownership (squatters, indigenous rights), historical changes (abolition of slavery), as well as apparently marginal cases, such as the questions, whether people own their seats on the bus, or their places in a queue, and how people understand “cultural appropriation” and slavery. In contrast to some previous theories, the model is empirically testable and free ofad hocstipulations. (shrink)

This paper focuses on the cognitive/computational and evolutionary levels. It describes three proposals to make cognition computationally tractable, namely: Resource Rationality, the Adaptive Toolbox and Massive Modularity. While each of these proposals appeals to evolutionary considerations to dissolve the intractability of cognition, Rich, Blokpoel, de Haan, and van Rooij argue that, in each case, the intractability challenge is not resolved, but just relocated to the level of evolution.

This paper focuses on the cognitive/computational and evolutionary levels. It describes three proposals to make cognition computationally tractable, namely: Resource Rationality, the Adaptive Toolbox and Massive Modularity. While each of these proposals appeals to evolutionary considerations to dissolve the intractability of cognition, Rich, Blokpoel, de Haan, and van Rooij argue that, in each case, the intractability challenge is not resolved, but just relocated to the level of evolution.

The third part, Cognition, concerns abstract questions about knowledge and truth as well as more concrete questions about the usefulness and tractability of various graphic representations of information. The book would be of special interest to Research Institutes in Computer Science, Researchers in Philosophical Logic, Deontic Logic, Applied Logic, Artificial Intelligence, and Cognitive Science.

This chapter contains sections titled: Introduction Antipredatory Behavior in Western Evening Grosbeaks and its Relevance to Action Theory Social Play Behavior and Action Theory References Further reading.

The theory of psychosis and autism as diametrical disorders offers a tractable and testable view of normal and abnormal human cognitive variation as a function of opposing traits grouped by their selection for maternal and paternal reproductive fitness. The theory could be usefully rooted and developed with reference to the lower-level perceptual and attentional phenomena from which social cognitive modules are developmentally refined.

A central aim of cognitive science is to understand the fundamental mechanisms that enable humans to navigate and make sense of complex environments. In this letter, we argue that computational complexity theory, a foundational framework for evaluating computational resource requirements, holds significant potential in addressing this challenge. As humans possess limited cognitive resources for processing vast amounts of information, understanding how humans perform complex cognitive tasks requires comprehending the underlying factors that drive information processing demands. Computational complexity theory provides a (...) comprehensive theoretical framework to achieve this goal. By adopting this framework, we can gain new insights into how cognitive systems work and develop a more nuanced understanding of the relation between task complexity and human behavior. We provide empirical evidence supporting our argument and identify several open research questions and challenges in applying computational complexity theory to human decision‐making and cognitive science at large. (shrink)

The problem of the cognitive penetrability of perception pertains to whether perceptual processing may be impacted by higher-order cognitive processes. It may be understood in a twofold sense: 1) whether what a perceptual system computes may be altered in a way that is semantically coherent to one’s cognitive states; 2) whether perceptual experience may be influenced by cognitive processes. It has been argued that the cognitive penetrability problem is not scientifically tractable since we have no direct access to other (...) persons’ subjective experiences and, therefore, we have to rely on their reports, which are mediated by higher-order processes (e.g., judgments). In this paper, I analyze the scope of methods harnessed in contemporary work on the penetrability of perception, focusing particularly on methods from experimental psychology and neuroscience. Among them, I indicate the most promising techniques and paradigms, as well as those that are inadequate to successfully tackling the problem. I also discuss experimental results which unequivocally suggest direct influences on perception which have not been addressed to date by supporters of the view that perception is impenetrable. I also describe the predictive processing theory of cognition, focusing on how it contributes to our understanding of cognitive penetrability, and discuss scientific results validating the theory. In conclusion, converging empirical evidence seems to suggest that perception is cognitively penetrable and we seem to be at the dawn of the ultimate solution of the problem. (shrink)

The target article makes a compelling case for the idea that agents rely on the world for external memory in fast-paced perceptual tasks. As I argue, however, agents also rely on the external environment for computational hardware that helps to keep cognitive computations tractable. Hence the external world provides not only memory for computations involving perceptual system actions, but it provides domain-level actions that figure in cognitive computations as well.

Why should anybody care about theoretical simplicity? It is pretty clear that simpler theories don't stand a better chance of being true, just because they are simpler than their competitors. Of course, simpler theories are easier to use in technological applications, and they are more tractable. But that is something engineers should be concerned about. Why should the theoretical scientist be interested in simple theories? ;The principal virtue of simple theories is their facilitation of scientific understanding in virtue of (...) their greater explanatory power. Simple theories are more unified, and they allow important kinds of reasoning about the world. If a theory yields a unified but structure-rich picture of the world, and thereby a high degree of understanding, we can design relevant experiments, form rational expectations, and in general are in a better position to gather relevant data than when we confront the world without any understanding whatsoever. Simple theories are therefore, in virtue of increasing our understanding, epistemically advantageous. That's why the theoretical scientist should be interested in simple theories. ;Of course, since the choice of simple theories does not guarantee getting closer to the truth, the claim that such a choice is epistemically advantageous presupposes that we draw a distinction between the explanatory power of theories and their accuracy. This distinction has not received sufficient attention in the existing literature, and that's why it was so difficult to say exactly what the virtue of simple theories is. Recognizing that explanatory power and accuracy are orthogonal aspects of scientific theories allows us to assign simplicity the role of facilitating understanding and thereby guiding controlled experimentation. (shrink)

According to the traditional nomological-deductive methodology of physics and chemistry [Hempel and Oppenheim, 1948], explaining a phenomenon means subsuming it under a law. Logic becomes then the glue of explanation and laws the primary explainers. Thus, the scientific study of a system would consist in the development of a logically sound model of it, once the relevant observables (state variables) are identified and the general laws governing their change (expressed as differential equations, state transition rules, maximization/minimization principles,. . . ) (...) are well determined, together with the initial or boundary conditions for each particular case. Often this also involves making a set of assumptions about the elementary components of the system (e.g., their structural and dynamic properties) and modes of local interaction. In this framework, predictability becomes the main goal and that is why research is carried out through the construction of accurate mathematical models. Thus, physics and chemistry have made most progress so far by focusing on systems that, either due to their intrinsic properties or to the conditions in which they are investigated, allow for very strong simplifying assumptions, under which, nevertheless, those highly idealized models of reality are deemed to be in good correspondence with reality itself. Despite the enormous success that this methodology has had, the study of living and cognitive phenomena had to follow a very different road, because these phenomena are produced by systems whose underlying material structure and organization do not permit such crude approximations. Seen from the perspective of physics or chemistry, biological and cognitive systems are made of an enormous number of parts or elements interacting in non-linear and selective ways, which makes very difficult their tractability through mathematical models. In addition, many of those interacting elements are hierarchically organized, in a way that the “macroscopic” (observable) parts behave according to rules that cannot be, in practice, derived from simple principles at the level of their “microscopic” dynamics.. (shrink)

De Neys (2021) argues that the debate between single- and dual-process theorists of thought has become both empirically intractable and scientifically inconsequential. I argue that this is true only under the traditional framing of the debate—when single- and dual-process theories are understood as claims about whether thought processes share the same defining properties (e.g., making mathematical judgments) or have two different defining properties (e.g., making mathematical judgments autonomously versus via access to a central working memory capacity), respectively. But if single- (...) and dual-process theories are understood in cognitive modeling terms as claims about whether thought processes function to implement one or two broad types of algorithms, respectively, then the debate becomes scientifically consequential and, presumably, empirically tractable. So, I argue, the correct response to the current state of the debate is not to abandon it, as De Neys suggests, but to reframe it as a debate about cognitive models. (shrink)

Given the very large numbers of documents involved in e-discovery investigations, lawyers face a considerable challenge of collaborative sensemaking. We report findings from three workplace studies which looked at different aspects of how this challenge was met. From a sociotechnical perspective, the studies aimed to understand how investigators collectively and individually worked with information to support sensemaking and decision making. Here, we focus on discovery-led refinement; specifically, how engaging with the materials of the investigations led to discoveries that supported refinement (...) of the problems and new strategies for addressing them. These refinements were essential for tractability. We begin with observations which show how new lines of enquiry were recursively embedded. We then analyse the conceptual structure of a line of enquiry and consider how reflecting this in e-discovery support systems might support scalability and group collaboration. We then focus on the individual activity of manual document review where refinement corresponded with the inductive identification of classes of irrelevant and relevant documents within a collection. Our observations point to the effects of priming on dealing with these efficiently and to issues of cognitive ergonomics at the human–computer interface. We use these observations to introduce visualisations that might enable reviewers to deal with such refinements more efficiently. (shrink)

Since Darwin, the idea of psychological continuity between humans and other animals has dominated theory and research in investigating the minds of other species. Indeed, the field of comparative psychology was founded on two assumptions. First, it was assumed that introspection could provide humans with reliable knowledge about the causal connection between specific mental states and specific behaviors. Second, it was assumed that in those cases in which other species exhibited behaviors similar to our own, similar psychological causes were at (...) work. In this paper. we show how this argument by analogy is flowed with respect to the case of second-order mental states. As a test case, we focus on the question of how other species conceive of visual attention, and in particular whether chimpanzees interpret seeing as a mentalistic event involving internal states of perception, attention, and belief. We conclude that chimpanzees do not reason about seeing in this manner, and indeed, there is considerable reason to suppose that they do not harbor representations of mental states in general. We propose a reinterpretation model in which the majority of the rich social behaviors that humans and other primates share in common emerged long before the human lineage evolved the psychological means of interpreting those behaviors in mentalistic terms. Although humans, chimpanzees, and most other species may be said to possess mental states, humans alone may have evolved a cognitive specialization for reasoning about such states. (shrink)

This paper sketches a solution to a problem which has been emphasized by Fodor. This is the problem of how to explain distinctively-human flexible cognition in modular terms. There are three aspects to the proposed account. First, it is suggested that natural language sentences might serve to integrate the outputs of a number of conceptual modules. Second, a creative sentence-generator, or supposer, is postulated. And third, it is argued that a set of principles of inference to the best explanation (...) can be constructed from already-extant aspects of linguistic testimony and discourse interpretation. Most importantly, it is suggested that the resulting architecture should be implementable in ways that are computationally tractable. (shrink)

Context: Direct realism is a non-reductive, anti-representationalist theory of perception lying at the heart of mainstream analytic philosophy, where it is currently generating a lot of interest. For all that, it is widely held to be both controversial and anti-scientific. On the other hand, the sensorimotor theory of perception initially generated a lot of interest within enactive philosophy of cognitive science, but has arguably not yet delivered on its initial promise. Problem: I aim to show that the sensorimotor theory and (...) direct realism complement each other, and that the result is a philosophically radical, but fully scientifically realised, theory of perception. Method: The article uses philosophical analysis and discussion. It also draws on empirical evidence from the relevant cognitive sciences. Results: Direct realism can be augmented by sensorimotor theory to become a scientifically tractable alternative to the mainstream, representationalist research programme within cognitive science. Implications: The article aims to further clarify the philosophical importance of the sensorimotor approach to perception. It also aims to show that the apparently radical claim that we perceive objects themselves is amenable to normal scientific study. Constructivist content: Objects are analysed as a kind of collaboration between the world and the perceiver. On this account, we can never perceive outside the categories of our own understanding, but we do perceive genuinely outside our own heads. Thus, the approach here is not exactly constructivism, though it shares many goals and results with constructivism. (shrink)

Scientists are rapidly mapping the chemical and physical pathways that constitute biological systems, making the complexity of processes such as inheritance, development, evolution, and even the origin of life increasingly tractable. Through genetics and neuroscience, biological understanding is now being extended deeply into the human sciences and has begun to transform our understanding of behavior, mind, culture, and values. The idea of a science-driven unity of knowledge has reemerged in several forms in both reductionist and nonreductionist frameworks. This volume (...) examines some of the extraordinary empirical discoveries that have caused a revival of this idea and presents theories from thinkers in a variety of disciplines, including E. O. Wilson, Eric Kandel, and Elaine Scarry. (shrink)

In this paper, I defend Non-Inferentialism about mental states, the view that we can perceive some mental states in a direct, non-inferential way. First, I discuss how the question of mental state perception is to be understood in light of recent debates in the philosophy of perception, and reconstruct Non-Inferentialism in a way that makes the question at hand—whether we can perceive mental states or not—scientifically tractable. Next, I motivate Non-Inferentialism by showing that under the assumption of the widely-accepted (...) Principle of Cognitive Economy, any account that treats mental state perception as an inferential process commits itself to an unrealistically inefficient picture of our cognitive architecture. Drawing on research in cognitive science, I will then show that my Non-Inferentialist view receives direct support by the available empirical evidence. I conclude that there is no psychologically relevant sense in which perception of mental states differs from paradigmatic cases of perception, such as the perception of ordinary objects. (shrink)

Tetris provides a difficult, dynamic task environment within which some people are novices and others, after years of work and practice, become extreme experts. Here we study two core skills; namely, choosing the goal or objective function that will maximize performance and a feature-based analysis of the current game board to determine where to place the currently falling zoid so as to maximize the goal. In Study 1, we build cross-entropy reinforcement learning models to determine whether different goals result in (...) different feature weights. Two of these optimization strategies quickly rise to performance plateaus, whereas two others continue toward higher but more jagged heights. In Study 2, we compare the zoid placement decisions made by our best CERL models with those made by 67 human players. Across 370,131 human game episodes, two CERL models picked the same zoid placements as our lowest scoring human for 43% of the placements and as our three best scoring experts for 65% of the placements. Our findings suggest that people focus on maximizing points, not number of lines cleared or number of levels reached. They also show that goal choice influences the choice of zoid placements for CERLs and suggest that the same is true of humans. Tetris has a repetitive task structure that makes Tetris more tractable and more like a traditional experimental psychology paradigm than many more complex games or tasks. Hence, although complex, Tetris is not overwhelmingly complex and presents a right-sized challenge to cognitive theories, especially those of integrated cognitive systems. (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)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial (...) time. Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

Tetris provides a difficult, dynamic task environment within which some people are novices and others, after years of work and practice, become extreme experts. Here we study two core skills; namely, choosing the goal or objective function that will maximize performance and a feature-based analysis of the current game board to determine where to place the currently falling zoid so as to maximize the goal. In Study 1, we build cross-entropy reinforcement learning models to determine whether different goals result in (...) different feature weights. Two of these optimization strategies quickly rise to performance plateaus, whereas two others continue toward higher but more jagged heights. In Study 2, we compare the zoid placement decisions made by our best CERL models with those made by 67 human players. Across 370,131 human game episodes, two CERL models picked the same zoid placements as our lowest scoring human for 43% of the placements and as our three best scoring experts for 65% of the placements. Our findings suggest that people focus on maximizing points, not number of lines cleared or number of levels reached. They also show that goal choice influences the choice of zoid placements for CERLs and suggest that the same is true of humans. Tetris has a repetitive task structure that makes Tetris more tractable and more like a traditional experimental psychology paradigm than many more complex games or tasks. Hence, although complex, Tetris is not overwhelmingly complex and presents a right-sized challenge to cognitive theories, especially those of integrated cognitive systems. (shrink)

Most of us create and use a panoply of non-sentential representations throughout our ordinary lives: we regularly use maps to navigate, charts to keep track of complex patterns of data, and diagrams to visualize logical and causal relations among states of affairs. But philosophers typically pay little attention to such representations, focusing almost exclusively on language instead. In particular, when theorizing about the mind, many philosophers assume that there is a very tight mapping between language and thought. Some analyze utterances (...) as the outer vocalizations of inner thoughts (e.g. Grice 1957, Devitt 2005), while others treat thought as a form of inner speech (e.g. Sellars 1956/1997, Carruthers 2002). But even philosophers who take no stand on the relative priority of language and thought still tend to individuate mental states in terms of the sentences we use to ascribe them. Indeed, Dummett (1993) claims that it is constitutive of analytic philosophy that it approaches the mind by way of language. In many ways, this linguistic model is salutary. Our thoughts are often intimately intertwined with their linguistic expression, and public language does provide a comparatively tractable proxy for, and a window into, the messier realm of thought. However, an exclusive focus on thought as it is expressed in language threatens to leave other sorts of thought unexplained, or even to blind us to their possibility. In particular, many cognitive ethologists and psychologists find it useful to talk about humans, chimpanzees, birds, rats, and even bees as employing cognitive maps. We need to make sense of this way of talking about minds as well as more familiar sentential descriptions. In what follows, I investigate the theoretical and practical possibility of non-sentential thought. Ultimately, I am most interested in the contours of distinctively human thought: what forms does human thought take, and how do those different forms interact? How does human thought compare with that of other animals? In this essay, however, I focus on a narrower and more basic theoretical question: could thought occur in maps? Many philosophers are convinced that in some important sense, thought per se must be language-like.. (shrink)

This paper argues that a popular account of intentions can be extended to beliefs. Beliefs are stable all-out states that allow for planning and coordination in a way that is tractable for cognitively limited creatures like human beings. Scepticism is expressed that there is really anything like credences as standardly understood.

Notice that this paper has not claimed that all natural languages are CFL's. What it has shown is that every published argument purporting to demonstrate the non-context-freeness of some natural language is invalid, either formally or empirically or both.18 Whether non-context-free characteristics can be found in the stringset of some natural language remains an open question, just as it was a quarter century ago.Whether the question is ultimately answered in the negative or the affirmative, there will be interesting further questions (...) to ask. If it turns out that natural languages are indeed always CFL's, it will be reasonable to ask whether this helps to explain why speakers apparently recognize so quickly whether a presented utterance corresponds to a grammatical sentence or not, and to associate structural and semantic details with it. It might also be reasonable to speculate about the explanation for the universally context-free character of the languages used by humans, and to wonder whether evolutionary biological factors are implicated in some way (Sampson (1979) could be read in this light). And naturally, it will be reasonable to pursue the program put forward by Gazdar (1981, in press) to see to what extent CFL-inducing grammatical devices can be exploited to yield insightful descriptions of natural languages that capture generalizations in revealing ways.If a human language that is not a CFL is proved to exist, on the other hand, a different question will be raised: give the non-context-free character of human languages in general, why has this property been so hard to demonstrate that it has taken over twenty-five years to bring it to light since the issue was first explicitly posed? If human languages do not have to be CFL's, why do so many (most?) of them come so close to having the property of context-freeness? And, since the CFL's certainly constitute a very broad class of mathematically natural and computationally tractable languages, what property of human beings or their communicative or cognitive needs is it that has caused some linguistic communities to reach beyond the boundaries of this class in the course of evolving a linguistic system?Either way, we shall be interested to see our initial question resolved, and further questions raised. One cautionary word should be said, however, about the implications (or lack of them) that the answer will have for grammatical studies. Chomsky has repeatedly stated that he does not see weak generative capacity as a theme of central importance in the theory of grammar, and we agree. It is very far from being the case that the recent resurgence of interest in exploring the potential of CF-PSG or equivalent systems will, or should, be halted dead in its tracks by the discovery (if it is ever forthcoming) that some natural language is not a CFL. In the area of parsing, for instance, it seems possible that natural languages are not only parsed on the basis of constituent structure such as a CF-PSG would assign, but are parsed as if they were finite state languages (see Langendoen (1975) and Church (1980) for discussion along these lines). That is, precisely those construction-types that figure in the various proofs that English is not an FSL appear to cause massive difficulty in the human processing system; the sentences crucial to the proofs are for the most part unprocessable unless they are extremely short (yet the arguments for English not being and FSL only go through if length is not an issue). This means that in practice properties of finite state grammars are still of great potential importance to linguistic theory despite the fact that they do not provide the framework for defining the total class of grammatical sentences. The same would almost certannly be true of CF-PSG's if they were shown to be inadequate in a similar sense. It is highly unlikely that the advances made so far in far in phrase structure description could be nullified by a discovery about weak generative capacity. Moreover, there are known to be numerous ways in which the power of CF-PSG's can be marginally enhanced to permit, for example, xx languages to be generated without allowing anything like the full class of recursively enumerable or even context-sensitive languages (see Hopcroft and Ullmann (1979), Chapter 14) for an introduction to this topic, noting especially Figure 14.7 on p. 393. The obvious thing to do if natural languages were ever shown not to be CFL's in the general case would be to start exploring such minimal enhancements of expressive power to determine exactly what natural languages call for in this regard and how it could be effectively but parsimoniously provided in a way that closely modelled human linguistic capacities.In the meantime, it seems reasonable to assume that the natural languages are a proper subset of the infinite-cardinality CFL's until such time as they are validly shown not to be. (shrink)