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

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.

A Cantor series expansion for a real number x with respect to a basic sequence $Q=(q_1,q_2,\dots )$, where $q_i \geq 2$, is a generalization of the base b expansion to an infinite sequence of bases. Ki and Linton in 1994 showed that for ordinary base b expansions the set of normal numbers is a $\boldsymbol {\Pi }^0_3$ -complete set, establishing the exact complexity of this set. In the case of Cantor series there are three natural notions of normality: normality, (...) ratio normality, and distribution normality. These notions are equivalent for base b expansions, but not for more general Cantor series expansions. We show that for any basic sequence the set of distribution normal numbers is $\boldsymbol {\Pi }^0_3$ -complete, and if Q is $1$ -divergent then the sets of normal and ratio normal numbers are $\boldsymbol {\Pi }^0_3$ -complete. We further show that all five non-trivial differences of these sets are $D_2(\boldsymbol {\Pi }^0_3)$ -complete if $\lim _i q_i=\infty $ and Q is $1$ -divergent. This shows that except for the trivial containment that every normal number is ratio normal, these three notions are as independent as possible. (shrink)

Journal of Mathematical Logic, Volume 25, Issue 02, August 2025. Let [math] be an integer. We show that the set of real numbers that are Poisson generic in base b is [math]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base b and not Poisson generic in base b is complete for the class given by the differences between [math] sets. We also show that the effective versions (...) of these results hold in the effective Borel hierarchy. (shrink)

Let [Formula: see text] be an integer. We show that the set of real numbers that are Poisson generic in base b is [Formula: see text]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base b and not Poisson generic in base b is complete for the class given by the differences between [Formula: see text] sets. We also show that the effective versions of these results hold (...) in the effective Borel hierarchy. (shrink)

We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M' over the same vocabulary if Φ is true on M but false on M'. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M'. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M'. We prove that every n-element structure M is identifiable by a (...) formula with quantifier rank less than (1- 1/2k)n+k²-k+4 and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than (1-1/2k²+2)n+k quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than n-√ n+k²+k quantifiers suffice to identify M and, as long as we keep the number of universal quantifiers bounded by a constant, at total n-O(√ n) quantifiers are necessary. (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)

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)

Let μ be a universal lower enumerable semi-measure . Any computable upper bound for μ can be effectively separated from zero with a constant . Computable positive lower bounds for μ can be nontrivial and allow one to construct natural examples of hypersimple sets.

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

Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n-randomness is definable purely in terms of K. To do this (...) we extend a certain “limsup” formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $\Delta _2^0$ sets of minimal descriptions. (shrink)

Keith S. Donnellan’s article “Reference and Definite Descriptions” (1966) was written with the intention of showing that the theories of Bertrand Russell and Peter F. Strawson equally fail to capture the actual linguistic use of definite descriptions. With this end, Donnellan dwells on the distinction between the attributive and referential uses. However, the situation is complicated for Donnellan in light of the fact that many conceivable uses of definite descriptions do not seem to fit into either category. There are uses (...) that should be understood as deferential rather than attributive, just as there are uses in which various possibilities of referential failure committed by speakers result in situations in which the description simply does not account for the variety of possibilities, that is, cases in which one cannot speak of either a referential or an attributive use. The reason for this seems to be that there is hardly a “pure” attributive use. The descriptions used in common examples usually contain referential elements, such as nouns and indexicals. When these are misused, the inadequacy of Donnellan’s distinction is exposed. The second thesis presented here is that the attributive uses envisaged in Donnellan’s classic paper are characterized by their distinctive inferencial nature, with the consequence that the attributive use is generally less natural and plausible than the referential use. (shrink)

Cerebellar Purkinje cells generate two distinct types of spikes, complex and simple spikes, both of which have conventionally been considered to be highly irregular, suggestive of certain types of stochastic processes as underlying mechanisms. Interestingly, however, the interspike interval structures of complex spikes have not been carefully studied so far. We showed in a previous study that simple spike trains are actually composed of regular patterns and single interspike intervals, a mixture that could not be explained by a simple rate-modulated (...) Poisson process. In the present study, we systematically investigated the interspike interval structures of separated complex and simple spike trains recorded in anaesthetized rats, and derived an appropriate stochastic model. We found that: (i) complex spike trains do not exhibit any serial correlations, so they can effectively be generated by a renewal process, (ii) the distribution of intervals between complex spikes exhibits two narrow bands, possibly caused by two oscillatory bands (0.5–1 and 4–8 Hz) in the input to Purkinje cells and (iii) the regularity of regular patterns and single interspike intervals in simple spike trains can be represented by gamma processes of orders, which themselves are drawn from gamma distributions, suggesting that multiple sources modulate the regularity of simple spike trains. (shrink)

