Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, ranging from (...) small time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

The current literature standardly conceives of voting power in terms of decisiveness: the ability to change the voting outcome by unilaterally changing one’s vote. I argue that this classic conception of voting power, which fails to account for partial decisiveness or efficacy, produces erroneous results because it saddles the concept of voting power with implausible microfoundations. This failure in the measure of voting power in turn reflects a philosophical mistake about the concept of social power in general: a failure to (...) recognize that an agent can exercise individual social power with others’ assistance, in virtue of the group’s collective power, sometimes even when she could not unilaterally scuttle the group’s collective power. I therefore develop a conception of efficacy that admits of degrees and defend a Recursive Measure of voting power that takes partial efficacy into account. (shrink)

Traces the development of recursive functions from their origins in the late nineteenth century to the mid-1930s, with particular emphasis on the work and influence of Kurt Gödel.

A class of problems is called decidable if there is an algorithm which will give the answer to any problem of the class after a finite length of time. The purpose of this paper is to discuss the classes of problems that can be solved by infinitely long decision procedures in the following sense: An algorithm is given which, for any problem of the class, generates an infinitely long sequence of guesses. The problem will be said to be solved in (...) the limit if, after some finite point in the sequence, all the guesses are correct and the same. Functions, sets, and functionals which are decidable by such infinite algorithms will be calledlimiting recursive. These, together with classes of objects which can beidentified in the limit, are the subjects of this report.Without qualification,setwill mean set of numbers;functionwill mean number-theoretic function of 1 variable, possibly partial;functionalswill take numerical values and have any number of numerical and/or function variables, the latter ranging solely over total functions of 1 variable. Thus a function is a special case of a functional,xwill invariably stand for a numerical variable;φfor a function variable;gfor a guess ;nfor the numerical variable which indexes the guesses, referred to as thetime. (shrink)

This volume contains papers from the recursion theory session of the Kazan Workshop on Recursion and Complexity Theory. Recursion theory, the study of computability, is an area of mathematical logic that has traditionally been particularly strong in the United States and the former Soviet Union. This was the first workshop ever to bring together about 50 international experts in recursion theory from the United States, the former Soviet Union and Western Europe.

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.

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)

Define a second order tree to be a map between trees. We show that many properties of ordinary trees have analogs for second order trees. In particular, we show that there is a notion of “definition by recursion on a well-founded second order tree” which generalizes “definition by transfinite recursion”. We then use this new notion of definition by recursion to prove an analog of Lusin’s Separation theorem for closure spaces of global sections of a second order (...) tree. (shrink)

This work is a self-contained elementary exposition of the theory of recursive functionals, that also includes a number of advanced results.

This paper, a contribution to “micro set theory”, is the study promised by the first author in [M4], as improved and extended by work of the second. We use the rudimentarily recursive functions and the slightly larger collection of gentle functions to initiate the study of provident sets, which are transitive models of $\mathsf{PROVI}$, a subsystem of $\mathsf{KP}$ whose minimal model is Jensen’s $J_{\omega}$. $\mathsf{PROVI}$ supports familiar definitions, such as rank, transitive closure and ordinal addition—though not ordinal multiplication—and Shoenfield’s unramified (...) forcing. Providence is preserved under directed unions. An arbitrary set has a provident closure, and the extension of a provident $M$ by a set-generic $\mathcal{G}$ is the provident closure of $M\cup\{\mathcal{G}\}$. The improvidence of many models of $\mathsf{Z}$ is shown. The final section uses similar but simpler recursions to show, in the weak system $\mathsf{MW}$, that the truth predicate for $\dot{\varDelta}_{0}$ formulæ is $\Delta_{1}$. (shrink)

The book examines one of the most contested topics in linguistics and cognitive science: the role of recursion in language. It offers a precise account of what recursion is, what role it should play in cognitive theories of human knowledge, and how it manifests itself in the mental representations of language and other cognitive domains.

This almost self-contained introduction to higher recursion theory is essential reading for all researchers in the field.

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)

This volume presents the lecture notes of short courses given by three leading experts in mathematical logic at the 2012 Asian Initiative for Infinity Logic Summer School. The major topics cover set-theoretic forcing, higher recursion theory, and applications of set theory to C*-algebra. This volume offers a wide spectrum of ideas and techniques introduced in contemporary research in the field of mathematical logic to students, researchers and mathematicians.

