In this article we review some of the main results of descriptive complexity theory in order to make the reader familiar with the nature of the investigations in this area. We start by presenting the characterization of automata recognizable languages by monadic second-order logic. Afterwards we explain the characterization of various logics by fIxed-point logics. We assume familiarity with logic but try to keep knowledge of complexity theory to aminimum.

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary (...) variants and extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time or polynomial space can be characterized as collections of all classes of finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth. (shrink)

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

We prove that, for each countable ordinal ξ≥1, there exist some -complete ω-powers, and some -complete ω-powers, extending previous works on the topological complexity of ω-powers [O. Finkel, Topological properties of omega context free languages, Theoretical Computer Science 262 669–697; O. Finkel, Borel hierarchy and omega context free languages, Theoretical Computer Science 290 1385–1405; O. Finkel, An omega-power of a finitary language which is a borel set of infinite rank, Fundamenta informaticae 62 333–342; D. Lecomte, Sur les ensembles de (...) phrases infinies constructibles a partir d’un dictionnaire sur un alphabet fini, Séminaire d’Initiation a l’Analyse, 1, année 2001–2002; D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232; J. Duparc, O. Finkel, An ω-Power of a Context-Free Language Which Is Borel Above , in: S. Bold, B. Löwe, T. Räsch, J. van Benthem , in the Proceedings of the international conference foundations of the formal sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany, in: Studies in Logic, vol. 11, College Publications at King’s College, 2007, pp. 109–122]. We prove effective versions of these results; in particular, for each recursive ordinal there exist some recursive sets A2<ω such that , where and denote classes of the hyperarithmetical hierarchy. To do this, we prove effective versions of a result by Kuratowski, describing a set as the range of a closed subset of the Baire space ωω by a continuous bijection. This leads us to prove closure properties for the pointclasses in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered in [D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232]. (shrink)

§1. I will start with a quick definition of descriptive set theory: It is the study of the structure of definable sets and functions in separable completely metrizable spaces. Such spaces are usually called Polish spaces. Typical examples are ℝn, ℂn, Hilbert space and more generally all separable Banach spaces, the Cantor space 2ℕ, the Baire space ℕℕ, the infinite symmetric group S∞, the unitary group, the group of measure preserving transformations of the unit interval, etc.In this (...) class='Hi'>theory sets are classified in hierarchies according to the complexity of their definitions and the structure of sets in each level of these hierarchies is systematically analyzed. In the beginning we have the Borel sets in Polish spaces, obtained by starting with the open sets and closing under the operations of complementation and countable unions, and the corresponding Borel hierarchy. After this come the projective sets, obtained by starting with the Borel sets and closing under the operations of complementation and projection, and the corresponding projective hierarchy.There are also transfinite extensions of the projective hierarchy and even much more complex definable sets studied in descriptive set theory, but I will restrict myself here to Borel and projective sets, in fact just those at the first level of the projective hierarchy, i.e., the Borel (), analytic () and coanalytic () sets. (shrink)

Complexity theory challenges educational philosophy to reconsider accepted paradigms of teaching, learning and educational research. However, though attractive, not least because of its critique of positivism, its affinity to Dewey and Habermas, and its arguments for openness, diversity, relationships, agency and creativity, the theory is not without its difficulties. These are seen to lie in terms of complexity theory's nature, status, methodology, utility and contribution to the philosophy of education, being a descriptive theory (...) that is easily misunderstood as a prescriptive theory, silent on key issues of values and ethics that educational philosophy should embrace, of questionable internal consistency, and of limited ‘added value’ in educational philosophy. The paper sets out key tenets of complexity theory and argues that, though it is useful for educational philosophy, it requires new conceptual tools and mind‐sets to comprehend fully its significance. (shrink)

then essentially characterized the hypotheses that mechanical scientists can successfully decide in the limit in terms of arithmetic complexity. These ideas were developed still further by Peter Kugel [4]. In this paper, I extend this approach to obtain characterizations of identification in the limit, identification with bounded mind-changes, and identification in the short run, both for computers and for ideal agents with unbounded computational abilities. The characterization of identification with n mind-changes entails, as a corollary, an exact arithmetic characterization (...) of Putnam's n-trial predicates, which closes a gap of a factor of two in Putnam's original characterization [12]. (shrink)

