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)

The paper is concerned with the psychological relevance of a logical model for deductive reasoning. We propose a new way to analyze logical reasoning in a deductive version of the Mastermind game implemented within a popular Dutch online educational learning system (Math Garden). Our main goal is to derive predictions about the difficulty of Deductive Mastermind tasks. By means of a logical analysis we derive the number of steps needed for solving these tasks (a proxy for working memory load). Our (...) model is based on the analytic tableaux method, known from proof theory. We associate the difficulty of Deductive Mastermind game-items with the size of the corresponding logical trees obtained by the tableaux method. We derive empirical hypotheses from this model. A large group of students (over 37 thousand children, 5–12 years of age) played the Deductive Mastermind game, which gave empirical difficulty ratings of all 321 game-items. The results show that our logical approach predicts these item ratings well, which supports the psychological relevance of our model. (shrink)

Learning theory has frequently been applied to language acquisition, but discussion has largely focused on information theoretic problems—in particular on the absence of direct negative evidence. Such arguments typically neglect the probabilistic nature of cognition and learning in general. We argue first that these arguments, and analyses based on them, suffer from a major flaw: they systematically conflate the hypothesis class and the learnable concept class. As a result, they do not allow one to draw significant conclusions about the learner. (...) Second, we claim that the real problem for language learning is the computational complexity of constructing a hypothesis from input data. Studying this problem allows for a more direct approach to the object of study—the language acquisition device—rather than the learnable class of languages, which is epiphenomenal and possibly hard to characterize. The learnability results informed by complexity studies are much more insightful. They strongly suggest that target grammars need to be objective, in the sense that the primitive elements of these grammars are based on objectively definable properties of the language itself. These considerations support the view that language acquisition proceeds primarily through data-driven learning of some form. (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.

The representational distortion (RD) approach to similarity (e.g., Hahn, Chater, & Richardson, 2003) proposes that similarity is computed using the transformation distance between two entities. We argue that researchers who adopt this approach need to be concerned with how representational transformations can be determined a priori. We discuss several roadblocks to using this approach. Specifically we demonstrate the difficulties inherent in determining what transformations are psychologically salient and the importance of considering the directionality of transformations.

This paper deals with the question: what are the key requirements for a physical system to perform digital computation? Time and again cognitive scientists are quick to employ the notion of computation simpliciter when asserting basically that cognitive activities are computational. They employ this notion as if there was or is a consensus on just what it takes for a physical system to perform computation, and in particular digital computation. Some cognitive scientists in referring to digital computation simply adhere to (...) Turing’s notion of computability . Classical computability theory studies what functions on the natural numbers are computable and what mathematical problems are undecidable. Whilst a mathematical formalism of computability may perform a methodological function of evaluating computational theories of certain cognitive capacities, concrete computation in physical systems seems to be required for explaining cognition as an embodied phenomenon . There are many non-equivalent accounts of digital computation in physical systems. I examine only a handful of those in this paper: (1) Turing’s account ; (2) The triviality “account”; (3) Reconstructing Smith’s account of participatory computation ; (4) The Algorithm Execution account . My goal in this paper is twofold. First, it is to identify and clarify some of the underlying key requirements mandated by these accounts. I argue that these differing requirements justify a demand that one commits to a particular account when employing the notion of computation in regard to physical systems. Second, it is to argue that despite the informative role that mathematical formalisms of computability may play in cognitive science, they do not specify the relationship between abstract and concrete computation. (shrink)

Barnes, A. and P. Thagard Empathy and analogy. Dialogue: Canadian Philosophical Review, 36: 705-720. HTML Croft, D., & Thagard, P.. Dynamic imagery: A computational model of motion and visual analogy. In L. Magnani and N. Nersessian, Model-based reasoning: Science, technology, values. New York: Kluwer/Plenum, 259-274. PDF only. HTML description of program and code for DIVA.

The dominant practice of AI alignment assumes (1) that preferences are an adequate representation of human values, (2) that human rationality can be understood in terms of maximizing the satisfaction of preferences, and (3) that AI systems should be aligned with the preferences of one or more humans to ensure that they behave safely and in accordance with our values. Whether implicitly followed or explicitly endorsed, these commitments constitute what we term a preferentist approach to AI alignment. In this paper, (...) we characterize and challenge the preferentist approach, describing conceptual and technical alternatives that are ripe for further research. We first survey the limits of rational choice theory as a descriptive model, explaining how preferences fail to capture the thick semantic content of human values, and how utility representations neglect the possible incommensurability of those values. We then critique the normativity of expected utility theory (EUT) for humans and AI, drawing upon arguments showing how rational agents need not comply with EUT, while highlighting how EUT is silent on which preferences are normatively acceptable. Finally, we argue that these limitations motivate a reframing of the targets of AI alignment: Instead of alignment with the preferences of a human user, developer, or humanity-writ-large, AI systems should be aligned with normative standards appropriate to their social roles, such as the role of a general-purpose assistant. Furthermore, these standards should be negotiated and agreed upon by all relevant stakeholders. On this alternative conception of alignment, a multiplicity of AI systems will be able to serve diverse ends, aligned with normative standards that promote mutual benefit and limit harm despite our plural and divergent values. (shrink)

Why should moral philosophers, moral psychologists, and machine ethicists care about computational complexity? Debates on whether artificial intelligence (AI) can or should be used to solve problems in ethical domains have mainly been driven by what AI can or cannot do in terms of human capacities. In this paper, we tackle the problem from the other end by exploring what kind of moral machines are possible based on what computational systems can or cannot do. To do so, we analyze normative (...) ethics through the lens of computational complexity. First, we introduce computational complexity for the uninitiated reader and discuss how the complexity of ethical problems can be framed within Marr’s three levels of analysis. We then study a range of ethical problems based on consequentialism, deontology, and virtue ethics, with the aim of elucidating the complexity associated with the problems themselves (e.g., due to combinatorics, uncertainty, strategic dynamics), the computational methods employed (e.g., probability, logic, learning), and the available resources (e.g., time, knowledge, learning). The results indicate that most problems the normative frameworks pose lead to tractability issues in every category analyzed. Our investigation also provides several insights about the computational nature of normative ethics, including the differences between rule- and outcome-based moral strategies, and the implementation-variance with regard to moral resources. We then discuss the consequences complexity results have for the prospect of moral machines in virtue of the trade-off between optimality and efficiency. Finally, we elucidate how computational complexity can be used to inform both philosophical and cognitive-psychological research on human morality by advancing the moral tractability thesis. (shrink)

Cognitive modules are internal mental structures. Some theorists and empirical researchers hypothesise that the human mind is either partially or massively comprised of structures that are modular in nature. Is the massive modularity of mind hypothesis a cogent view about the ontological nature of human mind or is it, rather, an effective/ineffective adaptationist discovery heuristic for generating predictively successful hypotheses about both heretofore unknown psychological traits and unknown properties of already identified psychological traits? Considering the inadequacies of the case in (...) favour of massive modularity as an ontological hypothesis, I suggest approaching and valuing massive modularity as an adaptationist discovery heuristic. (shrink)

The medium‐independence of computational descriptions has shaped common conceptions of computational explanation. So long as our goal is to explain how a system successfully carries out its computations, then we only need to describe the abstract series of operations that achieve the desired input–output mapping, however they may be implemented. It is argued that this abstract conception of computational explanation cannot be applied to so‐called real‐time computing systems, in which meeting temporal deadlines imposed by the systems with which a device (...) interfaces are constitutive of the computing tasks that a device performs. Instead, real‐time computing reveals the need for alternative conceptions of computational explanation, as well as computational implementation, that eschew medium‐independence. (shrink)

One of the critical issues in the philosophy of science is to understand scientific knowledge. This paper proposes a novel approach to the study of reflection on science, called “cognitive metascience”. In particular, it offers a new understanding of scientific knowledge as constituted by various kinds of scientific representations, framed as cognitive artifacts. It introduces a novel functional taxonomy of cognitive artifacts prevalent in scientific practice, covering a huge diversity of their formats, vehicles, and functions. As a consequence, toolboxes, conceptual (...) frameworks, theories, models, and individual hypotheses can be understood as artifacts supporting our cognitive performance. It is also shown that by empirically studying how artifacts function, we may discover hitherto undiscussed virtues and vices of these scientific representations. This paper relies on the use of language technology to analyze scientific discourse empirically, which allows us to uncover the metascientific views of researchers. This, in turn, can become part of normative considerations concerning virtues and vices of cognitive artifacts. (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)

I propose the notion of ‘epistemic sanity’, a property of parsimony between the holding of true but not false beliefs and the consideration of our cognitive limitations. Where ‘alethic value’ is the epistemic value of holding true but not false beliefs, the ‘alethic potential’ of an agent is the amount of extra alethic value that she is expected to achieve, given her current environment, beliefs, and reasoning skills. Epistemic sanity would be related to the holding of (true or false) beliefs (...) that increase the agent's alethic potential (relevant beliefs) but not of beliefs that decrease it (this is related to cognitive parsimony). Suspension of judgment, forgetting, and clutter avoidance are the main contributors to an agent's epistemic sanity, where this paper focuses on suspension. I argue that rational suspension favors the holding of true and relevant beliefs, which is not the case for the extremes of opinionation (no suspension) and skepticism (general suspension). In the absence of evidence, opinionated agents are often forced to rely on principles such as the principle of indifference, but suspension dominates indifference in terms of alethic value in some conditions. A rational agent would only find it beneficial to adopt skepticism if she considers herself to be an anti-expert about her entire agenda, but then ‘flipping’ beliefs maximizes expected alethic value in relation to skepticism. The study of epistemic sanity results in an ‘impure’ veritism, which can deal with some limitations of veritism (e.g., explaining the existence of false but relevant beliefs). (shrink)

Many scientists routinely generalize from study samples to larger populations. It is commonly assumed that this cognitive process of scientific induction is a voluntary inference in which researchers assess the generalizability of their data and then draw conclusions accordingly. We challenge this view and argue for a novel account. The account describes scientific induction as involving by default a generalization bias that operates automatically and frequently leads researchers to unintentionally generalize their findings without sufficient evidence. The result is unwarranted, overgeneralized (...) conclusions. We support this account of scientific induction by integrating a range of disparate findings from across the cognitive sciences that have until now not been connected to research on the nature of scientific induction. The view that scientific induction involves by default a generalization bias calls for a revision of the current thinking about scientific induction and highlights an overlooked cause of the replication crisis in the sciences. Commonly proposed interventions to tackle scientific overgeneralizations that may feed into this crisis need to be supplemented with cognitive debiasing strategies against generalization bias to most effectively improve science. (shrink)

Cognitive modules are internal mental structures. Some theorists and empirical researchers hypothesize that the human mind is either partially or massively comprised of structures that are modular in nature. Modules are also invoked to explain cognitive capacities associated with the performance of specific functional tasks. Jerry Fodor (1983) considered that modules are useful only for explaining relatively low-level systems (input systems). These are the systems involved in capacities like perception and language. For Fodor, the central (high-level) systems of mind — (...) those involved in capacities like judgment (the “fixation of belief” in Fodor’s jargon), planning (practical reasoning), decision-making, and so forth — are not explainable in terms of modular mechanisms. However, some other philosophers as well as proponents and practitioners of evolutionary psychology consider that it is sensible — and even necessary — to invoke modules for explaining these systems, too. Indeed, the debate over modularity is mainly a debate over the modularity of central systems (high-level cognitive capacities). Admittedly, it is also possible to raise doubts about the modularity of peripheral systems (Prinz, 2006), but this kind of skepticism is not widespread in the literature. In contrast, both the empirical and the theoretical (a priori) cases in favor of central modularity are usually contested on multiple fronts and in tough terms. The case for the modularity of central systems is the core of the case for the massive modularity of mind hypothesis (viz. the hypothesis that consists in asserting that both the peripheral and the central systems of human mind are largely composed of modules). Granted, the massive modularity of mind hypothesis is an empirical statement and, as such, its truth should be ultimately decided in an empirical way, not a priori (Sperber, 1994, 2001). Nonetheless, much of the debate over massive modularity has taken place on theoretical grounds. This is due to an alleged underdetermination of the hypotheses regarding the modularity of central systems by data. In such conditions, the remaining open option has been to advance theoretical considerations in favor of the plausibility — and not directly in favor of the empirical truth or truthlikeness — of the massive modularity of mind generally, and of the modularity of some central systems in particular. These theoretical considerations are mostly based on an adaptationist view of evolution cum a classical computationalist approach to mind. They include arguments about the nature and evolution of hierarchically ordered complex systems (the evolvability of complexity argument), a presumption of optimality expressed in the apparent design of phenotypic traits shaped by natural selection (the task-specificity argument) and dismissing nonmodular mental architectures as computationally intractable (the tractability argument). Is the massive modularity of mind hypothesis a cogent view about the ontological nature of human mind or is it, rather, an effective/ineffective adaptationist discovery heuristic for generating predictively successful hypothesis about both heretofore unknown psychological traits and unknown properties of already identified psychological traits? Considering the inadequacies of the case in favor of massive modularity as an ontological hypothesis, I suggest approaching and valuing massive modularity as an adaptationist discovery heuristic. (shrink)

Recent years have seen a Bayesian revolution in cognitive science. This should be of interest to metaphysicians of science, whose naturalist project involves working out the metaphysical implications of our leading scientific accounts, and in advancing our understanding of those accounts by drawing on the metaphysical frameworks developed by philosophers. Toward these ends, in this paper I develop a metaphysics of the Bayesian mind. My central claim is that the Bayesian approach supports a novel empirical argument for normativism, the thesis (...) that belief has a normative essence, with the norms in question being those of rationality. The argument I develop draws in part on the causal powers subset account of realization defended by Wilson and Shoemaker, with the link being that Bayesians often appeal to Marr’s framework of levels of analysis, which carries with it multiple realizability claims that can be understood in terms of the subset model. I then use the view developed, with its appeal to normativism and subset realization, to explain how Bayesians can accommodate empirical findings of irrationality that are sometimes thought to pose a problem for their view. (shrink)

Compositionality has been a central concept in linguistics and philosophy for decades, and it is increasingly prominent in many other areas of cognitive science. Its status, however, remains contentious. Here, I reassess the nature and scope of the principle of compositionality (Partee, 1995) from the perspective of psycholinguistics and cognitive neuroscience. First, I review classic arguments for compositionality and conclude that they fail to establish compositionality as a property of human language. Next, I state a new competence argument, acknowledging the (...) fact that any competent user of a language L can assign to most expressions in L at least one meaning which is a functiononlyof the meanings of the expression's parts and of its syntactic structure. I then discuss selected results from cognitive neuroscience, indicating that the human brain possesses the processing capacities presupposed by the competence argument. Finally, I outline a language processing architecture consistent with the neuroscience results, where semantic representations may be generated by a syntax‐driven streamandby an “asyntactic” processing stream, jointly or independently. Compositionality is viewed as a constraint on computation in the former stream only. (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 (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)

Previous studies have shown that people often use heuristics in making inferences and that subjective memory experiences, such as recognition or familiarity of objects, can be valid cues for inferences. So far, many researchers have used the binary choice task in which two objects are presented as alternatives (e.g., “Which city has the larger population, city A or city B?”). However, objects can be presented not only as alternatives but also in a question (e.g., “Which country is city X in, (...) country A or country B?”). In such a situation, people can make inferences based on the relationship between the object in the question and each object given as an alternative. In the present study, we call this type of task a “relationships‐comparison task.” We modeled the three inference strategies that people could apply to solve it (familiarity‐matching [FM; a new heuristic we propose in this study], familiarity heuristic [FH], and knowledge‐based inference [KI]) to examine people's inference processes. Through Studies 1, 2, and 3, we found that (a) people tended to rely on heuristics, and that FM (inferences based on similarity in familiarity between objects) well explained participants' inference patterns; (b) FM could work as an ecologically rational strategy for the relationships–comparison task since it could effectively reflect environmental structures, and that the use of FM could be highly replicable and robust; and (c) people could sometimes use a decision strategy like FM, even in their daily lives (consumer behaviors). The nature of the relationships–comparison task and human cognitive processes is discussed. (shrink)

Resource rationality may explain suboptimal patterns of reasoning; but what of “anti-Bayesian” effects where the mind updates in a direction opposite the one it should? We present two phenomena — belief polarization and the size-weight illusion — that are not obviously explained by performance- or resource-based constraints, nor by the authors’ brief discussion of reference repulsion. Can resource rationality accommodate them?

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)