We show that if κ is a weakly compact cardinal then the embeddability relation on trees of size κ is invariantly universal. This means that for every analytic quasi-order R on the generalized Cantor space View the MathML source there is an Lκ+κ-sentence φ such that the embeddability relation on its models of size κ, which are all trees, is Borel bi-reducible to R. In particular, this implies that the relation of embeddability on trees of size κ is complete for (...) analytic quasi-orders on View the MathML source. These facts generalize analogous results for κ=ω obtained in Louveau and Rosendal [17] and Friedman and Motto Ros [6], and it also partially extends a result from Baumgartner [3] concerning the structure of the embeddability relation on linear orders of size κ. (shrink)

The generation of route descriptions is a fundamental task of navigation systems. A particular problem in this context is to identify routes that can easily be described and processed by users. In this work, we present a framework for representing route networks with the qualitative information necessary to evaluate and optimize route descriptions with regard to ambiguities in them. We identify different agent models that differ in how agents are assumed to process route descriptions while navigating through route networks and (...) discuss which agent models can be translated into PDL programs. Further, we analyze the computational complexity of matching route descriptions and paths in route networks in dependency of the agent model. Finally, we empirically evaluate the influence of the agent model on the optimization and the processing of route instructions. (shrink)

The social intuitionist approach to moral judgments advanced by social psychologist Jonathan Haidt presupposes that it is possible to provide an explanation of the human moral sense without normative implications. By contrast, Iris Murdoch’s philosophical work on moral psychology suggests that every description of morality necessarily involves evaluative features that reveal the thinker’s own moral attitudes and implicit philosophical pictures. In the light of this, we contend that Haidt’s treatment of the story about Julie and Mark, two siblings who decide (...) to have casual, protected, and in his view harmless sex, provides a too simplistic picture of what is involved in understanding human morality. Despite his aim to explain the roots of moral judgments, he fails to provide a deeper understanding of morality in two different respects. First, he does so by suggesting that his story contains all the relevant information needed to take a moral stand on it, and by rejecting as irrelevant the wider human context in which questions about sexual and family relations arise. Second, he simplifies the responses of the people who are subject to his experiment by disregarding their various reasons for disapproving and by equating understanding human morality with explaining an impersonal psychological process. (shrink)

The article will be divided into three parts: 1. Explain the literary origins of the nesting pattern and its relationship to cinema narrative, and analyse the nesting tactics commonly used in films under Hollywood’s classical narrative. 2. Describe the variations in nested structures in films made in the 1990s, focusing on self-reflexive nesting, which emerged as a new model beyond conventional nesting during this period. 3. Distinguish the literary style of embedded narratives from the visual recognition mode and provide an (...) example of how the latter is used in films to create impossible puzzles. (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)

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)

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.

Background Individuals living with multimorbidity and/or mental health issues, low education, socioeconomic status, and polypharmacy are often called complex patients. The complexity of their health and social care needs can make them prone to disease burden and suffering. Therefore, they frequently access health care services to seek guidance for managing their illness and suffering. Aims The aim of this research was to describe the approaches used by nurses to alleviate the suffering of individuals with multimorbidity and complex needs in (...) acute care settings. Research Design A qualitative descriptive approach. Participants and Research Context Semi-structured interviews were conducted with 19 nurses working in general, medical-surgical, specialized, and intensive care settings across five hospitals in Pakistan. Reflexive thematic analysis was used for analysis. Ethical Considerations Ethical approval was obtained from the Ethical Committee of Al-Nafees Medical College Islamabad, Pakistan. Findings Four themes were generated: Deeper Exploration of Patients’ Health-Illness Situation and Complexity, Prioritizing Patient Psychosocial and Emotional Needs, Instilling Hope and Encouragement in Patients, and Creating a Comforting Environment to Foster Sharing of felt needs. Discussion Nurses emphasized the need of deeper inquiry into patients illness situation and complexity to discern the impact of determinants on their well-being and develop care plans that are tailored to address psychosocial, emotional, and physical suffering of this patient population. Conclusions Alleviation of patient suffering is integral to compassionate nursing care. Nurses use a multifaceted approach entailing sensitive understanding, recognizing sociocultural and structural determinants impact on patient situation, and individual and interdisciplinary altruistic actions to alleviate patient suffering. (shrink)