Although the theory of definability had many important antecedents—such as the descriptive set theory initiated by the French semi-intuitionists in the early 1900s—the main ideas were first laid out in precise mathematical terms by Alfred Tarski beginning in 1929. We review here the basic notions of languages, explicit definability, and grammatical complexity, and emphasize common themes in the theories of definability for four important languages underlying, respectively, descriptive set theory, recursive function theory, classical (...) pure logic, and finite-universe logic. We review the history of previous studies of the similarities and differences in the theories of definability of the first three of these four languages. A seminal role leading toward unification of the theories has been played by the separation principles introduced by Nikolai Luzin in 1927. Emphasizing analogies and driving toward further unification embracing finite-universe logic we concentrate on a simple example—the first and second separation principles for existential-universal first-order sentences . Using this as a test case for the fundamental problem of how to “finitize” arguments in classical pure logic to the finite-universe case, we are led to the analogous negative solution by using the theory of certain special graphs: a graph is - special for any positive integers m , n , p , q iff it is bipartite with m red points and n blue points and for every p -tuple of red points there is a blue point to which they are all connected . As an aside we introduce for further study a natural “Ramseyesque” increasing sequence A of positive integers, where A is the least positive integer n for which an -special graph exists. (shrink)

Complexity theory challenges educational philosophy to reconsider accepted paradigms of teaching, learning and educational research. However, though attractive, not least because of its critique of positivism, its affinity to Dewey and Habermas, and its arguments for openness, diversity, relationships, agency and creativity, the theory is not without its difficulties. These are seen to lie in terms of complexity theory's nature, status, methodology, utility and contribution to the philosophy of education, being a descriptive theory (...) that is easily misunderstood as a prescriptive theory, silent on key issues of values and ethics that educational philosophy should embrace, of questionable internal consistency, and of limited ‘added value’ in educational philosophy. The paper sets out key tenets of complexity theory and argues that, though it is useful for educational philosophy, it requires new conceptual tools and mind‐sets to comprehend fully its significance. (shrink)

Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative (...) class='Hi'>complexity of notions that are of interest in descriptive set theory. In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals. (shrink)

We generalize the notion of analytic/Borel equivalence relations, orbit equivalence relations, and Borel reductions between them to their continuous and quantitative counterparts: analytic/Borel pseudometrics, orbit pseudometrics, and Borel reductions between them. We motivate these concepts on examples and we set some basic general theory. We illustrate the new notion of reduction by showing that the Gromov–Hausdorff distance maintains the same complexity if it is defined on the class of all Polish metric spaces, spaces bounded from below, from above, (...) and from both below and above. Then we show that [Formula: see text] is not reducible to equivalences induced by orbit pseudometrics, generalizing the seminal result of Kechris and Louveau. We answer in negative a question of Ben Yaacov, Doucha, Nies, and Tsankov on whether balls in the Gromov–Hausdorff and Kadets distances are Borel. In appendix, we provide new methods using games showing that the distance-zero classes in certain pseudometrics are Borel, extending the results of Ben Yaacov, Doucha, Nies, and Tsankov. There is a complementary paper of the authors where reductions between the most common pseudometrics from functional analysis and metric geometry are provided. (shrink)

This paper presents a number of objections to Jeffrey King's quantificational theory of complex demonstratives. Some of these objections have to do with modality, whereas others concern attitude ascriptions. Various possible replies are considered. The debate between quantificational theorists and direct reference theorists over complex demonstratives is compared with recent debates concerning definite descriptions.

We discuss some of the experimental motivation for the need for semigroup decay laws and the quantum Lax-Phillips theory of scattering and unstable systems. In this framework, the decay of an unstable system is described by a semigroup. The spectrum of the generator of the semigroup corresponds to the singularities of the Lax-Phillips S-matrix. In the case of discrete (complex) spectrum of the generator of the semigroup, associated with resonances, the decay law is exactly exponential. The states corresponding to (...) these resonances (eigenfunctions of the generator of the semigroup) lie in the Lax-Phillips Hilbert space, and, therefore, all physical properties of the resonant states can be computed. We show that the parametrized relativistic quantum theory is a natural setting for the realization of the Lax-Phillips theory. (shrink)

We develop a category theoretical scheme for the comprehension of the information structure associated with a complex system, in terms of families of partial or local information carriers. The scheme is based on the existence of a categorical adjunction, that provides a theoretical platform for the descriptive analysis of the complex system as a process of functorial information communication.

