Recent years have seen an increasing interest in the study of continuous-time computational models. However, not so much has been done with respect to setting up a complexity theoretic framework for such models. The present paper intends to go a step into this direction. We consider problems over the real numbers which we try to relate to Lyapunov theory for dynamical systems: The global minimizers of particular energy functions are supposed to give solutions of the problem. (...) The structure of such energy functions leads to the introduction of problem classes U and NU; for the systems we are considering they parallel the classical complexity classes P and NP. We then introduce a notion of reducibility among problems and show existence of complete problems for NU and for PU, a polynomial hierarchy of continuous-time problems.For previous work on the computational capabilities of continuous-time systems see the surveys by Cris Moore [9] and by Pekka Orponen [10]. Our paper presents a step into the direction of creating a general framework for a complexity theory of continuous-time systems as outlined in [10]. It is closely related to work done by A. Ben-Hur, H. Siegelmann, and S. Fishman [12, 11]. (shrink)

In [1] Todorov has shown by means of axiomatic set theory that there exists a nonstandard function Δ: *ℝn → * ℂ such that for all continuous functions φ: ℝn → ℂ, equation image.Here *ℝ and *ℂ are the set of the nonstandard real numbers and the set of the nonstandard complex numbers, respectively, and *φ: *ℝn → *ℂ is the nonstandard extension of φ In the present note we want to prove an analogous theorem by predicative (...) means only. (shrink)

A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship (...) between these two complexity measures is further studied and compared with the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. (shrink)

The ontology of Bohmian mechanics includes both the universal wave function and particles. Proposals for understanding the physical significance of the wave function in this theory have included the idea of regarding it as a physically-real field in its 3N-dimensional space, as well as the idea of regarding it as a law of nature. Here we introduce and explore a third possibility in which the configuration space wave function is simply eliminated—replaced by a set of single-particle pilot-wave fields (...) living in ordinary physical space. Such a re-formulation of the Bohmian pilot-wave theory can exactly reproduce the statistical predictions of ordinary quantum theory. But this comes at the rather high ontological price of introducing an infinite network of interacting potential fields which influence the particles’ motion through the pilot-wave fields. We thus introduce an alternative approach which aims at achieving empirical adequacy with a more modest ontological complexity, and provide some preliminary evidence for optimism regarding the program of trying to replace the configuration space wave function with a set of fields in ordinary physical space. (shrink)

The basic concept of Type-2 Theory of Effectivity to define computability on topological spaces or limit spaces are representations, i. e. surjection functions from the Baire space onto X. Representations having the topological property of admissibility are known to provide a reasonable computability theory. In this article, we investigate several additional properties of representations which guarantee that such representations induce a reasonable Type-2 Complexity Theory on the represented spaces. For each of these properties, we give (...) a nice characterization of the class of spaces that are equipped with a representation having the respective property. (shrink)

Hager and Beckett assert that a ‘characteristic feature of … assorted co-present groups is that their processes and outputs are marked by the full gamut of human experiences involved in their functioning’. My paper endorses and further develops this claim. I begin by expanding on their emphasis upon the priority of relations in terms of Dewey and Bentley’s transactionalism and Buddhist dependent co-origination and emptiness. Next, I emphasize the importance of embodied perspectives in acquiring meaning and transforming the world. Here, (...) too, we will find surprising Buddhist connections. Finally, I examine the primacy of practice: how we acquire our minds and selves by participating in shared social practices. This stance is shared by philosophers as diverse as Heidegger, Wittgenstein, and Dewey. (shrink)

Adopting a materialist approach to the mind has far reaching implications for many presuppositions regarding the properties of the brain, including those that have traditionally been consigned to “the mental” aspect of human being. One such presupposition is the conception of the disembodied self. In this article we aim to account for the self as a material entity, in that it is wholly the result of the physiological functioning of the embodied brain. Furthermore, we attempt to account for the structure (...) of the self by invoking the logic of the narrative. While our conception of narrative selfhood incorporates the work of both Freud and Dennett, we offer a critique of these two theorists and then proceed to amend their theories by means of complexity theory. We argue that the self can be characterised as a complex system, which allows us to account for the structure of the wholly material self. (shrink)

In this paper, we simulate the estimation of motion through an interframe difference detection function model and investigate the spatial-temporal context information correlation filtering target tracking algorithm, which is complex and computationally intensive. The basic theory of spatiotemporal context information and correlation filtering is studied to construct a fast target tracking method. The different computational schemes are designed for the flow of multiframe target detection from background removal to noise reduction, to single-frame detection, and finally to multiframe detection, respectively. (...) This enables the ground-based telescope to effectively detect spatial targets in dense stellar backgrounds in both modes. The method is validated by simulations and experiments and can meet the requirements of real projects. The interframe bit attitude estimation is optimized by using the beam-parity method to reduce the interframe estimation noise; a global optimization strategy based on the bit attitude map is used in the back end to reduce the system computation amount and make the global bit attitude estimation more accurate; a loop detection based on the word pocket model is added to the system to reduce the cumulative error. (shrink)

Given any collection F of computable functions over the reals, we show that there exists an algorithm that, given any sentence A containing only bounded quantifiers and functions in F, and any positive rational number delta, decides either “A is true”, or “a delta-strengthening of A is false”. Moreover, if F can be computed in complexity class C, then under mild assumptions, this “delta-decision problem” for bounded Sigma k-sentences resides in Sigma k. The results stand in sharp (...) contrast to the well-known undecidability of the general first-order theories with these functions, and serve as a theoretical basis for the use of numerical methods in decision procedures for formulas over the reals. (shrink)

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

