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.

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)

Ethical disputes arise over differences in the content of the ethical beliefs people hold on either side of an issue. One person may believe that it is wrong to have an abortion for financial reasons, whereas another may believe it to be permissible. But, the magnitude and difficulty of such disputes may also depend on other properties of the ethical beliefs in question—in particular, how objective they are perceived to be. As a psychological property of moral belief, objectivity is relatively (...) unexplored, and we argue that it merits more attention. We review recent psychological evidence which demonstrates that individuals differ in the extent to which they perceive ethical beliefs to be objective, that some ethical beliefs are perceived to be more objective than others, and that both these sources of variance are somewhat systematic. This evidence also shows that differences in perceptions of objectivity underpin quite different psychological reactions to ethical disagreement. Apart from reviewing this evidence, our aim in this paper is to draw attention to unanswered psychological questions about moral objectivity, and to discuss the relevance of moral objectivity to two issues of public policy. (shrink)

In this paper, I will discuss a well-known oscillation in Frege’s conception of sense. My point is only partially concerned with his two different criteria of sense identity, and touches upon a more specific point: what happens if we apply Frege’s intuitive criterion for the difference of thoughts to logically equivalent sentences? I will try to make a schematic argument here that will preempt any endeavor to make Frege more coherent than he really is. In sections A and B, I (...) will present two alternative Fregean ways to treat the sense of logically equivalent sentences. Frege really oscillated between two alternative conceptions of sense, and his inability to detect the contrast between the two alternative conceptions is partly due to his strong conception of rationality. To apply the criterion of difference of thoughts to logical matters, we may also use a weak notion of rationality, or at least a notion of rationality of human agents, with limited computational resources. The distinctions towards which Frege was striving are better understood nowadays from the point of view of the treatment of limited rationality, which imposes itself even in logical matters. (shrink)

This paper explores the ways in which resource limitations influence the nature of perceptual and cognitive processes. A framework is developed that allows early visual processing to be analyzed in terms of these limitations. In this approach, there is no one ``best'' system for any visual process. Rather, a spectrum of systems exists, differing in the particular trade-offs made between performance and resource requirements.

We discuss external and internal graphical and linguistic representational systems. We argue that a cognitive theory of peoples' reasoning performance must account for (a) the logical equivalence of inferences expressed in graphical and linguistic form; and (b) the implementational differences that affect facility of inference. Our theory proposes that graphical representations limit abstraction and thereby aid processibility. We discuss the ideas of specificity and abstraction, and their cognitive relevance. Empirical support comes from tasks (i) involving and (ii) not involving the (...) manipulation of external graphics. For (i), we take Euler's Circles, provide a novel computational reconstruction, show how it captures abstractions, and contrast it with earlier construals, and with Mental Models' representations. We demonstrate equivalence of the graphical Euler system, and the non-graphical Mental Models system. For (ii), we discuss text comprehension, and the mental performance of syllogisms. By positing an internal system with the same specificity as Euler's Circles we cover the Mental Models data, and generate new empirical predictions. Finally, we consider how the architecture of working memory explains why such specific representations are relatively easy to store. (shrink)

Within AI and the cognitively related disciplines, there exist a multiplicity of uses of belief. On the face of it, these differing uses reflect differing views about the nature of an objective phenomenon called belief. In this paper I distinguish six distinct ways in which belief is used in AI. I shall argue that not all these uses reflect a difference of opinion about an objective feature of reality. Rather, in some cases, the differing uses reflect differing concerns with special (...) AI applications. In other cases, however, genuine differences exist about the nature of what we pre-theoretically call belief. To an extent the multiplicity of opinions about, and uses of belief, echoes the discrepant motivations of AI researchers. The relevance of this discussion for cognitive scientists and philosophers arises from the fact that (a) many regard theoretical research within AI as a branch of cognitive science, and (b) even if theoretical AI is not cognitive science, trends within AI influence theories developed within cognitive science. It should be beneficial, therefore, to unravel the distinct uses and motivations surrounding belief, in order to discover which usages merely reflect differing pragmatic concerns, and which usages genuinely reflect divergent views about reality. (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)

This paper outlines a method to assess the effectiveness of diagrams, from semiotic foundations. In doing so, we explore the Peircian notion of signification, as applied to diagrammatic representations. We review a history of diagrams, with particular emphasis on schematics used for representing systems, and uncover the neglect of semiotic analysis of diagrammatic representations. Through application of category theory to the Peircian triadic model, we propose a set of quantitative quality measures for diagrams, and a framework for their assessment, based (...) on the properties of their encoding, pragmatic and perceptual morphisms. These measures include diagram complexity, utility, aesthetics and expert assessment of semiotic content, together with qualitative feedback. We consider the diagrams as an aid to cognitive processes, rather than a purely communication media. This utility-focused perspective on diagram quality dimensions allows for fresh insights into the creation of effective diagrams. (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)

The recognition that human minds/brains are finite systems with limited resources for computation has led some researchers to advance the Tractable 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 the P‐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 the FPT‐Cognition thesis as 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)

This paper is a commentary on the target article by Lokendra Shastri & Venkat Ajjanagadde [S&A]: “From simple associations to systematic reasoning: A connectionist representation of rules, variables and dynamic bindings using temporal synchrony” in same issue of the journal, pp.417–451. -/- It puts S&A's temporal-synchrony binding method in a broader context, comments on notions of pointing and other ways of associating information - in both computers and connectionist systems - and mentions types of reasoning that are a challenge to (...) S&A's system (amongst many other connectionist systems, recognizing that S&A's is much more capable as regards reasoning than most other contemporary systems). (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)

We discuss external and internal graphical and linguistic representational systems. We argue that a cognitive theory of peoples' reasoning performance must account for (a) the logical equivalence of inferences expressed in graphical and linguistic form, and (b) the implementational differences that affect facility of inference. Our theory proposes that graphical representation limit abstraction and thereby aid “processibility”. We discuss the ideas of specificity and abstraction, and their cognitive relevance. Empirical support both comes from tasks which involve the manipulation of external (...) graphics and tasks that do not. For the former, we take Euler's (1772) circles, provide a novel computational reconstruction, show how it captures abstractions, and contrast it with earlier construals and with Johnson‐Laird's (1983) mental models representations. We demonstrate equivalence of the graphical Euler system, and the nongraphical mental models system. For tasks not involving manipulation of external graphics, we discuss text comprehension, and the mental performance of syllogisms. By positing an internal system with the same specificity as Euler's circles, we cover the mental models data, and generate new empirical predictions. Finally, we consider how the architecture of working memory explains why such specific representations are relatively easy to store. (shrink)