Marr’s seminal distinction between computational, algorithmic, and implementational levels of analysis has inspired research in cognitive science for more than 30 years. According to a widely-used paradigm, the modelling of cognitive processes should mainly operate on the computational level and be targeted at the idealised competence, rather than the actual performance of cognisers in a specific domain. In this paper, we explore how this paradigm can be adopted and revised to understand mathematical problem solving. The computational-level approach applies methods from (...) computational complexity theory and focuses on optimal strategies for completing cognitive tasks. However, human cognitive capacities in mathematical problem solving are essentially characterised by processes that are computationally sub-optimal, because they initially add to the computational complexity of the solutions. Yet, these solutions can be optimal for human cognisers given the acquisition and enactment of mathematical practices. Here we present diagrams and the spatial manipulation of symbols as two examples of problem solving strategies that can be computationally sub-optimal but humanly optimal. These aspects need to be taken into account when analysing competence in mathematical problem solving. Empirically informed considerations on enculturation can help identify, explore, and model the cognitive processes involved in problem solving tasks. The enculturation account of mathematical problem solving strongly suggests that computational-level analyses need to be complemented by considerations on the algorithmic and implementational levels. The emerging research strategy can help develop algorithms that model what we call enculturated cognitive optimality in an empirically plausible and ecologically valid way. (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)

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)