Flight delay is one of the most challenging threats to operation of air transportation network system. Complex network was introduced into research studies on flight delays due to its low complexity, high flexibility in model building, and accurate explanation about real world. We surveyed recent progress about flight delay which makes extensive use of complex network theory in this paper. We scanned analyses on static network and temporal evolution, together with identification about topologically important nodes/edges. And, we (...) made a clarification about relations among robustness, vulnerability, and resilience in air transportation networks. Then, we investigated studies on causal relations, propagation modellings, and best spreaders identifications in flight delay. Ultimately, future improvements are summarized in fourfold. Under Complex Network, flight operation relevant subsystems or sublayers are discarded by the majority of available network models. Hierarchical modelling approaches may be able to improve this and provide more capable network models for flight delay. Traffic information is the key to narrow the gap between topology and functionality in current situations. Flight schedule and flight plan could be employed to detect flight delay causalities and model flight delay propagations more accurately. Real flight data may be utilized to validate and revise the detection and prediction models. It is of great importance to explore how to predict flight delay propagations and identify best spreaders at a low cost of calculation complexity. This may be achieved by analyzing flight delay in frequency domain instead of time domain. Summation of most critical nodes/edges may not be the most crucial group to network resilience or flight delay propagations. Effective algorithm for most influential sequence is to be developed. (shrink)

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

A mixture preorder is a preorder on a mixture space (such as a convex set) that is compatible with the mixing operation. In decision theoretic terms, it satisfies the central expected utility axiom of strong independence. We consider when a mixture preorder has a multi-representation that consists of real-valued, mixture-preserving functions. If it does, it must satisfy the mixture continuity axiom of Herstein and Milnor (1953). Mixture continuity is sufficient for a mixture-preserving multi-representation when the dimension of the (...) mixture space is countable, but not when it is uncountable. Our strongest positive result is that mixture continuity is sufficient in conjunction with a novel axiom we call countable domination, which constrains the order complexity of the mixture preorder in terms of its Archimedean structure. We also consider what happens when the mixture space is given its natural weak topology. Continuity (having closed upper and lower sets) and closedness (having a closed graph) are stronger than mixture continuity. We show that continuity is necessary but not sufficient for a mixture preorder to have a mixture-preserving multi-representation. Closedness is also necessary; we leave it as an open question whether it is sufficient. We end with results concerning the existence of mixture-preserving multi-representations that consist entirely of strictly increasing functions, and a uniqueness result. (shrink)

Teaching bioethics in the new millennium requires its practitioners to confront a wide area of methodological alternatives. This essay chronicles the author's journey from the principlism of Beauchamp and Childress, through narrative and postmodern bioethics, to a complex feminist critique of postmodern bioethics that emphasizes functional human capabilities and the creation of structures that can facilitate free discussion of those capabilities and how best to realize them. Teaching bioethics concerns not only the acknowledgement of differences but also reminding ourselves of (...) our samenesses. Sustained Habermasian democratic conversations might help us to escape the narrow confines of a postmodern bioethics of moral strangers for a richer world of moral friends. (shrink)

Relations between discrete and continuous complexity models are considered. The present paper is devoted to combine both models. In particular we analyze the 3-Satisfiability problem. The existence of fast decision procedures for this problem over the reals is examined based on certain conditions on the discrete setting. Moreover we study the behaviour of exponential time computations over the reals depending on the real complexity of 3-Satisfiability. This will be done using tools from complexity theory over (...) the integers. (shrink)

A mixture preorder is a preorder on a mixture space (such as a convex set) that is compatible with the mixing operation. In decision theoretic terms, it satisfies the central expected utility axiom of strong independence. We consider when a mixture preorder has a multi-representation that consists of real-valued, mixture-preserving functions. If it does, it must satisfy the mixture continuity axiom of Herstein and Milnor (1953). Mixture continuity is sufficient for a mixture-preserving multi-representation when the dimension of the (...) mixture space is countable, but not when it is uncountable. Our strongest positive result is that mixture continuity is sufficient in conjunction with a novel axiom we call countable domination, which constrains the order complexity of the mixture preorder in terms of its Archimedean structure. We also consider what happens when the mixture space is given its natural weak topology. Continuity (having closed upper and lower sets) and closedness (having a closed graph) are stronger than mixture continuity. We show that continuity is necessary but not sufficient for a mixture preorder to have a mixture-preserving multi-representation. Closedness is also necessary; we leave it as an open question whether it is sufficient. We end with results concerning the existence of mixture-preserving multi-representations that consist entirely of strictly increasing functions, and a uniqueness result. (shrink)

The extreme length of chromosomal DNA requires organizing mechanisms to both promote functional genetic interactions and ensure faithful chromosome segregation when cells divide. Microscopy and genome‐wide contact frequency analyses indicate that intra‐chromosomal looping of DNA is a primary pathway of chromosomal organization during all stages of the cell cycle. DNA loop extrusion has emerged as a unifying model for how chromosome loops are formed in cis in different genomic contexts and cell cycle stages. The highly conserved family of SMC complexes (...) have been found to be required for DNA cis‐looping and have been suggested to be the enzymatic core of loop extruding machines. Here, the current body of evidence available for the in vivo and in vitro action of SMC complexes is discussed and compared to the predictions made by the loop extrusion model. How SMC complexes may differentially act on chromatin to generate DNA loops and how they could work to generate the dynamic and functionally appropriate organization of DNA in cells is explored. -/- . (shrink)

