This graduate-level_text by a master in the field builds a function theory of the rational field that combines aspects of classical and intuitionist analysis. Topics include recursive convergence, recursive and relative continuity, recursive and relative differentiability, the relative integral, elementary functions, and transfinite ordinals. 1961 edition.

We investigate systems of ordinary differential equations with a parameter. We show that under suitable assumptions on the systems the solutions are computable in the sense of recursive analysis. As an application we give a complete characterization of the recursively enumerable sets using Fourier coefficients of recursive analytic functions that are generated by differential equations and elementary operations.

A development of a constructive fragment of analysis: "constructive" in the strong sense that instead of, say, Cauchy sequences, it deals only with recursive sequences of rationals which can be recursively shown to converge. Analogues of classical subjects such as continuity and differentiability are explored in detail. The book presupposes familiarity with both classical analysis and the theory of recursive functions.—R. H. T.

In this paper we develop a point-free approach to the study of topological spaces and functions on them, establish platforms for both and present some findings on recursive points. In the first sections of the paper, we obtain conditions under which our approach leads to the generation of ideal objects with which mathematicians work. Next, we apply the effective version of our approach to the real numbers, and make exact connections to the classical approach to recursive reals. In (...) the succeeding sections of the paper, we introduce machinery to produce functions on topological spaces and find succinct conditions which will be effectivized in our sequel. (shrink)

In this paper we continue our work of Kalantari and Welch . There we introduced machinery to produce a point-free approach to points and functions on topological spaces and found conditions for both which lend themselves to effectivization. While we studied recursive points in that paper, here, we present two useful classes of recursive functions on topological spaces, apply them to the reals, and find precise accounting for the nature of the properties of some examples that exist in (...) the literature. We end with a construction of a recursive function on a small subset of the unit interval which is strongly nonextendible. (shrink)

Solovay has shown that if F: [ω] ω → 2 is a clopen partition with recursive code, then there is an infinite homogeneous hyperarithmetic set for the partition (a basis result). Simpson has shown that for every 0 α , where α is a recursive ordinal, there is a clopen partition F: [ω] ω → 2 such that every infinite homogeneous set is Turing above 0 α (an anti-basis result). Here we refine these results, by associating the "order (...) type" of a clopen set with the Turing complexity of the infinite homogeneous sets. We also consider the Nash-Williams barrier theorem and its relation to the clopen Ramsey theorem. (shrink)

Alonzo Church's mathematical work on computability and undecidability is well-known indeed, and we seem to have an excellent understanding of the context in which it arose. The approach Church took to the underlying conceptual issues, by contrast, is less well understood. Why, for example, was "Church's Thesis" put forward publicly only in April 1935, when it had been formulated already in February/March 1934? Why did Church choose to formulate it then in terms of Gödel's general recursiveness, not his own λ (...) -definability as he had done in 1934? A number of letters were exchanged between Church and Paul Bernays during the period from December 1934 to August 1937; they throw light on critical developments in Princeton during that period and reveal novel aspects of Church's distinctive contribution to the analysis of the informal notion of effective calculability. In particular, they allow me to give informed, though still tentative answers to the questions I raised; the character of my answers is reflected by an alternative title for this paper, Why Church needed Gödel's recursiveness for his Thesis. In Section 5, I contrast Church's analysis with that of Alan Turing and explore, in the very last section, an analogy with Dedekind's investigation of continuity. (shrink)

The notion of a function from ℕ to ℕ defined by recursion on ordinal notations is fundamental in proof theory. Here this notion is generalized to functions on the universe of sets, using notations for well orderings longer than the class of ordinals. The generalization is used to bound the rate of growth of any function on the universe of sets that is Σ1-definable in Kripke–Platek admissible set theory with an axiom of infinity. Formalizing the argument provides an ordinal (...) class='Hi'>analysis. (shrink)

Mauldin [15] proved that there is an analytic set, which cannot be represented by $B\cup X$ for some Borel set B and a subset X of a $\boldsymbol{\Sigma }^0_2$ -null set, answering a question by Johnson [10]. We reprove Mauldin’s answer by a recursion-theoretical method. We also give a characterization of the Borel generated $\sigma $ -ideals having approximation property under the assumption that every real is constructible, answering Mauldin’s question raised in [15].

Transfinite ordinal numbers enter mathematical practice mainly via the method of definition by transfinite recursion. Outside of axiomatic set theory, there is a significant mathematical tradition in works recasting proofs by transfinite recursion in other terms, mostly with the intention of eliminating the ordinals from the proofs. Leaving aside the different motivations which lead each specific case, we investigate the mathematics of this action of proof transforming and we address the problem of formalising the philosophical notion of elimination which characterises (...) this move. (shrink)

