Online research in philosophy

We study the computational complexity of reciprocal sentences with quantified antecedents. We observe a computational dichotomy between different interpretations of reciprocity, and shed some light on the status of the so-called Strong Meaning Hypothesis.

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)

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)

The problem of computational complexity of semantics for some natural language constructions – considered in [M. Mostowski, D. Wojtyniak 2004] – motivates an interest in complexity of Ramsey quantifiers in finite models. In general a sentence with a Ramsey quantifier R of the following form Rx, yH(x, y) is interpreted as ∃A(A is big relatively to the universe ∧A2 ⊆ H). In the paper cited the problem of the complexity of the Hintikka sentence is reduced to (...) the problem of computational complexity of the Ramsey quantifier for which the phrase “A is big relatively to the universe” is interpreted as containing at least one representative of each equivalence class, for some given equvalence relation. In this work we consider quantifiers Rf, for which “A is big relatively to the universe” means “card(A) > f (n), where n is the size of the universe”. Following [Blass, Gurevich 1986] we call R mighty if Rx, yH(x, y) defines N P – complete class of finite models. Similarly we say that Rf is N P –hard if the corresponding class is N P –hard. We prove the following theorems. (shrink)

This book asks not only how the study of white-collar crime can enrich our understanding of crime and justice more generally, but also how criminological ...

We study the computational complexity of the model checking problem for quantifier-free dependence logic ${(\mathcal{D})}$ formulas. We characterize three thresholds in the complexity: logarithmic space (LOGSPACE), non-deterministic logarithmic space (NL) and non-deterministic polynomial time (NP).

The main claim of this paper is that notions of implementation based on an isomorphic correspondence between physical and computational states are not tenable. Rather, ``implementation'' has to be based on the notion of ``bisimulation'' in order to be able to block unwanted implementation results and incorporate intuitions from computational practice. A formal definition of implementation is suggested, which satisfies theoretical and practical requirements and may also be used to make the functionalist notion of ``physical realization'' precise. The (...) upshot of this new definition of implementation is that implementation cannot distinguish isomorphic bisimilar from non-isomporphic bisimilar systems anymore, thus driving a wedge between the notions of causal and computational complexity. While computationalism does not seem to be affected by this result, the consequences for functionalism are not clear and need further investigations. (shrink)

I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.

Some problems rarely discussed in traditional philosophy of science are mentioned: The empirical sciences using mathematico-quantitative theoretical models are frequently confronted with several types of computational problems posing primarily methodological limitations on explanatory and prognostic matters. Such limitations may arise from the appearances of deterministic chaos and (too) high computational complexity in general. In many cases, however, scientists circumvent such limitations by utilizing reductional approximations or complexity reductions for intractable problem formulations, thus constructing new models (...) which are computationally tractable. Such activities are compared with reduction types (more) established in philosophy of science. (shrink)

The main powerful method for establishing termination of term rewriting systems was discovered by Nachum Dershowitz through the introduction of certain natural well founded orderings (lexicographic path orderings). This leads to natural decision problems which may be of the highest computational complexity of any decidable problems appearing in a natural established computer science context.

I argue that considerations about computational complexity show that all finite agents need characteristics like those that have been called epistemic virtues. The necessity of these virtues follows in part from the nonexistence of shortcuts, or efficient ways of finding shortcuts, to cognitively expensive routines. It follows that agents must possess the capacities – metavirtues –of developing in advance the cognitive virtues they will need when time and memory are at a premium.

The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (...) (= finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic. (shrink)

Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).

The theme of this book is formed by a pair of concepts: the concept of formal language as carrier of the precise expression of meaning, facts and problems, and the concept of algorithm or calculus, i.e. a formally operating procedure for the solution of precisely described questions and problems. The book is a unified introduction to the modern theory of these concepts, to the way in which they developed first in mathematical logic and computability theory and later in automata theory, (...) and to the theory of formal languages and complexity theory. Apart from considering the fundamental themes and classical aspects of these areas, the subject matter has been selected to give priority throughout to the new aspects of traditional questions, results and methods which have developed from the needs or knowledge of computer science and particularly of complexity theory. It is both a textbook for introductory courses in the above-mentioned disciplines as well as a monograph in which further results of new research are systematically presented and where an attempt is made to make explicit the connections and analogies between a variety of concepts and constructions. (shrink)

Many of the formalisms used in Attribute Value grammar are notational variants of languages of propositional modal logic, and testing whether two Attribute Value Structures unify amounts to testing for modal satisfiability. In this paper we put this observation to work. We study the complexity of the satisfiability problem for nine modal languages which mirror different aspects of AVS description formalisms, including the ability to express re-entrancy, the ability to express generalisations, and the ability to express recursive constraints. Two (...) main techniques are used: either Kripke models with desirable properties are constructed, or modalities are used to simulate fragments of Propositional Dynamic Logic. Further possibilities for the application of modal logic in computational linguistics are noted. (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)