A new theory for basic function in the nervous system has recently been proposed (Dempsher, J., 1979a, 1979b; 1980, 1981). The major basic themes of the new theory are as follows: (1) There are two fundamental units of structure and function, the fibre or conducting mechanism, and the neurocentre, where nervous system function as we know it takes place. (2) The nerve impulse is regarded as a mathematical event. The mathematics is the result of a prescribed fusion of (...) energy and matter. (3) Nervous system function everywhere in the nervous system is mathematical. In the fibre, the prescribed fusion of energy and matter results in a number. In the neurocentre, the prescribed fusion of energy and matter results in a mathematical function. Basic function in the nervous system everywhere requires a transformation of a nerve impulse in the fibre into a nerve impulse in the neurocentre with opposing properties: The nerve impulse in the fibre is confined to the fibre; cannot sum with another nerve impulse; can travel long distances with constant form and velocity; curvature in space and time are not significant features; and it is regarded as a number. On the other hand, the nerve impulse in the neurocentre is confined to the neurocentre; can sum with other nerve impulses; cannot travel long distances - even in a very short distance, it changes form; curvature in space and time is a very significant feature; and it is regarded as a mathematical function.The approach to determine how one form of the nerve impulse is transformed into the other at the input region is based on two of the differences listed above: (1) The nerve impulse in the fibre cannot sum with another nerve impulse in the fibre, whereas in the neurocentre, several nerve impulses sum to form a larger nerve impulse. (2) The nerve impulse in the fibre is regarded as a number, in the neurocentre, it is regarded as a mathematical function. The commonality of (1) and (2) is that the properties defining the nerve impulse in the fibre are associated with the property ofdiscreteness, whereas, the properties defining the nerve impulse in the neurocentre are associated with the property ofcontinuousness. Thus, the basic theme of unification of function at the input region of the neurocentre is the transformation of a phenomenon with the property of discreteness into a phenomenon with the property of continuousness. The solution to this transformation is approached from two directions:biologic andmathematical. In the biologic approach, the unit element of the nerve impulse in the fibre terminations (as.u. as a wave of energy, a spike in the classical theory) fuses with a. calcium-binding protein causing the release of Ca++. The calcium ions then combine with another protein. Associated with the second reaction is a conformational change in the Ca++-protein complex and the unit element in the neurocentre, bs.u., is emitted. Individual bs.u. then fuse with acetylcholine; summation occurs andwave b is emitted. In the mathematical approach, the nerve impulse as a number, is partitioned into two numbers with a precise rule relating these two numbers. One possibility suggested is that the number can be regarded as the value of a trigonometric function. This value then gives rise to an angle with sides related in a ratio or proportionality fashion — a relationship with the property of continuousness, as contrasted with that of a single number, discreteness. Both biologic and mathematical approaches are united so as to suggest that the mathematical (trigonometric) function arose as the result of a fusion of energy (as.u. as a wave of energy) and the calcium-binding protein as matter; following this reaction, bs.u., with opposing properties, is emitted. (shrink)

The reliability of previous findings on two crucial aspects of counterfactual thinking, namely the content of counterfactual modifications and their impact on future performance, has been questioned for the frequent use of tasks characterised by simple causal domains, that restrict participants’ possibility to consider a broad range of modifications. To overcome this limitation, we utilised a new experimental task featuring a complex causal domain to investigate such key aspects. The results indicated that participants tend to generate counterfactuals about elements outside (...) their control, especially when presented with a challenging version of the task (Study 1a) and, to a lesser extent, when they receive negative feedback on their performance (Study 1b). Moreover, despite occasional implementations of actions mentioned in controllable counterfactuals, being engaged in counterfactual thinking did not lead to subsequent performance improvements (Study 2). The implications of these findings for the debate on the function of counterfactual thinking are discussed. (shrink)

A notion of resource‐bounded Baire category is developed for the classPC[0,1]of all polynomial‐time computable real‐valued functions on the unit interval. The meager subsets ofPC[0,1]are characterized in terms of resource‐bounded Banach‐Mazur games. This characterization is used to prove that, in the sense of Baire category, almost every function inPC[0,1]is nowhere differentiable. This is a complexity‐theoretic extension of the analogous classical result that Banach proved for the classC[0, 1] in 1931. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim).