SUMMARYA discussion of Western notions of ‘sacrifice’ can benefit from descriptions of non-Western understandings of ‘sacrifice’, in the sense that non-Western understandings of ‘sacrifice’ introduce aspects and dimensions into the debate that may not have been fully taken into account so far. In order to find out whether the Indian case confirms Western scholarly theories of religious sacrifice, ideas and practices regarding sacrifice in the Mahābhārata epic and in the Bhagavadgītā will be confronted with several of these theories, in particular (...) some current in cultural anthropology and religious studies which focus on gift exchange, self-sacrifice or violence. A conjectural conclusion as to why human beings sacrifice in general will be drawn at the very end of this essay in comparative religion. (shrink)

What is the relationship between complexity in the world and complexity in the mind? Intuitively, increasingly complex objects and events should give rise to increasingly complex mental representations (or perhaps a plateau in complexity after a certain point). However, a counterintuitive possibility with roots in information theory is an inverted U-shaped relationship between the “objective” complexity of some stimulus and the complexity of its mental representation, because excessively complex patterns might be characterized by surprisingly (...) short computational descriptions (e.g., if they are represented as having been generated “randomly”). Here, we demonstrate that this is the case, using a novel approach that takes the notion of “description” literally. Subjects saw static and dynamic visual stimuli whose objective complexity could be carefully manipulated, and they described these stimuli in their own words by giving freeform spoken descriptions of them. Across three experiments totaling over 10,000 speech clips, spoken descriptions of shapes (Experiment 1), dot-arrays (Experiment 2), and dynamic motion-paths (Experiment 3) revealed a striking quadratic relationship between the raw complexity of these stimuli and the length of their spoken descriptions. In other words, the simplest and most complex stimuli received the shortest descriptions, while those stimuli with a “medium” degree of complexity received the longest descriptions. Follow-up analyses explored the particular words used by subjects, allowing us to further explore how such stimuli were represented. We suggest that the mind engages in a kind of lossy compression for overly complex stimuli, and we discuss the utility of such freeform responses for exploring foundational questions about mental representation. (shrink)

When philosophers talk about descriptions, usually they have in mind singular definite descriptions such as ‘the finest Greek poet’ or ‘the positive square root of nine’, phrases formed with the definite article ‘the’. English also contains indefinite descriptions such as ‘a fine Greek poet’ or ‘a square root of nine’, phrases formed with the indefinite article ‘a’ (or ‘an’); and demonstrative descriptions (also known as complex demonstratives) such as ‘this Greek poet’ and ‘that tall woman’, formed with the demonstrative articles (...) ‘this’ and ‘that’. Following the custom in philosophy, in this chapter often we use ‘description’ as short for ‘definite description’; and following the custom in linguistics, often we use ‘definite’, ‘indefinite’, and ‘demonstrative’ as shorthand nouns. For the most part we focus on definite and indefinites, although a few words about demonstratives are called for. At the centre of debates about descriptions is the matter of whether they are devices of reference or of predication (simple or higher-order), and much discussion focuses on how various proposals are to be incorporated into broader theories of the semantics of natural language. But philosophical interest goes beyond the confines of linguistics, logic, and the philosophy of language because choices made about the semantics of descriptions have repercussions elsewhere, particularly in epistemology and metaphysics. A simple match of form and meaning appears to fail.1 First, many occurrences of expressions of both forms ‘the φ’ and ‘a φ’ appear to be used to talk about particular individuals. Consider (1). (shrink)

Dynamic systems theory (DS) provides tools for exploring how simpler elements can interact to produce complex psychological configurations. It may, as Lewis demonstrates, provide means for explicating relationships between two reductionist approaches to overlapping sets of phenomena. The result is a description of psychological phenomena at a level that begins to achieve the richness we would hope to achieve in examining psychological life as it is experienced and explored in psychoanalysis.

In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NC R , PAR R , EXP R and some others more.

Standard semantic theories predict that non-deictic readings for complex demonstratives should be much more widely available than they in fact are. If such readings are the result of a lexical ambiguity, as Kaplan (1977) and others suggest, we should expect them to be available wherever a definite description can be used. The same prediction follows from ‘hidden argument’ theories like the ones described by King (2001) and Elbourne (2005). Wolter (2006), however, has shown that complex demonstratives admit non-deictic interpretations only (...) when a precise set of structural constrains are met. In this paper, I argue that Wolter’s results, properly understood, upend the philosophical status quo. They fatally undermine the ambiguity theory and demand a fundamental rethinking of the hidden argument approach. (shrink)

I criticized Jeffrey King’s theory of complex demonstratives in “Problems for a Quantificational Theory of Complex Demonstratives.” King replied in “Complex Demonstratives as Quantifiers: Objections and Replies.” I here comment on some of King’s replies.

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)