Various algorithms have been proposed for learning (partial) genetic regulatory networks through systematic measurements of differential expression in wild type versus strains in which expression of specific genes has been suppressed or enhanced, as well as for determining the most informative next experiment in a sequence. While the behavior of these algorithms has been investigated for toy examples, the full computational complexity of the problem has not received sufficient attention. We show that finding the true regulatory network requires (...) (in the worst-case) exponentially many experiments (in the number of genes). Perhaps more importantly, we provide an algorithm for determining the set of regulatory networks consistent with the observed data. We then show that this algorithm is infeasible for realistic data (specifically, nine genes and ten experiments). This infeasibility is not due to an algorithmic flaw, but rather to the fact that there are far too many networks consistent with the data (10 18 in the provided example). We conclude that gene perturbation experiments are useful in confirming regulatory network models discovered by other techniques, but not a feasible search strategy. (shrink)

Modal dependence logic was introduced recently by Väänänen. It enhances the basic modal language by an operator = (). For propositional variables p 1, . . . , p n , = (p 1, . . . , p n-1, p n ) intuitively states that the value of p n is determined by those of p 1, . . . , p n-1. Sevenster (J. Logic and Computation, 2009) showed that satisfiability for modal dependence logic is complete for nondeterministic (...) exponential time.In this paper we consider fragments of modal dependence logic obtained by restricting the set of allowed propositional connectives. We show that satisfiability for poor man’s dependence logic, the language consisting of formulas built from literals and dependence atoms using ${\wedge, \square, \lozenge}$ (i. e., disallowing disjunction), remains NEXPTIME-complete. If we only allow monotone formulas (without negation, but with disjunction), the complexity drops to PSPACE-completeness.We also extend Väänänen’s language by allowing classical disjunction besides dependence disjunction and show that the satisfiability problem remains NEXPTIME-complete. If we then disallow both negation and dependence disjunction, satisfiability is complete for the second level of the polynomial hierarchy. Additionally we consider the restriction of modal dependence logic where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the satisfiability problem for this bounded arity dependence logic is PSPACE-complete and that the complexity drops to the third level of the polynomial hierarchy if we then disallow disjunction.In this way we completely classify the computational complexity of the satisfiability problem for all restrictions of propositional and dependence operators considered by Väänänen and Sevenster. (shrink)

Complexity and Postmodernism explores the notion of complexity in the light of contemporary perspectives from philosophy and science. The book integrates insights from complexity and computational theory with the philosophical position of thinkers including Derrida and Lyotard. Paul Cilliers takes a critical stance towards the use of the analytical method as a tool to cope with complexity, and he rejects Searle's superficial contribution to the debate.

Given any simply consistent formal theory F of the state complexity L(S) of finite binary sequences S as computed by 3-tape-symbol Turing machines, there exists a natural number L(F ) such that L(S) > n is provable in F only if n < L(F ). On the other hand, almost all finite binary sequences S satisfy L(S) > L(F ). The proof resembles Berry’s..

We compared the processing of natural language quantifiers in a group of patients with schizophrenia and a healthy control group. In both groups, the difficulty of the quantifiers was consistent with computational predictions, and patients with schizophrenia took more time to solve the problems. However, they were significantly less accurate only with proportional quantifiers, like more than half. This can be explained by noting that, according to the complexity perspective, only proportional quantifiers require working memory engagement.

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)

This paper examines the rising competition between computational and dynamic conceptualizations of complexity in economics. While computable economics views the complexity as something rigorously defined based on concepts from probability, information, and computability criteria, dynamic complexity is based on whether a system endogenously and deterministically generates erratically dynamic behavior of certain kinds. On such behavior is the phenomenon of emergence, the appearance of new forms or structures at higher levels of a system from processes occurring at (...) lower levels. While the two concepts can overlap, they represent substantially different perspectives. A competition of sorts between them may become more important as new, computerized market systems emerge and evolve to higher levels of complexity of both kinds. (shrink)

Human intentional communication is marked by its flexibility and context sensitivity. Hypothesized brain mechanisms can provide convincing and complete explanations of the human capacity for intentional communication only insofar as they can match the computational power required for displaying that capacity. It is thus of importance for cognitive neuroscience to know how computationally complex intentional communication actually is. Though the subject of considerable debate, the computational complexity of communication remains so far unknown. In this paper we defend (...) the position that the computational complexity of communication is not a constant, as some views of communication seem to hold, but rather a function of situational factors. We present a methodology for studying and characterizing the computational complexity of communication under different situational constraints. We illustrate our methodology for a model of the problems solved by receivers and senders during a communicative exchange. This approach opens the way to a principled identification of putative model parameters that control cognitive processes supporting intentional communication. (shrink)

Even beginners and young graduate students will have something to learn from this book." (Andre Hautot, Physicalia, Vol. 57 (3), 2005)"All-in-all, this highly ...

This introduction to certain mathematical topics central to theoretical computer science treats computability and recursive functions, formal languages and automata, computational complexity, and cruptography. The presentation is essentially self-contained with detailed proofs of all statements provided. Although it begins with the basics, it proceeds to some of the most important recent developments in theoretical computer science.