In lieu of an abstract, here is a brief excerpt of the content:Philosophy and Literature 25.2 (2001) 233-250 [Access article in PDF] Narrative Theory and Function: Why Evolution Matters Michelle Scalise Sugiyama I It may seem a strange proposition that the study of human evolution is integral to the study of literature, yet that is exactly what this paper proposes. The reasons for this are twofold. Firstly, the practice of storytelling is ancient, pre-dating not only the advent of writing, (...) but of agriculture and permanent settlement as well. Secondly, narrative is ultimately a product of the mind, which in turn is the product of a long history of evolution by natural selection. Thus, an understanding of why and how humans create and consume narrative requires an understanding of (1) features of ancestral environments and (2) features of the mind that made the emergence of this phenomenon possible.There can be little doubt that narrative emerged in human prehistory. Language, an obvious prerequisite for storytelling, is likely to have emerged by at least 50,000 and possibly 250,000 years ago, depending upon whether one places one's trust in archaeological or anatomical evidence. 1 The most reasonable estimate is offered by Geoffrey Miller, who points out that, given its universality, the language faculty must have emerged by the time ancestral Homo sapiens began migrating out of Africa approximately 100,000 years ago. 2 Although the oldest known written narrative (The Epic of Gilgamesh) dates back only 5,000 years, the written literary traditions of many ancient cultures are known to be rooted in longstanding oral traditions. 3 The fact that many modern foraging peoples have rich and complex oral traditions further suggests that the emergence of narrative is not linked to the development of agriculture 10,000 years ago. Moreover, other forms of symbolic expression, such as the cave paintings, Venus figurines, and engraved bone [End Page 233] and antler that have been found at various sites throughout Europe, date back approximately 30,000 years, and rock paintings in Australia may date back even farther. 4 Since humans were physiologically capable of speech long before they began producing these artifacts, storytelling is likely to be at least as ancient as these other representational forms. Indeed, one scholar situates the "dawn of the oral tradition" within this period (Pfeiffer, p. 189). Given, then, that modern humans (Homo sapiens sapiens) have been in existence for approximately 100,000 years 5 and are the only hominid species or subspecies known for certain to exhibit storytelling behavior, we can safely say that oral narrative is a product of our hunting-and-gathering past, likely to have emerged between 30,000 and 100,000 years ago.The universality of narrative is further testimony to its being an ancient cognitive phenomenon. Literate or not, all known cultures, past and present, practice storytelling. 6 Moreover, all normally developing humans acquire the ability to process and generate stories: studies of Western children indicate that the ability to tell stories emerges spontaneously between the ages of two-and-a-half and three, and children as young as thirty months can distinguish between narrative and non-narrative uses of language. 7 In contrast to reading, writing, and arithmetic, no special education is required for narrative competence to develop, nor is there any evidence that oral literacy is acquired through contact with other cultures; although subject matter is often exchanged between groups, the practice of storytelling itself arises independently among even the most isolated peoples. Nor does any type of culture have a monopoly on narrative sophistication: the stories of hunter-horticulturalist societies are no less observant, insightful, or artful than those of agrarian or industrial societies.As with language, narrative takes the same basic form across cultures, which David Bordwell and Kristin Thompson define as "a chain of events in cause-effect relationship occurring in time." Given the preponderance of human agents in narrative, most narrative theorists would probably modify this barebones description to include character (usually understood to have a human psychology), goal-oriented action, and resolution. Frank Kermode, for example, defines the "proprieties" of narrative as "connexity, closure, and character," and John... (shrink)

The purpose of this paper is modelling and controlling the spread of COVID-19 disease in Morocco. A nonlinear mathematical model with two subclasses of infectious individuals is proposed. The population is divided into five classes, namely, susceptible, exposed, undiagnosed infectious, diagnosed patients, and removed individuals. To reflect the real dynamic of the COVID-19 transmission in Morocco, the real reported data are used for estimating model parameters. Two controls representing screening effort and limited treatment are considered. Based on viability (...) theory and set-valued analysis, a Lyapunov function is constructed such that both exposed and infected populations are decreased to zero asymptotically. The corresponding controls are derived via a continuous selection of adequately designed feedback map. Numerical simulations are presented with three scenarios. Our results show that when only one control is to be applied, screening is the most effective in decreasing the number of people in the three infected compartments, whereas combining both controls is found to be highly effective and leads to a significant improvement in the epidemiological situation of Morocco. To the best of our knowledge, this work is the first one that applies the set-valued approach to a controlled COVID-19 model which agrees with the observed cases in Morocco. (shrink)

In this paper I suggest that several problems in the study of emotion depend on a lack of adequate analytical tools, in particular on the tendency of viewing the organism as a modular and hierarchical system whose activity is mainly constituted by strictly sequential causal events. I argue that theories and models based on this view are inadequate to account for the complex reciprocal influences of the many ingredients that constitute emotions. Cognitive processes, feelings and bodily states are so subtly (...) intertwined that it is not possible to determine which one "comes first" in a causal chain. The dynamical systems approach in cognitive science, I suggest, provides a more appropriate framework for the study of emotion. In particular, the notion of circular causation and collective action help depict the organism as a self-organising system in which emotion emerges as a function of its global activity. Among others, this dynamical perspective allows revising the popular notion of appraisal in a way that can dissolve some of the questions that have taunted emotion theorists thus far. (shrink)

Function refers to a broad family of concepts of varying abstractness and range of application, from a many-one mathematical relation of great generality to, for example, highly specialized roles of designed elements in complex machines such as degaussing in a television set, or contributory processes to control mechanisms in complex metabolic pathways, such as the inhibitory function of the appropriate part of the lac-operon on the production of lactase through its action on the genome in the absence of lactose. We (...) would like a language broad enough, neutral enough, but yet powerful enough to cover all such cases, and at the same time to give a framework form explanation both of the family resemblances and differences. General logic and mathematics are too abstract, but more importantly, too broad, whereas other discourses of function, such as the biological and teleological contexts, are too narrow. Information is especially suited since it is mathematically grounded, but also has a wellknown physical interpretation through the Schr dinger/Brillouin Negentropy Principle of Information, and an engineering or design interpretation through Shannon's communication theory. My main focus will be on the functions of autonomous anticipatory systems, but I will try to demonstrate both the connections between this notion of function and the others, especially to dynamical systems with a physical interpretation on the one side and intentional systems on the other. The former are based in concepts like force, energy and work, while the latter involve notions like representation, control and purpose, traditionally, at least in Modern times, on opposite sides of the Cartesian divide. In principle, information can be reduced to energy, but it has the advantage of being more flexible, and easier to apply to higher level phenomena. (shrink)

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). (...) Dr Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (shrink)