In this article I try to show the philosophical continuity of Russell's ideas from his paradox of classes to Principia mathematica. With this purpose, I display the main results (descriptions, substitutions and types) as moments of the same development, whose principal goal was (as in his The principles) to look for a set of primitive ideas and propositions giving an account of all mathematics in logical terms, but now avoiding paradoxes. The sole way to reconstruct this central period in Russell (...) is to resort to unpublished manuscripts, which show the publications of these years to be the extremities of one same iceberg. Thus the logical problems (doubts about propositions, matrices and functions) are parallel to the ontological (the searching for genuine logical subjects) and methodological ones (the status of eliminative reduction). Paradoxes were the cause that the kind of (constructive) definition already applied by Russell, as an inheritance of Moorean analysis, obtained a new trait: ontological elimination, which, beginning with a ?no classes theory? and the theory of descriptions, led to a new theory of judgment (already present in manuscripts from 1906), ?incomplete symbols, and logical constructions. (shrink)

Abstract:About 1904 Meinong formulated his most famous idea: there are no empty (non-referential) terms. Russell also did not accept non-referential singular terms, but in “On Denoting” he claimed that all singular terms that are apparently empty could be explained away as apparent singular terms. However, if we take a more careful look at both theories, the picture becomes more complex. It is well known that Russell’s concept of a genuine proper name is very technical; but this is also true of (...) Meinong. Also, according to Meinong we can refer “directly” only to a very special category of ontologically simple objects. However, a very important difference is that, in the domain of Meinongian objects, a plurality of objects always corresponds to each description. Thus, if Meinong were right, there could be no definite descriptions. If we narrow the domain of reference to existent objects, we can secure the uniqueness of the reference object by specifying a collection of predicates that is contingently satisfied by only one (existing) object. But if we operate in the domain of all possible objects, we have to specify all properties that are had by the object in question. It turns out that such a “Leibnizian” specification amounts to the complete description of a possible world. (shrink)

This paper considers the impact of complexity theory on the way in which we see propositions corresponding to the reality that they describe, and our concept of truth in that context. A contingently associated idea is the atomistic expectation that we can reduce language to primitive units of meaning, and tie those in with agreed units of experience. If we see both language and the reality that it describes and explains as complex, this position becomes difficult to maintain. (...) Complexity theory, with its emphasis on non‐linear and dynamic interactions between multiple variables, within indeterminate and transient systems, supports the case for a connectionist and holistic analysis. Theories are more likely to be under‐determined by evidence and open to interpretation, with the potential for ‘certainties’ weakened. If educational situations are complex, then the drive towards specific and focused research findings that will support policy and practice, and the associated notion of control, is illusory. Rather than providing evidence for prescription, research is thus understood as descriptive and explanatory, within a range of interpretative possibilities. Action takes place within a necessarily incomplete and constantly changing situation, more appropriately understood in terms of survival than control. (shrink)

Descriptive semantic theories purport to characterize the meanings of the expressions of languages in whatever complexity they might have. Foundational semantics purports to identify the kind of considerations relevant to establish that a given descriptive semantics accurately characterizes the language used by a given individual or community. Foundational Semantics I presents three contrasting approaches to the foundational matters, and the main considerations relevant to appraise their merits. These approaches contend that we should look at the contents of (...) speakers’ intuitions; at the deep psychology of users and its evolutionary history, as revealed by our best empirical theories; or at the personal‐level rational psychology of those subjects. Foundational Semantics II examines a fourth view, according to which we should look instead at norms enforced among speakers. The two papers aim to determine in addition the extent to which the approaches are really rival, or rather complementary. (shrink)