Planning with incomplete knowledge becomes a very active research area since late 1990s. Many logical formalisms introduce sensing actions and conditional plans to address the problem. The action language $\mathcal{A}_{K}$ invented by Son and Baral is a well-known framework for this purpose. In this paper, we propose so-called cautious and weakly cautious semantics for $\mathcal{A}_{K}$ , in order to allow an agent to generate and execute reliable plans in safety-critical environments. Intuitively speaking, cautious and weakly cautious semantics enable the agent (...) to know exactly what happens after the execution of an action. Computational complexity analysis shows that cautious semantics reduces the reasoning complexity of $\mathcal{A}_{K}$ , it is also worth to point out that many useful domains could still be expressed with this setting. Another important contribution of our work is the development of Hoare style proof systems. These proof systems are served as inference mechanisms for the verification of conditional plans, and proved to be sound and complete. In addition, they could also be used for plan generation, in the sense that constructing a derivation is indeed a procedure to finding a plan. We point out that the proof systems posses a nice property for off-line planning, that is, the agent could generate and store short proofs in her spare time, and perform quick plan query by easily constructing a long proof from the stored shorter ones (under the assumption that sufficient proofs are stored). (shrink)

This volume provides an accessible theoretical introduction to the topic of complexity theory while considering its broader implications for educational change.

This book presents an up-to-date, unified treatment of research in bounded arithmetic and complexity of propositional logic, with emphasis on independence proofs and lower bound proofs. The author discusses the deep connections between logic and complexity theory and lists a number of intriguing open problems. An introduction to the basics of logic and complexity theory is followed by discussion of important results in propositional proof systems and systems of bounded arithmetic. More advanced topics are then treated, including (...) polynomial simulations and conservativity results, various witnessing theorems, the translation of bounded formulas (and their proofs) into propositional ones, the method of random partial restrictions and its applications, direct independence proofs, complete systems of partial relations, lower bounds to the size of constant-depth propositional proofs, the method of Boolean valuations, the issue of hard tautologies and optimal proof systems, combinatorics and complexity theory within bounded arithmetic, and relations to complexity issues of predicate calculus. Students and researchers in mathematical logic and complexity theory will find this comprehensive treatment an excellent guide to this expanding interdisciplinary area. (shrink)

(2) Vol., Classification of Propositional Provability Logics LD Beklemishev Introduction Overview. The idea of an axiomatic approach to the study of ...

An important distinction between phonology and syntax has been overlooked. All phonological patterns belong to the regular region of the Chomsky Hierarchy, but not all syntactic patterns do. We argue that the hypothesis that humans employ distinct learning mechanisms for phonology and syntax currently offers the best explanation for this difference.

Our primary interest is in determining how many gene perturbation experiments are required to determine the Various algorithms have been proposed for learning..

We prove that PTIME generalized quantifiers are closed under Boolean operations, iteration, cumulation and resumption. -/- .

The LNCS series reports state-of-the-art results in computer science research, development, and education, at a high level and in both printed and electronic form.

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.

This paper surveys applications of logical methods in the cognitive sciences. Special attention is paid to non-monotonic logics and complexity theory. We argue that these particular tools have been useful in clarifying the debate between symbolic and connectionist models of cognition.

Three recent, influential critiques (Stich 1978; Fodor 1981c; Block 1980) have argued that various tasks on the agenda for computational psychology put conflicting pressures on its theoretical constructs. Unless something is done, the inevitable result will be confusion or outright incoherence. Stich, Fodor, and Block present different versions of this worry and each proposes a different remedy. Stich wants the central notion of belief to be jettisoned if it cannot be shown to be sound. Fodor tries to reduce confusion (...) in computational psychology by dismissing some putative tasks as impossible. Block argues that the widespread faith in functionalism is just not warranted. I argue that all these critiques are misguided because they depend on holding cognitive psychology to taxonomic standards that other sciences routinely rise above. (shrink)

We consider the notion of everyday language. We claim that everyday language is semantically bounded by the properties expressible in the existential fragment of second–order logic. Two arguments for this thesis are formulated. Firstly, we show that so–called Barwise's test of negation normality works properly only when assuming our main thesis. Secondly, we discuss the argument from practical computability for finite universes. Everyday language sentences are directly or indirectly verifiable. We show that in both cases they are bounded by second–order (...) existential properties. Moreover, there are known examples of everyday language sentences which are the most difficult in this class (NPTIME–complete). (shrink)

We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier $\sQ_1$ is definable in terms of another quantifier $\sQ_2$, the base logic being monadic second-order logic, reduces to the question if a quantifier $\sQ^{\star}_1$ is definable in $\FO(\sQ^{\star}_2,<,+,\times)$ for certain first-order quantifiers $\sQ^{\star}_1$ and $\sQ^{\star}_2$. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. In particular, we show that the monadic second-order majority quantifier $\most^1$ is not definable (...) in second-order logic. (shrink)

In Minimal Rationality, Christopher Cherniak boldly challenges the myth of Man the the Rational Animal and the central role that the "perfectly rational...

We extend the language of the classical syllogisms with the sentence-forms “At most 1 p is a q” and “More than 1 p is a q”. We show that the resulting logic does not admit a finite set of syllogism-like rules whose associated derivation relation is sound and complete, even when reductio ad absurdum is allowed.

The following paper presents a characterization of three distinctions fundamental to computationalism, viz., the distinction between analog and digital machines, representation and nonrepresentation-using systems, and direct and indirect perceptual processes. Each distinction is shown to rest on nothing more than the methodological principles which justify the explanatory framework of the special sciences.

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