The class of recursive functions over the reals, denoted by , was introduced by Cristopher Moore in his seminal paper written in 1995. Since then many subsequent investigations brought new results: the class was put in relation with the class of functions generated by the General Purpose Analogue Computer of Claude Shannon; classical digital computation was embedded in several ways into the new model of computation; restrictions of were proved to represent different classes of recursive functions, e.g., (...) recursive, primitive recursive and elementary functions, and structures such as the Ritchie and the Grzergorczyk hierarchies.The class of real recursive functions was then stratified in a natural way, and and the analytic hierarchy were recently recognised as two faces of the same mathematical concept.In this new article, we bring a strong foundational support to the Real Recursive Function Theory, rooted in Mathematical Analysis, in a way that the reader can easily recognise both its intrinsic mathematical beauty and its extreme simplicity. The new paradigm is now robust and smooth enough to be taught. To achieve such a result some concepts had to change and some new results were added. (shrink)

Leech et al. present a connectionist algorithm as a model of (the development) of analogizing, but they do not specify the algorithm's associated computational-level theory, nor its computational complexity. We argue that doing so may be essential for connectionist cognitive models to have full explanatory power and transparency, as well as for assessing their scalability to real-world input domains.

This uncommonly fine textbook of the modern theory of functions of a real variable is particularly well-suited for mathematically mature students in the fields of philosophy and foundations of mathematics, philosophy of physics, probability theory, and statistics. Those who wish to achieve first-hand acquaintance with the quantum theory will also need to have a grasp of the material presented in this book. The first chapter presents a capsule survey of topics in abstract set theory (...) and algebra, including a discussion of relations, functions, the axiom of choice, and the well-ordering theorem, and leading up to the construction of the fields of real and complex numbers. The second chapter is an introduction to topology and spaces of topological functions. The approach is set-theoretical. Chapter three deals with the theory of the Lebesgue integral and measure theory. This chapter is quite comprehensive, rigorous and embellished with many exercises for the student. Subsequent sections include the theories of function spaces, Banach spaces, abstract Hilbert spaces, and differentiation. This is clearly one of the more worthwhile texts in its field.—H. P. K. (shrink)

A case is made for supposing that the total probability accounted for in a decision analysis is less than unity. This is done by constructing a measure on the set of all codes for computable functions in such a way that the measure of every effectively accountable subset is bounded by a number <1. The consistency of these measures with the Savage axioms for rational preference is established. Implications for applied decision theory are outlined.

1. One theory or many? In 2004 a very interesting and readable article by Lenore Blum, entitled “Computing over the reals: Where Turing meets Newton,” appeared in the Notices of the American Mathematical Society. It explained a basic model of computation over the reals due to Blum, Michael Shub and Steve Smale (1989), subsequently exposited at length in their influential book, Complexity and Real Computation (1997), coauthored with Felipe Cucker. The ‘Turing’ in the title of Blum’s article (...) refers of course to Alan Turing, famous for his explication of the notion of mechanical computation on discrete data such as the integers. The ‘Newton’ there has to do to with the well known numerical method due to Isaac Newton for approximating the zeros of continuous functions under suitable conditions that is taken to be a paradigm of scientific computing. Finally, the meaning of “Turing meets Newton” in the title of Blum’s article has another, more particular aspect: in connection with the problem of controlling errors in the numerical solution of linear equations and inversion of matrices,Turing (1948) defined a notion of condition for the relation of changes in the output of a computation due to small changes in the input that is analogous to Newton’s definition of the derivative. The thrust of Blum’s 2004 article was that the BSS model of computation on the reals is the appropriate foundation for scientific computing in general. By way of response, two years later another very interesting and equally readable article appeared in the Notices, this time by Mark Braverman and Stephen Cook (2006) entitled “Computing over the reals: Foundations for scientific computing,” in which the authors argued that the requisite foundation is provided by a quite different “bit computation” model, that is in fact prima facie incompatible with the BSS model. The bit computation model goes back to ideas due to Stefan Banach and Stanislaw Mazur in the latter part of the 1930s, but the first publication was not made until Mazur (1963).. (shrink)

In order to establish patterns of materialization of the beliefs we are going to consider that these have defined mathematical structures. It will allow us to understand better processes of the textual, architectonic, normative, educative, etc., materialization of an ideology. The materialization is the conversion by means of certain mathematical correspondences, of an abstract set whose elements are beliefs or ideas, in an impure set whose elements are material or energetic. Text is a materialization of ideology and it is any (...) representation of the Reality represented by symbolic means. In all text T we can observe diverse topological structures: Metric Textual Space, Textual Topology and a Textual Lattice. (shrink)

Many studies about organizational experiences and theories converge today in the idea that the economic factor, most competitive now in the production of value, is the de-materialization of the economical and organizational processes. Immaterial factors (like knowledge, services, information, relationships, virtual transactions, etc.) are the competitive and crucial innovations for future competition and, at the same time, the most important criteria to rethinking and understanding the future organization. If this is true, we can realize that every person in organizations, every (...) personal history in organizations, or better the evolutionary uniqueness of every person in organizations, is the real depositary and bearer of this de-materialization. (shrink)