We introduce the notion of complexity, first at an intuitive level and then in relatively more concrete terms, explaining the various characteristic features of complex systems with examples. There exists a vast literature on complexity, and our exposition is intended to be an elementary introduction, meant for a broad audience. -/- Briefly, a complex system is one whose description involves a hierarchy of levels, where each level is made of a large number of components interacting among themselves. The (...) time evolution of such a system is of a complex nature, depending on the interactions among subsystems in the next level below the one under consideration and, at the same time, conditioned by the level above, where the latter sets the context for the evolution. Generally speaking, the interactions among the constituents of the various levels lead to a dynamics characterized by numerous characteristic scales, each level having its own set of scales. What is more, a level commonly exhibits ‘emergent properties’ that cannot be derived from considerations relating to its component systems taken in isolation or to those in a different contextual setting. In the dynamic evolution of some particular level, there occurs a self-organized emergence of a higher level and the process is repeated at still higher levels. -/- The interaction and self-organization of the components of a complex system follow the principle commonly expressed by saying that the ‘whole is different from the sum of the parts’. In the case of systems whose behavior can be expressed mathematically in terms of differential equations this means that the interactions are nonlinear in nature. -/- While all of the above features are not universally exhibited by complex systems, these are nevertheless indicative of a broad commonness relative to which individual systems can be described and analyzed. There exist measures of complexity which, once again, are not of universal applicability, being more heuristic than exact. The present state of knowledge and understanding of complex systems is itself an emerging one. Still, a large number of results on various systems can be related to their complex character, making complexity an immensely fertile concept in the study of natural, biological, and social phenomena. -/- All this puts a very definite limitation on the complete description of a complex system as a whole since such a system can be precisely described only contextually, relative to some particular level, where emergent properties rule out an exact description of more than one levels within a common framework. -/- We discuss the implications of these observations in the context of our conception of the so-called noumenal reality that has a mind-independent existence and is perceived by us in the form of the phenomenal reality. The latter is derived from the former by means of our perceptions and interpretations, and our efforts at sorting out and making sense of the bewildering complexity of reality takes the form of incessant processes of inference that lead to theories. Strictly speaking, theories apply to models that are constructed as idealized versions of parts of reality, within which inferences and abstractions can be carried out meaningfully, enabling us to construct the theories. -/- There exists a correspondence between the phenomenal and the noumenal realities in terms of events and their correlations, where these are experienced as the complex behavior of systems or entities of various descriptions. The infinite diversity of behavior of systems in the phenomenal world are explained within specified contexts by theories. The latter are constructs generated in our ceaseless attempts at interpreting the world, and the question arises as to whether these are reflections of `laws of nature' residing in the noumenal world. This is a fundamental concern of scientific realism, within the fold of which there exists a trend towards the assumption that theories express truths about the noumenal reality. We examine this assumption (referred to as a ‘point of view’ in the present essay) closely and indicate that an alternative point of view is also consistent within the broad framework of scientific realism. This is the view that theories are domain-specific and contextual, and that these are arrived at by independent processes of inference and abstractions in the various domains of experience. Theories in contiguous domains of experience dovetail and interpenetrate with one another, and bear the responsibility of correctly explaining our observations within these domains. -/- With accumulating experience, theories get revised and the network of our theories of the world acquires a complex structure, exhibiting a complex evolution. There exists a tendency within the fold of scientific realism of interpreting this complex evolution in rather simple terms, where one assumes (this, again, is a point of view) that theories tend more and more closely to truths about Nature and, what is more, progress towards an all-embracing ‘ultimate theory’ -- a foundational one in respect of all our inquiries into nature. We examine this point of view closely and outline the alternative view -- one broadly consistent with scientific realism -- that there is no ‘ultimate’ law of nature, that theories do not correspond to truths inherent in reality, and that successive revisions in theory do not lead monotonically to some ultimate truth. Instead, the theories generated in succession are incommensurate with each other, testifying to the fact that a theory gives us a perspective view of some part of reality, arrived at contextually. Instead of resembling a monotonically converging series successive theories are analogous to asymptotic series. -/- Before we summarize all the above considerations, we briefly address the issue of the complexity of the {\it human mind} -- one as pervasive as the complexity of Nature at large. The complexity of the mind is related to the complexity of the underlying neuronal organization in the brain, which operates within a larger biological context, its activities being modulated by other physiological systems, notably the one involving a host of chemical messengers. The mind, with no materiality of its own, is nevertheless emergent from the activity of interacting neuronal assemblies in the brain. As in the case of reality at large, there can be no ultimate theory of the mind, from which one can explain and predict the entire spectrum of human behavior, which is an infinitely rich and diverse one. (shrink)

Answering one of the main questions of [S.-D. Friedman, T. Hyttinen and V. Kulikov, Generalized descriptive set theory and classification theory, Mem. Amer. Math. Soc. 230 80, Chap. 7], we show that there is a tight connection between the depth of a classifiable shallow theory [Formula: see text] and the Borel rank of the isomorphism relation [Formula: see text] on its models of size [Formula: see text], for [Formula: see text] any cardinal satisfying [Formula: see text]. (...) This is achieved by establishing a link between said rank and the [Formula: see text]-Scott height of the [Formula: see text]-sized models of [Formula: see text], and yields to the following descriptive set-theoretical analog of Shelah’s Main Gap Theorem: Given a countable complete first-order theory [Formula: see text], either [Formula: see text] is Borel with a countable Borel rank, or it is not Borel at all. The dividing line between the two situations is the same as in Shelah’s theorem, namely that of classifiable shallow theories. We also provide a Borel reducibility version of the above theorem, discuss some limitations to the possible complexities of [Formula: see text], and provide a characterization of categoricity of [Formula: see text] in terms of the descriptive set-theoretical complexity of [Formula: see text]. (shrink)

Descriptive semantic theories purport to characterize the meanings of the expressions of languages in whatever complexity they might have. Foundational semantics purports to identify the kind of considerations relevant to establish that a given descriptive semantics accurately characterizes the language used by a given individual or community. Foundational Semantics I presents three contrasting approaches to the foundational matters, and the main considerations relevant to appraise their merits. These approaches contend that we should look at the contents of (...) speakers’ intuitions; at the deep psychology of users and its evolutionary history, as revealed by our best empirical theories; or at the personal-level rational psychology of those subjects. Foundational Semantics II examines a fourth view, according to which we should look instead at norms enforced among speakers. The two papers aim to determine in addition the extent to which the approaches are really rival, or rather complementary. (shrink)

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

The philosophical conception of mechanistic explanation is grounded on a limited number of canonical examples. These examples provide an overly narrow view of contemporary scientific practice, because they do not reflect the extent to which the heuristic strategies and descriptive practices that contribute to mechanistic explanation have evolved beyond the well-known methods of decomposition, localization, and pictorial representation. Recent examples from evolutionary robotics and network approaches to biology and neuroscience demonstrate the increasingly important role played by computer simulations and (...) mathematical representations in the epistemic practices of mechanism discovery and mechanism description. These examples also indicate that the scope of mechanistic explanation must be re-examined: With new and increasingly powerful methods of discovery and description comes the possibility of describing mechanisms far more complex than traditionally assumed. (shrink)

This chapter contains sections titled: Simultaneity 1—Knower and Knowledge Simultaneities 2, 3, and 4—Transphenomenality, Transdisciplinarity, and Interdiscursivity Simultaneity 5—Descriptive and Pragmatic Insights Simultaneity 6—Representation and Presentation Simultaneity 7—Affect and Effect Simultaneity 8—Education and Research A Closing Note on Complicity: The Need for Critical Reflection References.

This paper investigates the compatibility between the theoretical framework of the global neuronal workspace theory (GNWT) of conscious processing and the perturbational complexity index (PCI). Even if it has been introduced within the framework of a concurrent theory (i.e. Integrated Information Theory), PCI appears, in principle, compatible with the main tenet of GNWT, which is a conscious process that depends on a long-range connection between different cortical regions, more specifically on the amplification, global propagation, and integration (...) of brain signals. Notwithstanding this basic compatibility, a number of limited compatibilities and apparent differences emerge. This paper starts from the description of brain complexity, a notion that is crucial for PCI, to then summary of the main features of PCI and the main tenets of GNWT. Against this background, the text explores the compatibility between PCI and GNWT. It concludes that GNWT and PCI are fundamentally compatible, even though there are some partial disagreements and some points to further examine. (shrink)

This fine collection of essays by a leading philosopher of science presents a defence of integrative pluralism as the best description for the complexity of scientific inquiry today. The tendency of some scientists to unify science by reducing all theories to a few fundamental laws of the most basic particles that populate our universe is ill-suited to the biological sciences, which study multi-component, multi-level, evolved complex systems. This integrative pluralism is the most efficient way to understand the different and (...) complex processes - historical and interactive - that generate biological phenomena. This book will be of interest to students and professionals in the philosophy of science. (shrink)

Some demonstrative expressions, those we might term ‘bare demonstratives’, appear without any appended descriptive content (e.g. occurrences of ‘this’ or ‘that’ simpliciter). However, it seems that the majority of demonstrative occurrences do not follow this model. ‘Complex demonstratives’ is the collective term I shall use for phrases formed by adjoining one or more common nouns to a demonstrative expression (e.g. ‘that cat’, ‘this happy man’) and I will call the combination of predicates immediately concatenated with the demonstrative in such (...) phrases the ‘matrix’ of the expression. The question, then, is how we should construe the logical form of such expressions within a semantic theory for our language; and I wish to suggest that some recent answers to this question are, in fact, mistaken. The structure of the paper is as follows: first, I wish to highlight two (often underlying) assumptions about the nature of noun phrases in general, and suggest that, if they are both adopted, they apparently constrain the possible accounts of the logical form of complex demonstratives to just three options. The second and third parts of the paper will be concerned with expanding these options and arguing that none of them are adequate; thus the major part of the paper is concerned with the negative claim that the most obvious moves to make in this area must actually fail on closer inspection. The fourth and final section will then (very briefly) sketch the positive thesis of the paper: that we can deliver a clear and cohesive account of complex demonstratives, armed simply with elements which we will draw from David Kaplan’s theory of demonstratives, but only at the cost of rejecting (or at least refining) one assumption we recognised initially. (shrink)

We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L ′ are two logics and μ is an asymptotic measure on finite structures, then $\scr{L}\equiv _{\text{a.e.}}\scr{L}^{\prime}(\mu)$ means that there is a class C of finite structures with μ (C)=1 (...) and such that L and L ′ define the same queries on C. We carry out a systematic investigation of $\equiv _{\text{a.e.}}$ with respect to the uniform measure and analyze the $\equiv _{\text{a.e.}}$ -equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework. (shrink)

We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of Lindström quantifers , (...) though it remains open whether this can be done for LOGSPACENP. (shrink)

A categorical, higher dimensional algebra and generalized topos framework for Łukasiewicz–Moisil Algebraic–Logic models of non-linear dynamics in complex functional genomes and cell interactomes is proposed. Łukasiewicz–Moisil Algebraic–Logic models of neural, genetic and neoplastic cell networks, as well as signaling pathways in cells are formulated in terms of non-linear dynamic systems with n-state components that allow for the generalization of previous logical models of both genetic activities and neural networks. An algebraic formulation of variable ‘next-state functions’ is extended to a Łukasiewicz–Moisil (...) Topos with an n-valued Łukasiewicz–Moisil Algebraic Logic subobject classifier description that represents non-random and non-linear network activities as well as their transformations in developmental processes and carcinogenesis. The unification of the theories of organismic sets, molecular sets and Robert Rosen’s (M,R)-systems is also considered here in terms of natural transformations of organismal structures which generate higher dimensional algebras based on consistent axioms, thus avoiding well known logical paradoxes occurring with sets. Quantum bionetworks, such as quantum neural nets and quantum genetic networks, are also discussed and their underlying, non-commutative quantum logics are considered in the context of an emerging Quantum Relational Biology. (shrink)

First we prove that the set of countable linear orders of the form I + I form a complete analytic set. As a consequence of this we improve a result of Humke and Laczkovich, who showed in [HL] that the set of functions of the form f ⚬ f form a true analytic set in C[0, 1]. We show that these functions form a complete analytic set, solving a problem mentioned on p. 215 of [K1] and on p. 4 of (...) [B]. (shrink)

This paper considers the impact of complexity theory on the way in which we see propositions corresponding to the reality that they describe, and our concept of truth in that context. A contingently associated idea is the atomistic expectation that we can reduce language to primitive units of meaning, and tie those in with agreed units of experience. If we see both language and the reality that it describes and explains as complex, this position becomes difficult to maintain. (...) Complexity theory, with its emphasis on non‐linear and dynamic interactions between multiple variables, within indeterminate and transient systems, supports the case for a connectionist and holistic analysis. Theories are more likely to be under‐determined by evidence and open to interpretation, with the potential for ‘certainties’ weakened. If educational situations are complex, then the drive towards specific and focused research findings that will support policy and practice, and the associated notion of control, is illusory. Rather than providing evidence for prescription, research is thus understood as descriptive and explanatory, within a range of interpretative possibilities. Action takes place within a necessarily incomplete and constantly changing situation, more appropriately understood in terms of survival than control. (shrink)

The paper gives a hermeneutical description of Jung’s theory of complexes and archetypes, in which the complexes are defined as those parts of psyche which have split from it. Thus the human inward could not be conceived as a simple and unified whole. Complexes were understood as neutral “nodal points” of the inner structure of psyche. Jung’s searching for the factors of their formation resulted in articulating of the theory of archetypes which he saw as the invisible “roots (...) of consciousness”. Later on an important connection between the theory of archetypes and Plato’s doctrine of history was postulated. The conception of archetypes was taken as a new interpretation of the latter, going back to A. Schopenhauer. In his articulation of the theory of archetypes Jung was influenced mainly by Kant’s conception of apriori intuitions and categories. In conclusion the author critically compares Jung’s conception with the existential of M. Heidegger, drawing from O. ?álek’s work. (shrink)

Several complexity theorists draw a sharp and ontologically robust distinction between (merely) complicated systems and (genuinely) complex systems. I argue that this distinction does not hold. Upon fine-grained analysis, ostensibly complicated systems turn out to be complex systems. The purported boundary between the complicated and the complex appears to be vague rather than sharp. Systems are complex by degrees.

A categorical, higher dimensional algebra and generalized topos framework for Łukasiewicz–Moisil Algebraic–Logic models of non-linear dynamics in complex functional genomes and cell interactomes is proposed. Łukasiewicz–Moisil Algebraic–Logic models of neural, genetic and neoplastic cell networks, as well as signaling pathways in cells are formulated in terms of non-linear dynamic systems with n-state components that allow for the generalization of previous logical models of both genetic activities and neural networks. An algebraic formulation of variable ‘next-state functions’ is extended to a Łukasiewicz–Moisil (...) Topos with an n-valued Łukasiewicz–Moisil Algebraic Logic subobject classifier description that represents non-random and non-linear network activities as well as their transformations in developmental processes and carcinogenesis. The unification of the theories of organismic sets, molecular sets and Robert Rosen’s (M,R)-systems is also considered here in terms of natural transformations of organismal structures which generate higher dimensional algebras based on consistent axioms, thus avoiding well known logical paradoxes occurring with sets. Quantum bionetworks, such as quantum neural nets and quantum genetic networks, are also discussed and their underlying, non-commutative quantum logics are considered in the context of an emerging Quantum Relational Biology. (shrink)

While proper names in argument positions have received a lot of attention, this cannot be said about proper names in the naming construction, as in “Call me Al”. I argue that in a number of more or less familiar languages the syntax of naming constructions is such that proper names there have to be analyzed as predicates, whose content mentions the name itself (cf. “quotation theories”). If proper names can enter syntax as predicates, then in argument positions they should have (...) a complex structure, consisting of a determiner and its restriction, like common nouns (cf. “definite description theories of proper names”). Further consideration of the compositional semantics of proper names in the naming construction also shows that they have another argument slot, that of the naming convention. As a result, we will be able to account for the indexicality of proper names in argument positions and provide compositional semantics of complex and modified proper names (e.g., the famous detective Sherlock Holmes ). (shrink)

The present thesis, compatible with Darwinian theory, endeavours to provide original answers to the question of why the evolution of species leads to beings more complex than those existing before. It is based on the repetition of two main principles alleged to play a role in evolution towards complexity, i.e. "juxtaposition" and "integration". Juxtaposition is the addition of identical entities. Integration is the modification, or specialisation, of these entities, leading to entities on a higher level, which use the (...) previous entities as units. Several concrete examples of the process are given, at the genetic level (introns), at the anatomical level and at the social level. Structures where integration at one level leaves the units at a lower level in a state of relative autonomy can be describedusing the metaphor of the "mosaic", and the description can also be applied to the human brain and functioning of thought, where essential functions such as language or memory have a mosaic structure. (shrink)

Standard semantic theories predict that non-deictic readings for complex demonstratives should be much more widely available than they in fact are. If such readings are the result of a lexical ambiguity, as Kaplan (in: Almog, Perry, Wettstein (eds) Themes from Kaplan, Oxford University Press, Oxford, 1977) and others suggest, we should expect them to be available wherever a definite description can be used. The same prediction follows from ‘hidden argument’ theories like the ones described by King (Complex Demonstratives: a Quantificational (...) Account, MIT Press, Cambridge, 2001) and Elbourne (Situations and Individuals, MIT Press, Cambridge, 2005). Wolter (That’s That; the Semantics and Pragmatics of Demonstrative Noun Phrases. Ph.D. thesis, University of California at Santa Cruz, 2006), however, has shown that complex demonstratives admit non-deictic interpretations only when a precise set of structural constrains are met. In this paper, I argue that Wolter’s results, properly understood, upend the philosophical status quo. They fatally undermine the ambiguity theory and demand a fundamental rethinking of the hidden argument approach. (shrink)

This article explores the place of complexity science within education and educational research. The discussion begins with the suggestion that educational research has a history of adopting interpretive frames from other domains with little adaptation. Complexity science is argued to compel a different sort of positioning, one that requires accommodation and participation rather than unproblematized assimilation and application. The argument is developed by considering the following simultaneities in education (and) research: knower and knowledge; transphenomenality; transdisciplinarity; interdiscursivity; descriptive (...) and pragmatic insights; representation and presentation; affect and effect; and education and research. (shrink)