Models of normal open induction are those normal discretely ordered rings whose nonnegative part satisfy Peano's axioms for open formulas in the language of ordered semirings. (Where normal means integrally closed in its fraction field.) In 1964 Shepherdson gave a recursive nonstandard model of open induction. His model is not normal and does not have any infinite prime elements. In this paper we present a recursive nonstandard model of normal open induction with an unbounded set of infinite prime elements.

Induction–recursion is a powerful definition method in intuitionistic type theory. It extends inductive definitions and allows us to define all standard sets of Martin-Löf type theory as well as a large collection of commonly occurring inductive data structures. It also includes a variety of universes which are constructive analogues of inaccessibles and other large cardinals below the first Mahlo cardinal. In this article we give a new compact formalization of inductive–recursive definitions by modeling them as initial algebras in slice (...) categories. We give generic formation, introduction, elimination, and equality rules generalizing the usual rules of type theory. Moreover, we prove that the elimination and equality rules are equivalent to the principle of the existence of initial algebras for certain endofunctors. We also show the equivalence of the current formulation with the formulation of induction–recursion as a reflection principle given in Dybjer and Setzer 93). Finally, we discuss two type-theoretic analogues of Mahlo cardinals in set theory: an external Mahlo universe which is defined by induction–recursion and captured by our formalization, and an internal Mahlo universe, which goes beyond induction–recursion. We show that the external Mahlo universe, and therefore also the theory of inductive–recursive definitions, have proof-theoretical strength of at least Rathjen's theory KPM. (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)

Although Peano arithmetic is necessarily incomplete, Isaacson argued that it is in a sense conceptually complete: proving a statement of the language of PA that is independent of PA will require conceptual resources beyond those needed to understand PA. This paper gives a test of Isaacon’s thesis. Understanding PA requires understanding the functions of addition and multiplication. It is argued that grasping these primitive recursive functions involves grasping the double ancestral, a generalized version of the ancestral operator. Thus, we can (...) test Isaacon’s thesis by seeing whether when we phrase arithmetic in a context with the double ancestral operator, the result is conservative over PA. This is a stronger version of the test given by Smith, who argued that understanding the predicate “natural number” requires understanding the ancestral operator, but did not investigate what is required to understand the arithmetic functions. (shrink)

A real number is recursively approximable if there is a computable sequence of rational numbers converging to it. If some extra condition to the convergence is added, then the limit real number might have more effectivity. In this note we summarize some recent attempts to classify the recursively approximable real numbers by the convergence rates of the corresponding computable sequences ofr ational numbers.

This paper is concerned with the proper way to effectivize the notion of a Polish space. A theorem is proved that shows the recursive Polish space structure is not found in the effectively open subsets of a space $${\mathcal {X}}$$ X, and we explore strong evidence that the effective structure is instead captured by the effectively open subsets of the product space $$\mathbb {N}\times {\mathcal {X}}$$ N × X.

iterations of REA operators, as well as extensions, generalizations and other applications are given in [6] while those for the ...

This work is a sequel to the author's Godel's Incompleteness Theorems, though it can be read independently by anyone familiar with Godel's incompleteness theorem for Peano arithmetic. The book deals mainly with those aspects of recursion theory that have applications to the metamathematics of incompleteness, undecidability, and related topics. It is both an introduction to the theory and a presentation of new results in the field.

The purpose of this paper is to clarify the relationship between various conditions implying essential undecidability: our main result is that there exists a theory T in which all partially recursive functions are representable, yet T does not interpret Robinson’s theory R. To this end, we borrow tools from model theory — specifically, we investigate model-theoretic properties of the model completion of the empty theory in a language with function symbols. We obtain a certain characterization of ∃∀ theories interpretable in (...) existential theories in the process. (shrink)