Within Bishop Set Theory, a reconstruction of Bishop’s theory of sets, we study the so-called completely separated sets, that is, sets equipped with a positive notion of an inequality, induced by a given set of real-valued functions. We introduce the notion of a global family of completely separated sets over an index-completely separated set, and we describe its Sigma- and Pi-set. The free completely separated set on a given set is also presented. Purely set-theoretic versions of (...) the classical Stone–Čech theorem and the Tychonoff embedding theorem for completely regular spaces are given, replacing topological spaces with function spaces and completely regular spaces with completely separated sets. (shrink)

This article responds to Philip Galanter’s essay ‘Complexism and the role of evolutionary art’ to explore complexism in relation to postmodern and generative architecture. Galanter poses complexism as a new theoretical mode that can supercede the divides of modernism/postmodernism and the two cultures (sciences/arts and humanities). The author, rather than promoting complexism, examines it as if from afar, positioning it as our most recent scientifically informed paradigm. She asserts that, in many ways, complexism functions as an ideology permeating realms (...) of cultural and intellectual production. Examples range from contemporary advertising to economic theory, political and economic protests such as the Occupy Movement, to the rhetorical and computational strategies in generative architecture. The author demonstrates that postmodernism in architecture was always theoretically tied to complex systems theory. Further, she connects the vagaries of application and extrapolation of complexity theory, across realms of current-day cultural production, to the definitional vagueness of some of complexism’s key terms (system, selforganization, emergence). Finally, she argues that two collateral effects of complexism are: (1) the promotion of dependence on environmentally damaging computational devices and (2) the socio-economic and environmental expulsions occurring in the global economy, as recently argued by sociologist Saskia Sassen. (shrink)

The interests of synthetic biologists may appear to differ greatly from those of evolutionary biologists. The engineering of organisms must be distinguished from the tinkering action of evolution; the ambition of synthetic biologists is to overcome the limits of natural evolution. But the relations between synthetic biology and evolutionary biology are more complex than this abrupt opposition: Synthetic biology may play an important role in the increasing interactions between functional and evolutionary biology. In practice, synthetic biologists have learnt to submit (...) the proteins and modules they construct to a Darwinian process of selection that optimizes their functioning. More importantly, synthetic biology can provide evolutionary biologists with decisive tools to test the scenarios they have elaborated by resurrecting some of the postulated intermediates in the evolutionary process, characterizing their properties, and experimentally testing the genetic changes supposed to be the source of new morphologies and functions. This synthetic, experimental evolution will renew and clarify many debates in evolutionary biology: It will lead to the explosion of some vague concepts as constraints, parallel evolution, and convergence, and replace them with precise mechanistic descriptions. In this way, synthetic biology resurrects the old philosophical debate about the relations between the real and the possible. (shrink)

It is generally agreed that organisms are Complex Adaptive Systems. Since the rise of Cybernetics in the middle of the last century ideas from information theory and control theory have been applied to the adaptations of biological organisms in order to explain how they work. This does not, however, explain functionality, which is widely but not universally attributed to biological systems. There are two approaches to functionality, one based on etiology (what a trait was selected for), and the (...) other based in autonomy. I argue that the etiological approach, as understood in terms of control theory, suffers from a problem of symmetry, by which function can equally well be placed in the environment as in the organism. Focusing on the autonomy view, I note that it can be understood to some degree in terms of control theory in its version called second order cybernetics. I present an approach to second order cybernetics that seems plausible for organisms with limited computational power, due to Hooker, Penfold and Evans. They hold that this approach gives something like concepts, certainly abstractions from specific situations, a trait required for functionality in its system adaptive form (i.e., control of the system by itself). Using this cue, I argue that biosemiotics provides the methodology to incorporate these quasi concepts into an account of functionality. (shrink)

We investigate the Ramsey theory of continuous graph-structures on complete, separable metric spaces and apply the results to the problem of covering a plane by functions. Let the homogeneity number[Formula: see text] of a pair-coloring c:[X]2→2 be the number of c-homogeneous subsets of X needed to cover X. We isolate two continuous pair-colorings on the Cantor space 2ω, c min and c max, which satisfy [Formula: see text] and prove: Theorem. For every Polish space X and every continuous (...) pair-coloringc:[X]2→2with[Formula: see text], [Formula: see text] There is a model of set theory in which[Formula: see text]and[Formula: see text]. The consistency of [Formula: see text] and of [Formula: see text] follows from [20]. We prove that [Formula: see text] is equal to the covering number of 2 by graphs of Lipschitz functions and their reflections on the diagonal. An iteration of an optimal forcing notion associated to c min gives: Theorem. There is a model of set theory in which ℝ2 is coverable byℵ1graphs and reflections of graphs of continuous real functions; ℝ2 is not coverable byℵ1graphs and reflections of graphs of Lipschitz real functions. Figure 1.1 in the introduction summarizes the ZFC results in Part I of the paper. The independence results in Part II show that any two rows in Fig. 1.1 can be separated if one excludes [Formula: see text] from row. (shrink)