In their book The Road to Maxwell's Demon Hemmo & Shenker re-describe the foundations of statistical mechanics from a purely empiricist perspective. The result is refreshing, as well as intriguing, and it goes against much of the literature on the demon. Their conclusion, however, that Maxwell's demon is consistent with statistical mechanics, still leaves open the question of why such a demon hasn't yet been observed on a macroscopic scale. This essay offers a sketch of what a possible answer could (...) look like. (shrink)

As brightly shown by Mainzer [24], the science of complexity has many distinct origins in many disciplines. Those various origins has led to “an interdisciplinary methodology to explain the emergence of certain macroscopic phenomena via the nonlinear interactions of microscopic elements” (ibid.). This paper suggests that the parallel and strong expansion of modeling and simulation - especially after the Second World War and the subsequent development of computers - is a rationale which also can be counted as an explanation (...) of this emergence. With the benefit of hindsight, one can find three periods in the methodologies of modeling in the empirical sciences: 1st the simple modeling of the simple, 2nd the simple modeling of the complex, 3rd the complex modeling and simulation of the complex. Our main thesis is that the current spreading (since the 90’s) of complex computer simulations of systems of models (where a simulation is no more a step by step calculus of a unique logico-mathematical model) is another promising dimension of the science of complexity. Following this claim, we propose to distinguish three different types of computer simulations in the context of complex systems’ modeling. Finally, we show that these types of simulations lead to three different types of weak emergence, too. (shrink)

As the number of computational models of eye-movement control in reading increases, so too will their coverage and complexity. This will make their comparison and testing increasingly challenging. We argue here that there is a need to develop a methodology for constructing and evaluating such models, and outline aspects of a possible methodology.

This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and infinitary (...) logics to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful way to analyze the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the application of logic to computer science. (shrink)

By a fragment of a natural language we mean a subset of thatlanguage equipped with semantics which translate its sentences intosome formal system such as first-order logic. The familiar conceptsof satisfiability and entailment can be defined for anysuch fragment in a natural way. The question therefore arises, for anygiven fragment of a natural language, as to the computational complexityof determining satisfiability and entailment within that fragment. Wepresent a series of fragments of English for which the satisfiabilityproblem is polynomial, NP-complete, (...) EXPTIME-complete,NEXPTIME-complete and undecidable. Thus, this paper represents a casestudy in how to approach the problem of determining the logicalcomplexity of various natural language constructions. In addition, wedraw some general conclusions about the relationship between naturallanguage and formal logic. (shrink)

An analogy between the evolution of organisms and some complex computational problems (cryptosystem cracking, determination of the shortest path in a graph) is considered. It is shown that in the absence of a priori information about possible species of organisms such a problem is complex (is rated in the class NP) and cannot be solved in a polynomial number of steps. This conclusion suggests the need for re-examination of evolution mechanisms. Ideas of a deterministic approach to the evolution are (...) discussed. (shrink)

Cellular automata (henceforth: CA) are discrete, abstract computational systems that have proved useful both as general models of complexity and as more specific representations of non-linear dynamics in a variety of scientific fields. Firstly, CA are (typically) spatially and temporally discrete: they are composed of a finite or denumerable set of homogeneous, simple units, the atoms or cells. At each time unit, the cells instantiate one of a finite set of states. They evolve in parallel at discrete time (...) steps, following state update functions or dynamical transition rules: the update of a cell state obtains by taking into account the states of cells in its local neighborhood (there are, therefore, no actions at a distance). Secondly, CA are abstract, as they can be specified in purely mathematical terms and implemented in physical structures. Thirdly, CA are computational systems: they can compute functions and solve algorithmic problems. Despite functioning in a different way from traditional, Turing machine-like devices, CA with suitable rules can emulate a universal Turing machine, and therefore compute, given Turing's Thesis, anything computable.... (shrink)