In their 2002 seminal paper Hauser, Chomsky and Fitch hypothesize that recursion is the only human-specific and language-specific mechanism of the faculty of language. While debate focused primarily on the meaning of recursion in the hypothesis and on the human-specific and syntax-specific character of recursion, the present work focuses on the claim that recursion is language-specific. We argue that there are recursive structures in the domain of motor intentionality by way of extending John R. Searle’s analysis of intentional (...) action. We then discuss evidence from cognitive science and neuroscience supporting the claim that motor-intentional recursion is language-independent and suggest some explanatory hypotheses: linguistic recursion is embodied in sensory-motor processing; linguistic and motor-intentional recursions are distinct and mutually independent mechanisms. Finally, we propose some reflections about the epistemic status of HCF as presenting an empirically falsifiable hypothesis, and on the possibility of testing recursion in different cognitive domains. (shrink)

Let the chain antichain principle (CAC) be the statement that each partial order on $\mathbb{N}$ possesses an infinite chain or an infinite antichain. Chong, Slaman, and Yang recently proved using forcing over nonstandard models of arithmetic that CAC is $\Pi^1_1$-conservative over $\text{RCA}_0+\Pi^0_1\text{-CP}$ and so in particular that CAC does not imply $\Sigma^0_2$-induction. We provide here a different purely syntactical and constructive proof of the statement that CAC (even together with WKL) does not imply $\Sigma^0_2$-induction. In detail we show using a (...) refinement of Howard's ordinal analysis of bar recursion that $\text{WKL}_0^\omega+\text{CAC}$ is $\Pi^0_2$-conservative over PRA and that one can extract primitive recursive realizers for such statements. Moreover, our proof is finitary in the sense of Hilbert's program. CAC implies that every sequence of $\mathbb{R}$ has a monotone subsequence. This Bolzano-Weierstraß}-like principle is commonly used in proofs. Our result makes it possible to extract primitive recursive terms from such proofs. We also discuss the Erdős-Moser principle, which—taken together with CAC—is equivalent to $\text{RT}^2_2$. (shrink)

Language sciences have long maintained a close and supposedly necessary coupling between the infinite productivity of the human language faculty and recursive grammars. Because of the formal equivalence between recursion and non-recursive iteration; recursion, in the technical sense, is never a necessary component of a generative grammar. Contrary to some assertions this equivalence extends to both center-embedded relative clauses and hierarchical parse trees. Inspection of language usage suggests that recursive rule components in fact contribute very little, and (...) likely nothing significant, to linguistic creativity. Further than this, if the productivity of human language is considered as not rigidly bound, but not infinite, then the need for any sort of iteration in generative grammars vanishes and can be replaced with a Non-iterative Explicit Alternatives Rule grammar. The knock-on effects of dispensing with recursive grammar components are: that language diversity can simply be based on rule and lexicon combinatorics with no potentially infinite dimensions derived from recursive or iterative components of rules; the oddity of a vast, multiply-infinite competence set of ‘grammatical but unacceptable’ productions is gone; and the development of a language faculty based on rules that eschew iterative rule components avoids any need for explaining ‘special’ mechanisms. On the broader front of searching for the mechanisms of mind, our analysis can be similarly applied to the proposals for a recursive basis for mind as an explanation for humanity’s great leap forward. (shrink)

This book is an investigation of algorithmic contingency and an elucidation of the contemporary situation that we are living in: the regular arrival of algorithmic catastrophes on a global scale. Through a historical analysis of philosophy, computation and media, this book proposes a renewed relation between nature and technics.

We use the multiple price list method and a recursive expected utility theory of smooth ambiguity to separate out attitude towards risk from that towards ambiguity. Based on this separation, we investigate if there are differences in agent behaviour under uncertainty over gain amounts vis-a-vis uncertainty over loss amounts. On an aggregate level, we find that (i) subjects are risk averse over gains and risk seeking over losses, displaying a “reflection effect” and (ii) they are ambiguity neutral over gains (...) and are mildly ambiguity seeking over losses. Further analysis shows that on an individual level, and with respect to both risky and ambiguous prospects, there is limited incidence of a reflection effect where subjects are risk/ambiguity averse (seeking) in gains and seeking (averse) in losses, though this incidence is higher for ambiguous prospects. A very high proportion of such cases of reflection exhibit risk (ambiguity) aversion in gains and risk (ambiguity) seeking in losses, with the reverse effect being significantly present in the case of risk but almost absent in case of ambiguity. Our results suggest that reflection across gains and losses is not a stable individual characteristic, but depends upon whether the form of uncertainty is precise or ambiguous, since we rarely find an individual who exhibits reflection in both risky and ambiguous prospects. We also find that correlations between attitudes towards risk and ambiguity were domain dependent. (shrink)