Physics and chemistry underlie the nature of all the world around us, including human brains. Consequently some suggest that in causal terms, physics is all there is. However, we live in an environment dominated by objects embodying the outcomes of intentional design (buildings, computers, teaspoons). The present day subject of physics has nothing to say about the intentionality resulting in existence of such objects, even though this intentionality is clearly causally effective. This paper examines the claim that the underlying physics (...) uniquely causally determines what happens, even though we cannot predict the outcome. It suggests that what occurs is the contextual emergence of complexity: the higher levels in the hierarchy of complexity have autonomous causal powers, functionally independent of lower level processes. This is possible because top-down causation takes place as well as bottom-up action, with higher level contexts determining the outcome of lower level functioning and even modifying the nature of lower level constituents. Stored information plays a key role, resulting in non-linear dynamics that is non-local in space and time. Brain functioning is causally affected by abstractions such as the value of money and the theory of the laser. These are realised as brain states in individuals, but are not equivalent to them. Consequently physics per se cannot causally determine the outcome of human creativity, rather it creates the possibility space allowing human intelligence to function autonomously. The challenge to physics is to develop a realistic description of causality in truly complex hierarchical structures, with top-down causation and memory effects allowing autonomous higher levels of order to emerge with genuine causal powers. (shrink)

An analysis of two heuristic strategies for the development of mechanistic models, illustrated with historical examples from the life sciences. In Discovering Complexity, William Bechtel and Robert Richardson examine two heuristics that guided the development of mechanistic models in the life sciences: decomposition and localization. Drawing on historical cases from disciplines including cell biology, cognitive neuroscience, and genetics, they identify a number of "choice points" that life scientists confront in developing mechanistic explanations and show how different choices result in (...) divergent explanatory models. Describing decomposition as the attempt to differentiate functional and structural components of a system and localization as the assignment of responsibility for specific functions to specific structures, Bechtel and Richardson examine the usefulness of these heuristics as well as their fallibility—the sometimes false assumption underlying them that nature is significantly decomposable and hierarchically organized. When Discovering Complexity was originally published in 1993, few philosophers of science perceived the centrality of seeking mechanisms to explain phenomena in biology, relying instead on the model of nomological explanation advanced by the logical positivists (a model Bechtel and Richardson found to be utterly inapplicable to the examples from the life sciences in their study). Since then, mechanism and mechanistic explanation have become widely discussed. In a substantive new introduction to this MIT Press edition of their book, Bechtel and Richardson examine both philosophical and scientific developments in research on mechanistic models since 1993. (shrink)

We study some representations of real numbers. We compare these representations, on the one hand from the viewpoint of recursive functionals, and of complexity on the other hand.The impossibility of obtaining some functions as recursive functionals is, in general, easy. This impossibility may often be explicited in terms of complexity: - existence of a sequence of low complexity whose image is not a recursive sequence, - existence of objects of low complexity but whose images (...) have arbitrarily high time- complexity .Moreover, some representations of real numbers that are equivalent from the viewpoint of recursive functionals, are very distinct from the viewpoint of complexity.We make a particular study of representations via continued fractions . We precise exactly what part of information available in the x's dfc is equivalent to the information available in its Dedekinds cut. We show that the sum of two reals whose dfcs are polynomial-time computable may be a real whose dfc has time complexity arbitrarily high.This work confirms that the unique representation of real numbers suitable for the ordinary calculus is via explicit Cauchy sequences of rationals.RésuméNous étudions différentes manières de présenter les nombres réels. Nous comparons ces présentations du point de vue des fonctionnelles récursives d'une part, et de celui des classes de complexité d'autre part.L'impossibilité d'obtenir certaines fonctions sous forme de fonctionnelles récursives est en général facile à établir. Cette impossiblité peut souvent être explicitée en termes de complexité: - il existe une suite de faible complexité dont l'image est une suite non récursive, - il existe des objets de faible complexité mais dont les images sont des objets de complexité arbitrairement grande .En outre, certaines présentations des réels équivalentes du point de vue des fonctionnelles récursives se distinguent nettement du point de vue de la complexité.Nous faisons une étude particulière concernant les développements en fraction continue . Nous précisions exactement quelle est la partie de l'information disponible dans le dfc d'un réel x qui équivaut à l'information disponible dans sa coupure de Dedekind. Nous montrons également que la somme de deux réels dont le dfc est calculable en temps polynomial peut être un réel dont le dfc est de complexité arbitrairement grande.Ce travail confirme que seule une présentation des réels via des suites de rationnels explicitement de Cauchy est adaptée aux calculs avec les réels. (shrink)

In complexity theory, both the brain and consciousness are understood as trophic systems—they consume metabolic energy when they function. Complex systems are dynamic and nonlinear and comprise diverse entities that are interdependent and interconnected in such a way that information is shared and that entities adapt to one another. Some natural complex systems are complex adaptive systems (CAS), which are sensitive to change in relation to their environments and are often chaotic. Consciousness and the neural systems mediating consciousness (...) may be modeled as CAS and, more specifically, as intelligent complex adaptive systems (ICAS), where intelligence means that a nervous system can solve problems successfully by intervening between sensory input and behavioral output. Evolution of any ICAS will result in emergent properties, particularly advanced brains. Two processes are involved in integrating experience and knowledge: the effort after meaning and the effort after truth. These efforts are mediated by the predominance given to direct experience presented to the brain's sensorium and modeling processes mediated by higher cognitive functions. Understanding consciousness as an ICAS has profound repercussions in how anthropology conceives of culture. (shrink)