The aim of this paper is an attempt to give an answer to the question what does it mean that a computational system is intelligent. We base on some theses that though debatable are commonly accepted. Intelligence is conceived as the ability of tractable solving of some problems that in general are not solvable by deterministic Turing Machine.

This article takes off from Johan van Benthem’s ruminations on the interface between logic and cognitive science in his position paper “Logic and reasoning: Do the facts matter?”. When trying to answer Van Benthem’s question whether logic can be fruitfully combined with psychological experiments, this article focuses on a specific domain of reasoning, namely higher-order social cognition, including attributions such as “Bob knows that Alice knows that he wrote a novel under pseudonym”. For intelligent interaction, it is important that the (...) participants recursively model the mental states of other agents. Otherwise, an international negotiation may fail, even when it has potential for a win-win solution, and in a time-critical rescue mission, a software agent may depend on a teammate’s action that never materializes. First a survey is presented of past and current research on higher-order social cognition, from the various viewpoints of logic, artificial intelligence, and psychology. Do people actually reason about each other’s knowledge in the way proscribed by epistemic logic? And if not, how can logic and cognitive science productively work together to construct more realistic models of human reasoning about other minds? The paper ends with a delineation of possible avenues for future research, aiming to provide a better understanding of higher-order social reasoning. The methodology is based on a combination of experimental research, logic, computational cognitive models, and agent-based evolutionary models. (shrink)