In this paper, we focus attention on the role of computer system complexity in ascribing responsibility. We begin by introducing the notion of technological moral action (TMA). TMA is carried out by the combination of a computer system user, a system designer (developers, programmers, and testers), and a computer system (hardware and software). We discuss three sometimes overlapping types of responsibility: causal responsibility, moral responsibility, and role responsibility. Our analysis is informed by the well-known accounts provided by Hart and (...) Hart and Honoré. While these accounts are helpful, they have misled philosophers and others by presupposing that responsibility can be ascribed in all cases of action simply by paying attention to the free and intended actions of human beings. Such accounts neglect the part played by technology in ascriptions of responsibility in cases of moral action with technology. For both moral and role responsibility, we argue that ascriptions of both causal and role responsibility depend on seeing action as complex in the sense described by TMA. We conclude by showing how our analysis enriches moral discourse about responsibility for TMA. (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 this paper we study the Kolmogorov complexity for non-effective computations, that is, either halting or non-halting computations on Turing machines. This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity. In particular, if the machine is allowed to overwrite its output, this complexity coincides with the classical Kolmogorov complexity for halting (...) computations relative to the first jump of the halting problem. However, on machines that cannot erase their output –called monotone machines–, we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations. We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations. (shrink)

We present some new decision and comparison problems of unusually high computational complexity. Most of the problems are strictly combinatorial in nature; others involve basic logical notions. Their complexities range from iterated exponential time completeness to (0 time completeness to ((((,0) time completeness to ((((,,0) time completeness. These three ordinals are well known ordinals from proof theory, and their associated com- plexity classes represent new levels of computational complexity for natural decision problems. Proofs will appear in (...) an extended version of this manuscript to be published elsewhere. (shrink)

Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

Sandu and Pietarinen [Partiality and Games: Propositional Logic. Logic J. IGPL 9 (2001) 101] study independence friendly propositional logics. That is, traditional propositional logic extended by means of syntax that allow connectives to be independent of each other, although the one may be subordinate to the other. Sandu and Pietarinen observe that the IF propositional logics have exotic properties, like functional completeness for three-valued functions. In this paper we focus on one of their IF propositional logics and study its properties, (...) by means of notions from computational complexity. This approach enables us to compare propositional logic before and after the IF make-over. We observe that all but one of the best-known decision problems experience a complexity jump, provided that the complexity classes at hand are not equal. Our results concern every discipline that incorporates some notion of independence such as computer science, natural language semantics, and game theory. A corollary of one of our theorems illustrates this claim with respect to the latter discipline. (shrink)

This paper examines and classifies the computational complexity of model checking and satisfiability for hybrid logics over frames with equivalence relations. The considered languages contain all possible combinations of the downarrow binder, the existential binder, the satisfaction operator, and the global modality, ranging from the minimal hybrid language to very expressive languages. For model checking, we separate polynomial-time solvable from PSPACE-complete cases, and for satisfiability, we exhibit cases complete for NP, PS pace , NE xp T ime , (...) and even N2E xp T ime . Our analysis includes the versions of all these languages without atomic propositions, and also complete frames. (shrink)

The relations between simplicity and economy, and between simplicity and complexity, are briefly discussed, and it is suggested that an appearance of simplicity may arise out of the matching of two complexities, e.g. in the perception of a simple color. Following out this idea, it is shown that scientific activity may be regarded as a matching of theoretical complexity against the complexity of nature, which leads to an expectation of an optimum theoretical complexity for successful scientific (...) work. Some senses of "success" in this context are discussed, and the role of computing machines in helping to achieve it assessed. (shrink)

The tension between expressive power and computational tractability poses an acute problem for theories of underspecified semantic representation. In previous work we have presented an account of underspecified scope representations within Property Theory with Curry Typing (PTCT), an intensional first-order theory for natural language semantics. Here we show how filters applied to the underspecified-scope terms of PTCT permit both expressive completeness and the reduction of computational complexity in a significant class of non-worst case scenarios.

The primary goal of this essay is to demonstrate how considerations from computational complexity theory can inform grammatical theorizing. To this end, generalized phrase structure grammar (GPSG) linguistic theory is revised so that its power more closely matches the limited ability of an ideal speaker-hearer: GPSG Recognition is EXP-POLY time hard, while Revised GPSG Recognition is NP-complete. A second goal is to provide a theoretical framework within which to better understand the wide range of existing GPSG models, embodied (...) in formal definitions as well as in implemented computer programs. (shrink)

The aim of this paper is to address the question: Can an artificial neural network (ANN) model be used as a possible characterization of the power of the human mind? We will discuss what might be the relationship between such a model and its natural counterpart. A possible characterization of the different power capabilities of the mind is suggested in terms of the information contained (in its computational complexity) or achievable by it. Such characterization takes advantage of recent (...) results based on natural neural networks (NNN) and the computational power of arbitrary artificial neural networks (ANN). The possible acceptance of neural networks as the model of the human mind's operation makes the aforementioned quite relevant. (shrink)

We compare time needed for understanding different types of quantifiers. We show that the computational distinction between quantifiers recognized by finite-automata and pushdown automata is psychologically relevant. Our research improves upon hypothesis and explanatory power of recent neuroimaging studies as well as provides evidence for the claim that human linguistic abilities are constrained by computational complexity.

What enables individually simple insects like ants to act with such precision and purpose as a group? How do trillions of individual neurons produce something as extraordinarily complex as consciousness? What is it that guides self-organizing structures like the immune system, the World Wide Web, the global economy, and the human genome? These are just a few of the fascinating and elusive questions that the science of complexity seeks to answer. In this remarkably accessible and companionable book, leading complex (...) systems scientist Melanie Mitchell provides an intimate, detailed tour of the sciences of complexity, a broad set of efforts that seek to explain how large-scale complex, organized, and adaptive behavior can emerge from simple interactions among myriad individuals. Comprehending such systems requires a wholly new approach, one that goes beyond traditional scientific reductionism and that re-maps long-standing disciplinary boundaries. Based on her work at the Santa Fe Institute and drawing on its interdisciplinary strategies, Mitchell brings clarity to the workings of complexity across a broad range of biological, technological, and social phenomena, seeking out the general principles or laws that apply to all of them. She explores as well the relationship between complexity and evolution, artificial intelligence, computation, genetics, information processing, and many other fields. Richly illustrated and vividly written, Complexity: A Guided Tour offers a comprehensive and eminently comprehensible overview of the ideas underlying complex systems science, the current research at the forefront of this field, and the prospects for the field's contribution to solving some of the most important scientific questions of our time. (shrink)

The aim of this book is to show how supramolecular complexity of cell organization can dramatically alter the functions of individual macromolecules within a cell. The emergence of new functions which appear as a consequence of supramolecular complexity, is explained in terms of physical chemistry. The book is interdisciplinary, at the border between cell biochemistry, physics and physical chemistry. This interdisciplinarity does not result in the use of physical techniques but from the use of physical concepts to study (...) biological problems. In the domain of complexity studies, most works are purely theoretical or based on computer simulation. The present book is partly theoretical, partly experimental and theory is always based on experimental results. Moreover, the book encompasses in a unified manner the dynamic aspects of many different biological fields ranging from dynamics to pattern emergence in a young embryo. The volume puts emphasis on dynamic physical studies of biological events. It also develops, in a unified perspective, this new interdisciplinary approach of various important problems of cell biology and chemistry, ranging from enzyme dynamics to pattern formation during embryo development, thus paving the way to what may become a central issue of future biology. (shrink)

In the past decades, an enormous amount of precious information has been collected about molecular and genetic characteristics of cancer. This knowledge is mainly based on a reductionistic approach, meanwhile cancer is widely recognized to be a ‘system biology disease’. The behavior of complex physiological processes cannot be understood simply by knowing how the parts work in isolation. There is not solely a matter how to integrate all available knowledge in such a (...) way that we can still deal with complexity, but we must be aware that a deeply transformation of the currently accepted oncologic paradigm is urgently needed. We have to think in terms of biological networks: understanding of complex functions may in fact be impossible without taking into consideration influences (rules and constraints) outside of the genome. Systems Biology involves connecting experimental unsupervised multivariate data to mathematical and computational approach than can simulate biologic systems for hypothesis testing or that can account for what it is not known from high-throughput data sets. Metabolomics could establish the requested link between genotype and phenotype, providing informations that ensure an integrated understanding of pathogenic mechanisms and metabolic phenotypes and provide a screening tool for new targeted drug. (shrink)

The aims of this paper are threefold: To show that game-playing (GP), the discipline of Artificial Intelligence (AI) concerned with the development of automated game players, has a strong epistemological relevance within both AI and the vast area of cognitive sciences. In this context games can be seen as a way of securely reducing (segmenting) real-world complexity, thus creating the laboratory environment necessary for testing the diverse types and facets of intelligence produced by computer models. This paper aims to (...) promote the belief that games represent an excellent tool for the project of computational psychology (CP). To underline how, despite this, GP has mainly adopted an engineering-inspired methodology and in doing so has distorted the framework of cognitive functionalism. Many successes (i.e. chess, checkers) have been achieved refusing human-like reasoning. The AI has appeared to work well despite ignoring an intrinsic motivation, that of creating an explanatory link between machines and mind. To assert that substantial improvements in GP may be obtained in the future only by renewed interest in human-inspired models of reasoning and in other cognitive studies. In fact, if we increase the complexity of games (from NP-Completeness to AI-Completeness) in order to reproduce real-life problems, computer science techniques enter an impasse. Many of AI’s recent GP experiences can be shown to validate this. The lack of consistent philosophical foundations for cognitive AI and the minimal philosophical commitment of AI investigation are two of the major reasons that play an important role in explaining why CP has been overlooked. (shrink)

We present a system of relational syllogistic, based on classical propositional logic, having primitives of the following form: $$\begin{array}{ll}\mathbf{Some}\, a \,{\rm are} \,R-{\rm related}\, {\rm to}\, \mathbf{some} \,b;\\ \mathbf{Some}\, a \,{\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{some}\, b;\\ \mathbf{All}\, a\, {\rm are}\,R-{\rm related}\, {\rm to}\, \mathbf{all} \,b.\end{array}$$ Such primitives formalize sentences from natural language like ‘ All students read some textbooks’. Here a, b denote arbitrary sets (of objects), and R denotes an (...) arbitrary binary relation between objects. The language of the logic contains only variables denoting sets, determining the class of set terms, and variables denoting binary relations between objects, determining the class of relational terms. Both classes of terms are closed under the standard Boolean operations. The set of relational terms is also closed under taking the converse of a relation. The results of the paper are the completeness theorem with respect to the intended semantics and the computational complexity of the satisfiability problem. (shrink)

Lexical semantics has become a major research area within computational linguistics, drawing from psycholinguistics, knowledge representation, computer algorithms and architecture. Research programmes whose goal is the definition of large lexicons are asking what the appropriate representation structure is for different facets of lexical information. Among these facets, semantic information is probably the most complex and the least explored.Computational Lexical Semantics is one of the first volumes to provide models for the creation of various kinds of computerised lexicons for (...) the automatic treatment of natural language, with applications to machine translation, automatic indexing, and database front-ends, knowledge extraction, among other things. It focuses on semantic issues, as seen by linguists, psychologists, and computer scientists. Besides describing academic research, it also covers ongoing industrial projects. (shrink)

In 1979, H. Lewis shows that the computational complexity of the Boolean satisfiability problem dichotomizes, depending on the Boolean operations available to formulate instances: intractable (NP-complete) if negation of implication is definable, and tractable (in P) otherwise [21]. Recently, an investigation in the same spirit has been extended to nonclassical propositional logics, modal logics in particular [2, 3]. In this note, we pursue this line in the realm of many-valued propositional logics, and obtain complexity classifications for the (...) parameterized satisfiability problem of two pertinent samples, Kleene and Gödel logics. (shrink)

This paper continues the study of the metric topology on $2^{\mathbb {N}}$ that was introduced by S. Binns. This topology is induced by a directional metric where the distance from $Y\in2^{\mathbb {N}}$ to $X\in2^{\mathbb {N}}$ is given by \[\limsup_{n}\frac{C(X\upharpoonright n|Y\upharpoonright n)}{n}.\] This definition is closely related to the notions of effective Hausdorff and packing dimensions. Here we establish that this is a path-connected topology on $2^{\mathbb {N}}$ and that under it the functions $X\mapsto\operatorname{dim}_{\mathcal{H}}X$ and $X\mapsto\operatorname{dim}_{p}X$ are continuous. We also investigate (...) the scalar multiplication operation that was introduced by Binns. The multiplication of a real $X\in2^{\mathbb {N}}$ by an element $\alpha\in[0,1]$ represents a dilution of the information in $X$ by a factor of $\alpha$ . Our main result is to show that every regular real is the dilution of a real of Hausdorff dimension 1. That is, that the information in every regular real can be maximally compressed. (shrink)

In this paper we address an important issue in the development of an adequate formal theory of underspecified semantics. The tension between expressive power and computational tractability poses an acute problem for any such theory. Generating the full set of resolved scope readings from an underspecified representation produces a combinatorial explosion that undermines the efficiency of these representations. Moreover, Ebert (2005) shows that most current theories of underspecified semantic representation suffer from expressive incompleteness. In previous work we present an (...) account of underspecified scope representations within Property Theory with Curry Typing (PTCT), an intensional first-order theory for natural language semantics. We review this account, and we show that filters applied to the underspecified-scope terms of PTCT permit expressive completeness. While they do not solve the general complexity problem, they do significantly reduce the search space for computing the full set of resolved scope readings in non-worst cases. We explore the role of filters in achieving expressive completeness, and their relationship to the complexity involved in producing full interpretations from underspecified representations. (shrink)

In this paper we probe the limits of the computational method in economics. This method involves modeling individual behavior and economic processes in terms of constrained optimization. In neoclassical economics human behavior is explained entirely computationally. Alternative paradigms include the evolutionary and the complexity?based approaches that model behavior and processes as non?optimizing or boundedly rational. But many of the models used in ?complex?evolutionary economics? are cellular automata or their equivalents. This means that neoclassical economics and complex?evolutionary economics are (...) both committed to a computational vision of the economy. A highly complex computational economy can evolve and self?organize but it also displays computational universality that means that many problems are not decidable. The inherent limits of computability become evident. This paper proposes incorporating a particular (constructive) non?computability into our view of economic behavior and processes. The paper defines constructively non?computational behavior, discusses its origins in Roger Penrose's writings, and provides an application of this concept to the question of realistic counterfactuals in economic models. (shrink)

This is a comprehensive discussion of complexity as it arises in physical, chemical, and biological systems, as well as in mathematical models of nature. Common features of these apparently unrelated fields are emphasised and incorporated into a uniform mathematical description, with the support of a large number of detailed examples and illustrations. The quantitative study of complexity is a rapidly developing subject with special impact in the fields of physics, mathematics, information science, and biology. Because of the variety (...) of the approaches, no comprehensive discussion has previously been attempted. This book will be of interest to graduate students and researchers in physics (nonlinear dynamics, fluid dynamics, solid-state, cellular automata, stochastic processes, statistical mechanics and thermodynamics), mathematics (dynamical systems, ergodic and probability theory), information and computer science (coding, information theory and algorithmic complexity), electrical engineering and theoretical biology. (shrink)

This paper discusses essential motivational representations necessary for a comprehensive computational cognitive architecture. It hypothesizes the need for implicit drive representations, as well as explicit goal representations. Drive representations consist of primary drives — both low-level primary drives (concerned mostly with basic physiological needs) and high-level primary drives (concerned more with social needs), as well as derived (secondary) drives. On the basis of drives, explicit goals may be generated on the fly during an agent’s interaction with various situations. These (...) motivational representations help to make cognitive architectural models more comprehensive and provide deeper explanations of psychological processes. This work represents a step forward in making computational cognitive architectures better reflections of the human mind and all its motivational complexity and intricacy. (shrink)

The ultimate goal of research into computational intelligence is the construction of a fully embodied and fully autonomous artificial agent. This ultimate artificial agent must not only be able to act, but it must be able to act morally. In order to realize this goal, a number of challenges must be met, and a number of questions must be answered, the upshot being that, in doing so, the form of agency to which we must aim in developing artificial agents (...) comes into focus. This chapter explores these issues, and from its results details a novel approach to meeting the given conditions in a simple architecture of information processing. (shrink)

This is a presentation about joint work between Hector Zenil and Jean-Paul Delahaye. Zenil presents Experimental Algorithmic Theory as Algorithmic Information Theory and NKS, put together in a mixer. Algorithmic Complexity Theory defines the algorithmic complexity k(s) as the length of the shortest program that produces s. But since finding this short program is in general an undecidable question, the only way to approach k(s) is to use compression algorithms. He shows how to use the Compress function in (...) Mathematica to give an idea about the compressibility of various sequences. However, the idea of applying a compression algorithm breaks down for very short sequences. This is true not only for the Compress function, but also for any other compression algorithm. Zenil's approach is to construct a metric of algorithmic complexity for short sequences from scratch. He defines the algorithmic probability as the probability that an arbitrary program produces a sequence. The basic idea is to run a whole class of computational devices such as Turing Machines or Cellular Automata, and compute the distributions of the sequences they generate. Zenil presents a comparison of frequency distributions of sequences generated by 2-state 3-color Turing Machines and 2-color radius 1 Cellular Automata. He also compared these distributions to distributions found in data from the real world, and found that not only there is correlation across different systems, but also that the distributions are rather stable, and the difference between the distributions in abstract systems and real-world data can be attributed to noise. In his paper Zenil elaborates on the nature of the noise he has encountered. Zenil conjectures that the correlation distances between different systems decreases with a larger number of steps, and converge in the infinite limit case. (shrink)

The ability to reason and think in a logical manner forms the basis of learning for most mathematics, computer science, philosophy and logic students. Based on the author's teaching notes at the University of Maryland and aimed at a broad audience, this text covers the fundamental topics in classical logic in an extremely clear, thorough and accurate style that is accessible to all the above. Covering propositional logic, first-order logic, and second-order logic, as well as proof theory, computability theory, and (...) model theory, the text also contains numerous carefully graded exercises and is ideal for a first or refresher course. (shrink)

We show that there is a structure of countably infinite signature with $P = N_{2}P$ and a structure of finite signature with $P = N_{1}P$ and $N_{1}P \neq N_{2}P$ . We give a further example of a structure of finite signature with $P \neq N_{1}P$ and $N_{1}P \neq N_{2}P$ . Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for (...) some finite ℒ the class of ℒ-structures with $P = N_{1}P$ is not closed under ultraproducts and obtain as corollaries that this class is not $\delta$ -elementary and that the class of ᵍ-structures with $P \neq N_{1}P$ is not elementary. Finally we prove that for all f dominating all polynomials there is a structure of finite signature with the following properties: $P \neq N_{1}P$ . $N_{1}P \neq N_{2}P$ , the levels $N_{2}TIME(n^{i})$ of $N_{2}P$ and the levels $N_{1}TIME(n^{i})$ of $N_{1}P$ are different for different i, indeed $DTIME(n^{i'}) \nsubseteq N_{2}TIME(n^{i})$ if $i' \textgreater i$ ; $DTIME(f) \nsubseteq N_{2}P$ , and $N_{2}P \nsubseteq DEC$ . DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of $N_{2}P$ is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts. (shrink)

The SRL (speciate re-entrant logic) of King (1989) is a sound, complete and decidable logic designed specifically to support formalisms for the HPSG (head-driven phrase structure grammar) of Pollard and Sag (1994). The SRL notion of modellability in a signature is particularly important for HPSG, and the present paper modifies an elegant method due to Blackburn and Spaan (1993) in order to prove that – modellability in each computable signature is 1 0 – modellability in some finite signature is (...) 1 0 -hard (hence not decidable), and – modellability in some finite signature is decidable. (shrink)

Advocates of the computational theory of mind claim that the mind is a computer whose operations can be implemented by various computational systems. According to these philosophers, the mind is multiply realisable because—as they claim—thinking involves the manipulation of syntactically structured mental representations. Since syntactically structured representations can be made of different kinds of material while performing the same calculation, mental processes can also be implemented by different kinds of material. From this perspective, consciousness plays a minor role (...) in mental activity. However, contemporary neuroscience provides experimental evidence suggesting that mental representations necessarily involve consciousness. Consciousness does not only enable individuals to become aware of their own thoughts, it also constantly changes the causal properties of these thoughts. In light of these empirical studies, mental representations appear to be intrinsically dependent on consciousness. This discovery represents an obstacle to any attempt to construct an artificial mind. (shrink)

The Language of Thought program has a suicidal edge. Jerry Fodor, of all people, has argued that although LOT will likely succeed in explaining modular processes, it will fail to explain the central system, a subsystem in the brain in which information from the different sense modalities is integrated, conscious deliberation occurs, and behavior is planned. A fundamental characteristic of the central system is that it is “informationally unencapsulated” -- its operations can draw from information from any cognitive domain. The (...) domain general nature of the central system is key to human reasoning; our ability to connect apparently unrelated concepts enables the creativity and flexibility of human thought, as does our ability to integrate material across sensory divides. The central system is the holy grail of cognitive science: understanding higher cognitive function is crucial to grasping how humans reach their highest intellectual achievements. But according to Fodor, the founding father of the LOT program and the related Computational Theory of Mind (CTM), the holy grail is out of reach: the central system is likely to be non-computational (Fodor 1983, 2000, 2008). Cognitive scientists working on higher cognitive function should abandon their efforts. Research should be limited to the modules, which for Fodor rest at the sensory periphery (2000).1 Cognitive scientists who work in the symbol processing tradition outside of philosophy would reject this pessimism, but ironically, within philosophy itself, this pessimistic streak has been very influential, most likely because it comes from the most well-known proponent of LOT and CTM. Indeed, pessimism about centrality has become assimilated into the mainstream conception of LOT. (Herein, I refer to a LOT that appeals to pessimism about centrality as the “standard LOT”). I imagine this makes the standard LOT unattractive to those philosophers with a more optimistic approach to what cognitive science can achieve.. (shrink)