The brains of higher mammals are extraordinary integrative devices. Signals from large numbers of functionally specialized groups of neurons distributed over many brain regions are integrated to generate a coherent, multimodal scene. Signals from the environment are integrated with ongoing, patterned neural activity that provides them with a meaningful context. We review recent advances in neurophysiology and neuroimaging that are beginning to reveal the neural mechanisms of integration. In addition, we discuss concepts and measures derived from information theory that (...) lend a theoretical basis to the notion of complexity as integration of information and suggest new experimental tests of these concepts. (shrink)

We propose a rudimentary formal framework for reasoning about recursion equations over inductively generated data. Our formalism admits all equational programs , and yet singles out none. While being simple, this framework has numerous extensions and applications. Here we lay out the basic concepts and definitions; show that the deductive power of our formalism is similar to that of Peano's Arithmetic; prove a strong normalization theorem; and exhibit a mapping from natural deduction derivations to an applied λ -calculus, à la (...) Curry–Howard, which provides a transparent proof of Gödel's result that the provably recursive functions of PA are definable by primitive recursion in finite types. Also of interest is the extent, uncommon among similar constructions, to which our mapping is oblivious to first order terms, including first order quantification and equality. Additional applications and extensions of the method will be presented in sequel papers. In particular, the methodology introduced here lends itself to systematic links between natural sub-formalisms and computational complexity classes. Since these sub-formalisms are largely transparent, allowing one to reason formally in the full system while leaving to automatic software tools the task of verifying that restrictions are complied with, the framework is particularly attractive for the development of Feasible Mathematics. (shrink)

This volume handles in various perspectives the concept of function and the nature of functional explanations, topics much discussed since two major and conflicting accounts have been raised by Larry Wright and Robert Cummins’s papers in the 1970s. Here, both Wright’s ”etiological theory of functions’ and Cummins’s ”systemic’ conception of functions are refined and elaborated in the light of current scientific practice, with papers showing how the ”etiological’ theory faces several objections and may in reply be (...) revisited, while its counterpart became ever more sophisticated, as researchers discovered fresh applications for it. Relying on a firm knowledge of the original positions and debates, this volume presents cutting-edge research evincing the complexities that today pertain in function theory in various sciences. Alongside original papers from authors central to the controversy, work by emerging researchers taking novel perspectives will add to the potential avenues to be followed in the future. Not only does the book adopt no a priori assumptions about the scope of functional explanations, it also incorporates material from several very different scientific domains, e.g. neurosciences, ecology, or technology. In general, functions are implemented in mechanisms; and functional explanations in biology have often an essential relation with natural selection. These two basic claims set the stage for this book’s coverage of investigations concerning both ”functional’ explanations, and the ”metaphysics’ of functions. It casts new light on these claims, by testing them through their confrontation with scientific developments in biology, psychology, and recent developments concerning the metaphysics of realization. Rather than debating a single theory of functions, this book presents the richness of philosophical issues raised by functional discourse throughout the various sciences.​ Content Level » Research Keywords » Causal role theory of functions - Determination of content - Ecosystem selection - Etiological theory of function - Evolutionary biology - Functional explanations - Historical concepts in biology - Larry Wright - Neurosciences - New mechanism - Selected effects functions - Systemic theory of functions - William Wimsatt Related subjects » Anthropology & Archaeology - Epistemology & Philosophy of Science - Evolutionary & Developmental Biology - Neuroscience - Philosophy TABLE OF CONTENTS Introduction.- Section I. Biological functions and functional explanations: genes, cells, organisms and ecosystems.- Part 1.A. Functions, organization and development in life sciences.- Chapter 1. William C. Wimsatt. Evolution and the Stability of Functional Architectures.- Chapter 2. Denis M. Walsh. Teleological Emergence: The Autonomy of Evo-Devo.- Chapter 3. Jean Gayon. Does oxygen have a function, or: where should the regress of biological functions stop?.- Part 1.B. Functional pluralism for biologists? Chapter 4. Frédéric Bouchard. How ecosystem evolution strengthens the case for functional pluralism.- Chapter 5. Robert N. Brandon. A general case for functional pluralism.- Chapter 6. Philippe Huneman. Weak realism in the etiological theory of functions.- Section 2. Section II. Psychology, philosophy of mind and technology: Functions in a man’s world.- Part 2.A. 2A. Metaphysics, function and philosophy of mind.- Chapter 7. Carl Craver. Functions and Mechanisms in Contemporary Neuroscience.- Chapter 8. Carl Gillett. Understanding the sciences through the fog of ”functionalism.’.- 2.B. Philosophy of technology, design and functions.- Chapter 9. Fran¸ coise Longy. Artifacts and Organisms: A Case for a New Etiological Theory of Functions.- Chapter 10. Pieter Vermaas and Wybo Houkes. Functions as Epistemic Highlighters: An Engineering Account of Technical, Biological and Other Functions.- Epilogue.- Larry Wright. Revising teleological explanations: reflections three decades on. (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.

It has been claimed that quantum mechanics, unlike classical mechanics, allows for free will. In this paper I articulate that claim and explain how a complex physical system possessing fractal-like self similarity could exhibitboth self consciousness and self determination. I use complexity theory to show how quantum mechanical indeterminacies at the neural level could “percolate up” to the levels of scale within the brain at which sensory-motor information transformations occur. Finally, I explain how macro level indeterminacy could be (...) coupled with self determination to provide a physical system with the capacity for radically free willing. (shrink)

We provide a first order axiomatization of the expansion of the complex field by the exponential function restricted to the subring of integers modulo the first order theory of (Z, +, ·).