In light of the recent credibility crisis in psychology, this paper argues for a greater emphasis on theorizing in scientific research. Although reliable experimental evidence, preregistration, methodological rigor, and new computational frameworks for modeling are important, scientific progress also relies on properly functioning theories. However, the current understanding of the role of theorizing in psychology is lacking, which may lead to future crises. Theories should not be viewed as mere speculations or simple inductive generalizations. To address this issue, the author (...) introduces a framework called “cognitive metascience,” which studies the processes and results of evaluating scientific practice. This study should proceed both qualitatively, as in traditional science and technology studies and cognitive science, and quantitatively, by analyzing scientific discourse using language technology. By analyzing theories as cognitive artifacts that support cognitive tasks, this paper aims to shed more light on their nature. This perspective reveals that multiple distinct theories serve entirely different roles, and studying these roles, along with their epistemic vices and virtues, can provide insight into how theorizing should proceed. The author urges a change in research culture to appreciate the variety of distinct theories and to systematically advance scientific progress. . (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 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)

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.

Humans regularly pursue activities characterized by dramatic success or failure outcomes where, critically, the chances of success depend on the time invested working toward it. How should people allocate time between suchmake‐or‐breakchallenges and safe alternatives, where rewards are more predictable (e.g., linear) functions of performance? We present a formal framework for studying time allocation between these two types of activities, and we explore optimal behavior in both one‐shot and dynamic versions of the problem. In the one‐shot version, we illustrate striking (...) discontinuities in the optimal time allocation policy as we gradually change the parameters of the decision‐making problem. In the dynamic version, we formulate the optimal strategy—defined by agiving‐upthreshold—which adaptively dictates when people should stop pursuing the make‐or‐break goal. We then show that this strategy is computationally inaccessible for humans, and we explore boundedly rational alternatives. We compare the performance of the optimal model against (a) a myopic giving‐up threshold that is easier to compute, and even simpler heuristic strategies that either (b) only decide whether or not to start pursuing the goal and never give up or (c) consider giving up at a fixed number of control points. Comparing strategies across environments, we investigate the cost and behavioral implications of sidestepping the computational burden of full rationality. (shrink)