Lautemann et al. (1995) gave a descriptive characterisation of the class of context-free languages, showing that a language is context-free iff it is definable as the set of words satisfying some sentence of a particular logic (fragment) over words. The present notes discuss how to specialise this result to the class of linear languages. Somewhat surprisingly, what would seem the most straightforward specialisation actually fails, due to the fact that linear grammars fail to admit a Greibach normal form. We (...) identify an alternative specialisation, based on an alternative characterisation of context-free languages, also noted by Lautemann et al. (1995). (shrink)

We propose a nonmonotonic Description Logic of typicality able to account for the phenomenon of combining prototypical concepts, an open problem in the fields of AI and cognitive modelling. Our logic extends the logic of typicality ALC + TR, based on the notion of rational closure, by inclusions p :: T(C) v D (“we have probability p that typical Cs are Ds”), coming from the distributed semantics of probabilistic Description Logics. Additionally, it embeds a set of cognitive heuristics for concept (...) combination. We show that the complexity of reasoning in our logic is EXPTIME-complete as in ALC. (shrink)

It is argued that complexity is not attributable directly to systems or processes but rather to the descriptions of their `best' models, to reflect their difficulty. Thus it is relative to the modelling language and type of difficulty. This approach to complexity is situated in a model of modelling. Such an approach makes sense of a number of aspects of scientific modelling: complexity is not situated between order and disorder; noise can be explicated by approaches to excess (...) modelling error; and simplicity is not truth indicative but a useful heuristic when models are produced by a being with a tendency to elaborate in the face of error. (shrink)

I present evidence for a systematic complexity-coherence tradeoff in cognition. I show how feasible strategies for increasing cognitive complexity along three dimensions come at the expense of a heightened vulnerability to incoherence. I discuss two normative implications of the complexity-coherence tradeoff: a novel challenge to coherence-based theories of bounded rationality and a new strategy for vindicating the rationality of seemingly irrational cognitions. I also discuss how the complexity-coherence tradeoff sharpens recent descriptive challenges to dual process (...) theories of cognition. (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)

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)

We prove two sets of results concerning computational complexity classes. First, we propose a new variation of the random oracle hypothesis, originally posed by Bennett and Gill after they showed that relative to a randomly chosen oracle, with probability 1. Their original hypothesis was quickly disproven in several ways, most famously in 1992 with the result that, in spite of the classes being shown unequal with probability 1. Here we propose a variation of what it means to be “large” (...) using the Ellentuck topology. In this new context, we demonstrate that the set of oracles separating and is not small, and obtain similar results for the separation of from along with the separation of from. We also show that the set of oracles equating with is large in this new sense. We demonstrate that this version of the hypothesis provides a sufficient condition for unrelativized relationships, at least in the cases considered here. Second, we examine the descriptive complexity of the classes of oracles providing the separations for these various classes, and determine their exact placement in the Borel hierarchy. (shrink)

The two-state-vector formalism presents a time-symmetric approach to the standard quantum mechanics, with particular importance in the description of experiments having pre- and post-selected ensembles. In this paper, using the correspondence limit of the quantum harmonic oscillator in the two-state-vector formalism, we produce harmonic oscillators that possess a classical behavior while having a complex-valued position and momentum. This allows us to discover novel effects that cannot be achieved otherwise. The proposed classical behavior does not describe the classical physics in the (...) usual sense since this behavior is subjected to the feature that only after the final measurement is performed, as a boundary condition, the complex-valued classical effects occur between the initial and the final boundary conditions. This classical behavior breaks down if one does not follow the decided boundary conditions during the experiment, since otherwise, one will contradict the impossibility of retrocausality. (shrink)

In this article an epistemological framework is proposed in order to integrate the emergentist thought with systemic studies on biological autonomy, which are focused on the role of organization. Particular attention will be paid to the role of the observer’s activity, especially: (a) the different operations he performs in order to identify the pertinent elements at each descriptive level, and (b) the relationships between the different models he builds from them. According to the approach sustained here, organization will be (...) considered as the result of a specific operation of identification of the relational properties of the functional components of a system, which do not necessarily coincide with the intrinsic properties of its structural constituents. Also, an epistemological notion of emergence—that of “complex emergence”—will be introduced, which can be defined as the insufficiency, even in principle, of a single descriptive modality to provide a complete description of certain classes of systems. This integrative framework will allow us to deal with two issues in biological and emergentist studies: (1) distinguishing the autonomy proper of living systems from some physical processes like those of structural stability and pattern generation, and (2) reconsidering the notion of downward causation not as a direct or indirect influence of the whole on its parts, but instead as an epistemological problem of interaction between descriptive domains in which the concept of organization proposed and the observational operations related to it play a crucial role. (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)

The essential structure of proofs is proposed as the basis for a measure of complexity of formulas in FOL. The motivating idea was the recognition that distinct theorems can have the same derivation modulo some non essential details. Hence the difficulty in proving them is identical and so their complexity should be the same. We propose a notion of complexity of formulas capturing this property. With this purpose, we introduce the notions of schema calculus, schema derivation and (...) description complexity of a schema formula. Based on these concepts we prove general robustness results that relate the complexity of introducing a logical constructor with the complexity of the component schema formulas as well as the complexity of a schema formula across different schema calculi. (shrink)

Michael Devitt claims that the predicative material that constitutes complex referential expressions makes a semantic contribution to the proposition expressed. He thus deviates from direct referentialism, according to which every referential expression -either simple or complex- contributes just with an object to the proposition expressed, leaving the predicative material out of the semantic content. However, when dealing with misdescriptions, Devitt has suggested a pragmatic way out: the audience can understand what the speaker is referring to even if the object does (...) not fall under the corresponding description. From my perspective, this proposal questions the semantic validity of the predicative material, together with Devitt's original claim. In this paper, I propose a way to solve the problem posed by misdescriptions that appeals to the idea of epistemically relativized properties, according to which the properties ascribed to the object -by means of the predicative material- correspond to the way the speaker thinks of it and not to the way the object really is. Michael Devitt sostiene que el material predicativo que constituye las expresiones referenciales complejas hace un aporte semántico a la proposición expresada, alejándose así del referencialismo directo, para el cual toda expresión referencial -sea ésta simple o compleja- contribuye sólo con un objeto singular a la proposición expresada. Sin embargo, al enfrentarse al problema de las descripciones fallidas, Devitt ofrece una salida pragmática: el oyente comprende a qué se refiere el hablante aun cuando el objeto referido no caiga bajo la descripción utilizada. Esto pone en cuestión la validez semántica del material predicativo, desestimando la postura original de Devitt. En el trabajo propongo una solución a este problema, apelando a la idea de propiedades epistémicamente relativizadas, de acuerdo con la cual lo que se predica del objeto por medio del material predicativo corresponde a las creencias del hablante, y no a lo que el objeto realmente es. (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)

The Kolmogorov complexity of a finite binary string is the length of the shortest description of the string. This gives rise to some ‘standard’ lowness notions for reals: A isK-trivial if its initial segments have the lowest possible complexity and A is low forKif using A as an oracle does not decrease the complexity of strings by more than a constant factor. We weaken these notions by requiring the defining inequalities to hold only up to all${\rm{\Delta }}_2^0$orders, (...) and call the new notions${\rm{\Delta }}_2^0$-bounded K-trivialand${\rm{\Delta }}_2^0$-bounded low for K. Several of the ‘nice’ properties ofK-triviality are lost with this weakening. For instance, the new weaker definitions both give uncountable set of reals. In this paper we show that the weaker definitions are no longer equivalent, and that the${\rm{\Delta }}_2^0$-boundedK-trivials are cofinal in the Turing degrees. We then compare them to other previously studied weakenings, namelyinfinitely-often K-trivialityandweak lowness for K. We show that${\rm{\Delta }}_2^0$-boundedK-trivial implies infinitely-oftenK-trivial, but no implication holds between${\rm{\Delta }}_2^0$-bounded low forKand weakly low forK. (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. (...) class='Hi'>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)

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)

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)

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)