It has been claimed that recursion is one of the properties that distinguishes human language from any other form of animal communication. Contrary to this claim, a recent study purports to demonstrate center‐embedded recursion in starlings. I show that the performance of the birds in this study can be explained by a counting strategy, without any appreciation of center‐embedding. To demonstrate that birds understand center‐embedding of sequences of the form AnBn (such as A1A2B2B1, or A3A4A5B5B4B3) would require not (...) only that they discriminate such patterns from other patterns, but that they appreciate that elements must be bound from the outside in (thus, in the above examples, A1B1, A2B2, A3B3, A4B4, A5B5 are bound pairs). This has not been shown in nonhuman species, and sentences with this structure are difficult even for humans to parse. There appears to be no evidence to date that nonhuman species understand recursion. (shrink)

GENERALIZED RECUBION THEORY II © North-Holland Publishing Company (1978) MONOTONE QUANTIFIERS AND ADMISSIBLE SETS Ion Barwise University of Wisconsin ...

Provability, Computability and Reflection.

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.

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. (...) In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous. (shrink)

The article introduces recursive ontology, a general ontology which aims to describe how being is organized and what are the processes that drive it. In order to answer those questions, I use a multidisciplinary approach that combines the theory of levels, philosophy and systems theory. The main claim of recursive ontology is that being is the product of a single recursive process of generation that builds up all of reality in a hierarchical fashion from fundamental physical particles to human societies. (...) To support this assumption, I provide the general laws and the basic principles of recursive ontology as well as a semi-formalised model of the theory based on a recursive generative grammar. Recursive ontology not only actively promotes a multidisciplinary investigation of reality, but also can be used as a general framework to develop future domain-specific theories. (shrink)

this paper we argue that the formalism can also be applied to modelling the hierarchical structure of physical mechanisms. The resulting network contains quantitative information about probabilities, as well as qualitative information about mechanistic structure and causal relations. Since information about probabilities, mechanisms and causal relations are vital for prediction, explanation and control respectively, a recursive Bayesian net can be applied to all these tasks. We show how a Recursive Bayesian Net can be used to model mechanisms in cancer science. (...) The highest level of the proposed model will contain variables at the clinical level, while a middle level will map the structure of the DNA damage response mechanism and the lowest level will contain information about gene expression. (shrink)

The series is devoted to the publication of high-level monographs on all areas of mathematical logic and its applications. It is addressed to advanced students and research mathematicians, and may also serve as a guide for lectures and for seminars at the graduate level.

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 propose and axiomatically analyze a class of rational solutions to simple allocation problems where a policy-maker allocates an endowment $E$ among $n$ agents described by a characteristic vector c. We propose a class of recursive rules which mimic a decision process where the policy-maker initially starts with a reference allocation of $E$ in mind and then uses the data of the problem to recursively adjust his previous allocation decisions. We show that recursive rules uniquely satisfy rationality, c-continuity, and other-c (...) monotonicity. We also show that a well-known member of this class, the Equal Gains rule, uniquely satisfies rationality, c-continuity, and equal treatment of equals. (shrink)

In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces,, of a recursively presented vector spaceV∞has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. In all (...) of these models, the algebraic closure of a set is nontrivial., is given in §1, however in vector spaces, cl is just the subspace generated byS, in Boolean algebras, cl is just the subalgebra generated byS, and in algebraically closed fields, cl is just the algebraically closed subfield generated byS.)In this paper, we give a general model theoretic setting in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the modelswhich we study is that the algebraic closure of setis just itself, i.e., cl = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class ofn-dimensional partial orderings. (shrink)

A semantics for the lambda-calculus due to Friedman is used to describe a large and natural class of categorical recursion-theoretic notions. It is shown that if e 1 and e 2 are godel numbers for partial recursive functions in two standard ω-URS's 1 which both act like the same closed lambda-term, then there is an isomorphism of the two ω-URS's which carries e 1 to e 2.

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.

It is an open problem within the study of recursively enumerable classes of recursively enumerable sets to characterize those recursively enumerable classes which can be recursively enumerated without repetitions. This paper is concerned with a weaker property of r.e. classes, namely that of being recursively enumerable with at most finite repetitions. This property is shown to behave more naturally: First we prove an extension theorem for classes satisfying this property. Then the analogous theorem for the property of recursively enumerable classes (...) of being recursively enumerable with a bounded number of repetitions is shown not to hold. The index set of the property of recursively enumerable classes "having an enumeration with finite repetitions" is shown to be Σ 0 6 -complete. (shrink)