This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink)

This paper presents a computational model of the way humans inductively identify and aggregate concepts from the low-level stimuli they are exposed to. Based on the idea that humans tend to select the simplest structures, it implements a dynamic hierarchical chunking mechanism in which the decision whether to create a new chunk is based on an information-theoretic criterion, the Minimum Description Length (MDL) principle. We present theoretical justifications for this approach together with results of an experiment in which participants, exposed (...) to meaningless symbols, have been implicitly encouraged to create high-level concepts by grouping them. Results show that the designed model, called hereafter MDLChunker, makes precise quantitative predictions both on the kind of chunks created by the participants and also on the moment at which these creations occur. They suggest that the simplicity principle used to design MDLChunker is particularly efficient to model chunking mechanisms. The main interest of this model over existing ones is that it does not require any adjustable parameter. (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)

We study the computational complexity of polyadic quantifiers in natural language. This type of quantification is widely used in formal semantics to model the meaning of multi-quantifier sentences. First, we show that the standard constructions that turn simple determiners into complex quantifiers, namely Boolean operations, iteration, cumulation, and resumption, are tractable. Then, we provide an insight into branching operation yielding intractable natural language multi-quantifier expressions. Next, we focus on a linguistic case study. We use computational complexity results to investigate semantic (...) distinctions between quantified reciprocal sentences. We show a computational dichotomy<br>between different readings of reciprocity. Finally, we go more into philosophical speculation on meaning, ambiguity and computational complexity. In particular, we investigate a possibility to<br>revise the Strong Meaning Hypothesis with complexity aspects to better account for meaning shifts in the domain of multi-quantifier sentences. The paper not only contributes to the field of the formal<br>semantics but also illustrates how the tools of computational complexity theory might be successfully used in linguistics and philosophy with an eye towards cognitive science. (shrink)