A method for the recursive identification of physiological models of the cardiovascular baroreflex is proposed and applied to the time-varying analysis of vagal and sympathetic activities. The proposed method was evaluated with data from five newborn lambs, which were acquired during injection of vasodilator and vasoconstrictors and the results show a close match between experimental and simulated signals. The model-based estimation of vagal and sympathetic contributions were consistent with physiological knowledge and the obtained estimators of vagal and sympathetic (...) activities were compared to traditional markers associated with baroreflex sensitivity. High correlations were observed between traditional markers and model-based indices. (shrink)

This paper is concerned with the event-based state and fault estimation problem for a class of linear discrete systems with randomly occurring faults and missing measurements. Different from the static event-based transmission mechanism with a constant threshold, a dynamic event-based mechanism is exploited here to regulate the threshold parameter, thus further reducing the amount of data transmission. Some mutually independent Bernoulli random variables are used to characterize the phenomena of ROFs and missing measurements. In order to simultaneously estimate the system (...) state and the fault signals, the main attention of this paper is paid to the design of recursive filter; for example, for all DETM, ROFs, and missing measurements, an upper bound for the estimation error covariance is ensured and the relevant filter gain matrix is designed by minimizing the obtained upper bound. Moreover, the rigorous mathematical analysis is carried out for the exponential boundedness of the estimation error. It is clear that the developed algorithms are dependent on the threshold parameters and the upper bound together with the probabilities of missing measurements and ROFs. Finally, a numerical example is provided to indicate the effectiveness of the presented estimation schemes. (shrink)

We show how two iterated products of selection functions can both be used in conjunction with systemTto interpret, via the dialectica interpretation and modified realizability, full classical analysis. We also show that one iterated product is equivalent over systemTto Spector’s bar recursion, whereas the other isT-equivalent to modified bar recursion. Modified bar recursion itself is shown to arise directly from the iteration of a different binary product of ‘skewed’ selection functions. Iterations of the dependent binary products are also considered (...) but in all cases are shown to beT-equivalent to the iteration of the simple products. (shrink)

We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...) historical and conceptual analysis of computability and recursion we make several recommendations in section §7 about preserving the intensional differences between the concepts of "computability" and "recursion." Specifically we recommend that: the term "recursive" should no longer carry the additional meaning of "computable" or "decidable;" functions defined using Turing machines, register machines, or their variants should be called "computable" rather than "recursive;" we should distinguish the intensional difference between Church's Thesis and Turing's Thesis, and use the latter particularly in dealing with mechanistic questions; the name of the subject should be "Computability Theory" or simply Computability rather than "Recursive Function Theory.". (shrink)

v. 1. Recursive model theory -- v. 2. Recursive algebra, analysis and combinatorics.

Several extensions of Gödel's system TT with new forms of recursion have been designed for the purpose of giving a computational interpretation to classical analysis. One can organise many of these extensions into two groups: those based on bar recursion , which include Spector's original bar recursion, modified bar recursion and the more recent products of selections functions, or those based on open recursion which in particular include the symmetric Berardi–Bezem–Coquand functional. We relate these two groups by showing that (...) both open recursion and the BBC functional are primitive recursively equivalent to a variant of modified bar recursion. Our results, in combination with existing research, essentially complete the classification up to primitive recursive equivalence of those extensions of system TT used to give a direct computational interpretation to choice principles. (shrink)

Thomas Hurka, in his book Virtue, Vice, and Value, and elsewhere, develops a recursive analysis of higher-order pleasures and pains. The account leads Hurka to some potentially controversial conclusions. For instance, Hurka argues on its basis that some states are both good and evil and also that the view he calls the conditionality view is false. In this paper, I argue that Hurka’s formulation of the recursive account is unusual and inelegant, and that Hurka reaches his conclusions (...) only because of its peculiar aspects. I provide an alternative recursive account which is similar in spirit to Hurka’s but which is theoretically elegant and does not entail those conclusions. (shrink)

This paper is a culmination of our new foundations for recursive analysis through recursive topology as reported in Kalantari and Welch 125; 98 87). While in those papers we developed groundwork for an approach to point free analysis and applied recursion theory, in this paper we blend techniques of recursion theory with those of topology to establish new findings. We present several new techniques different from existing ones which yield interesting results. Incidental to our work is (...) a unifying explanation of various schools of study for recursive analysis. (shrink)

We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains of recursive quantum functions and hence with avoidable points . An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be an arbitrary (...) subset of the avoidable points of a single avoidance function, and we study an effective union of such sets which we call a piecemeal avoidable set. We note that each of ‘the set of recursive points’ and ‘the set of avoidable points’ is of first category but not recursively of first category. We show an exdomain exists which is recursively nowhere dense, as well as one that is nowhere dense but not recursively nowhere dense. After establishing that every exdomain is recursively of first category, we prove that given any fixed exdomain, there is another exdomain, which while dense in the underlying space, is disjoint from the fixed exdomain. Finally, we show how to build a recursive sequence of recursive quantum functions that have mutually disjoint, dense exdomains. (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., (...) class='Hi'>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)