A central goal in Cognitive Science is understanding the mechanisms that underlie cognition. Here, we contend that Cognitive Science, despite intense multidisciplinary efforts, has furnished surprisingly few mechanistic insights. We attribute this slow mechanistic progress to the fact that cognitive scientists insist on performing underdetermined exercises, deriving overparametrized mechanistic theories of complex behaviors and seeking validation of these theories to the elusive notions of optimality and biological plausibility. We propose that mechanistic progress in Cognitive Science will accelerate once cognitive scientists (...) start focusing on simpler explananda that will enable them to chart an atlas of elementary cognitive operations. Looking forward, the next challenge for Cognitive Science will be to understand how these elementary cognitive processes are pieced together to explain complex behavior. (shrink)

Many compelling examples have recently been provided in which people can achieve impressive epistemic success, e.g. draw highly accurate inferences, by using simple heuristics and very little information. This is possible by taking advantage of the features of the environment. The examples suggest an easy and appealing naturalization of rationality: on the one hand, people clearly can apply simple heuristics, and on the other hand, they intuitively ought do so when this brings them high accuracy at little cost.. The ‘ought-can’ (...) principle is satisfied, and rationality is meaningfully normative. We show, however, that this naturalization program is endangered by a computational wrinkle in the adaptation process taken to be responsible for this heuristics-based (‘ecological’) rationality: for the adaptation process to guarantee even minimal rationality, it requires astronomical computational resources, making the problem intractable. We consider various plausible auxiliary assumptions in attempt to remove this obstacle, and show that they do not succeed; intractability is a robust property of adaptation. We discuss the implications of our findings for the project of naturalizing rationality. (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.

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)

There continues to be significant confusion about the goals, scope, and nature of modelling practice in neuroeconomics. This article aims to dispel some such confusion by using one of the most recent critiques of neuroeconomic modelling as a foil. The article argues for two claims. First, currently, for at least some economic model of choice behaviour, the benefits derivable from neurally informing an economic model do not involve special tractability costs. Second, modelling in neuroeconomics is best understood within Marr’s three-level (...) of analysis framework and in light of a co-evolutionary research ideology. The first claim is established by elucidating the relationship between the tractability of a model, its descriptive accuracy, and its number of variables. The second claim relies on an explanation of what it can take to neurally inform an economic model of choice behaviour. 1 Introduction2 Neurally Informed Models of Choice: A Case Study2.1 A case study on risk-sensitive choice2.1.1 Target and modelling framework2.1.2 Research question and hypotheses2.1.3 Competitive models of risk-sensitive behaviour2.1.4 Model-based fMRI: from economics to brains and back2.2 Neurally informed modelling3 Tractability: When Does Size Matter?4 Neural Integration and the Co-evolutionary Research Ideology5 Conclusion. (shrink)

We report two experiments which tested whether cognitive capacities are limited to those functions that are computationally tractable (PTIME-Cognition Hypothesis). In particular, we investigated the semantic processing of reciprocal sentences with generalized quantifiers, i.e., sentences of the form Q dots are directly connected to each other, where Q stands for a generalized quantifier, e.g. all or most. Sentences of this type are notoriously ambiguous and it has been claimed in the semantic literature that the logically strongest reading is preferred (Strongest (...) Meaning Hypothesis). Depending on the quantifier, the verification of their strongest interpretations is computationally intractable whereas the verification of the weaker readings is tractable. We conducted a picture completion experiment and a picture verification experiment to investigate whether comprehenders shift from an intractable reading to a tractable reading which should be dispreferred according to the Strongest Meaning Hypothesis. The results from the picture completion experiment suggest that intractable readings occur in language comprehension. Their verification, however, rapidly exceeds cognitive capacities in case the verification problem cannot be solved using simple heuristics. In particular, we argue that during verification, guessing strategies are used to reduce computational complexity. (shrink)

Are all three of Marr's levels needed? Should they be kept distinct? We argue for the distinct contributions and methodologies of each level of analysis. It is important to maintain them because they provide three different perspectives required to understand mechanisms, especially information-processing mechanisms. The computational perspective provides an understanding of how a mechanism functions in broader environments that determines the computations it needs to perform. The representation and algorithmic perspective offers an understanding of how information about the environment is (...) encoded within the mechanism and what are the patterns of organization that enable the parts of the mechanism to produce the phenomenon. The implementation perspective yields an understanding of the neural details of the mechanism and how they constrain function and algorithms. Once we adequately characterize the distinct role of each level of analysis, it is fairly straightforward to see how they relate. (shrink)

This paper starts from the observation that the standard arguments for compositionality are really arguments for the computability of semantics. Since computability does not entail compositionality, the question of what justifies compositionality recurs. The paper then elaborates on the idea of recursive semantics as corresponding to computable semantics. It is then shown by means of time complexity theory and with the use of term rewriting as systems of semantic computation, that syntactically unrestricted, noncompositional recursive semantics leads to computational explosion (factorial (...) complexity). Hence, with combinatorially unrestricted syntax, semantics with tractable time complexity is compositional. (shrink)

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)