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)

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.

Provability, Computability and Reflection.

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)

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

La noción de recursión se emplea en diferentes sentidos, adquiriendo una variedad de significados. Así, en unos casos se usa para caracterizar una regla esencial que constituye un modo de definición en un sistema. Este sentido tiene su origen en la Lógica Matemática y la Teoría de la Computabilidad. En otros casos se aplica para indicar la organización interna de una estructura, tal como sucede en la Ciencia Cognitiva y la Ciencia de la Computación, al tiempo que también se emplea (...) en el sentido anterior en estas mismas disciplinas. El objetivo de este trabajo es mostrar en cada caso las diferencias en el uso de ambos sentidos. (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)

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 define a fragment of monadic infinitary second-order logic corresponding to an abstract separation property, We use this to define the concept of a separation subclass. We use model theoretic techniques and games to show that separation subclasses whose axiomatisations are recursively enumerable in our second-order fragment can also be recursively axiomatised in their original first-order language. We pin down the expressive power of this formalism with respect to first-order logic, and investigate some questions relating to decidability and computational complexity. (...) As applications of these results, by showing that certain classes can be straightforwardly defined as separation subclasses, we obtain first-order axiomatisability results for these classes. In particlar, we apply this technique to graph colourings and a class of partial algebras arising from separation logic. (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.

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)

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)

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.

A unary algebra is an algebraic system A = , where ƒ 0 ,…,ƒ n are unary operations on A and n ∈ ω. In the paper we develop the theory of effective unary algebras. We investigate well-known questions of constructive model theory with respect to the class of unary algebras. In the paper we construct unary algebras with a finite number of recursive isomorphism types. We give the notions of program, uniform, and algebraic dimensions of models, and then (...) we investigate these notions on unary algebras. We find connections between algebraic and effective properties of r.e. representable unary algebras. We also deal with finitely generated r.e. unary algebras. We show the connections between trees and unary algebras. Our interests also concern recursive automorphisms groups, r.e. subalgebra and congruence lattices of effective unary algebras. (shrink)

There is a recursive set of natural numbers which is the difference set of some recursively enumerable set but which is not the difference set of any recursive set.

The classical measures of voting power are based on players' decisiveness or full causal efficacy in vote configurations or divisions. We design an alternative, recursive measure departing from this classical approach. We motivate the measure via an axiomatic characterisation based on reasonable axioms and by offering two complementary interpretations of its meaning: first, we interpret the measure to represent, not the player's probability of being decisive in a voting structure, but its expected probability of being decisive in a uniform (...) random walk from a vote configuration in the subset lattice (through which we represent the voting structure); and, second, we interpret it as representing a player's expected efficacy, thereby incorporating the notion of partial and not just full causal efficacy. We shore up our measure by demonstrating that it satisfies a set of postulates any reasonable voting measure should satisfy, namely, the iso-invariance, dummy, dominance, donation, minimum-power bloc, and quarrel postulates. (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)

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.

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 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 work is a self-contained elementary exposition of the theory of recursive functionals, that also includes a number of advanced results.

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)

On a widely held characterization, triadic joint attention is the capacity to perceptually attend to an object or event together with another subject. In the last four decades, research in developmental psychology has provided increasing evidence of the crucial role that this capacity plays in socio-cognitive development, early language acquisition, and the development of perspective-taking. Yet, there is a striking discrepancy between the general agreement that joint attention is critical in various domains, and the lack of theoretical consensus on how (...) to account for it. This paper pursues three interrelated aims: (i) it examines the contrast between reductive and non-reductive views of (triadic) joint attention, by bringing into focus the notion of recursive mindreading; (ii) it assembles, advances, and discusses a number of arguments against reductive views; (iii) finally, in dialogue with some prominent non-reductive views, it outlines the case for a non-reductive view that gives pride of place to the idea that co-attenders relate to one another as a ‘you’. (shrink)

Using only propositional connectives and the provability predicate of a Σ1-sound theory T containing Peano Arithmetic we define recursively enumerable relations that are complete for specific natural classes of relations, as the class of all r. e. relations, and the class of all strict partial orders. We apply these results to give representations of these classes in T by means of formulas.

It is well known that any finitary operation is recursive in a suitable total numeration. A. Orlicki showed that there is an ω-operation not recursive in any total numeration. We will show that any ω-operation is recursive in a partial numeration.

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.

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)

What has philosophy become after computation? Critical positions about what counts as intelligence, reason, and thinking have addressed this question by reenvisioning and pushing debates about the modern question of technology towards new radical visions. Artificial intelligence, it is argued, is replacing transcendental metaphysics with aggregates of data resulting in predictive modes of decision-making, replacing conceptual reflection with probabilities. This article discusses two main positions. While on the one hand, it is feared that philosophy has been replaced by cybernetic metaphysics, (...) on the other hand it is claimed that only the coconstitution of philosophy and automation challenges modern transcendental reason and colonial capital. As Donna Haraway pointed out, cybernetic circuits of communication have constructed counterfactual ontologies against the master narrative of the human. This article addresses recent attempts at redeveloping a critique of natural philosophy that explains cybernetic metaphysics beyond the universal master narratives of mechanicism and vitalism. This article suggests that the recursive system of nature and technology also needs to account for the problem of philosophical decision, which will be explored in terms of mediatic thinking, instrumentality, and automation. This article follows insights from the movie Get Out (2017) to argue that the model of philosophical decision relies on a servomechanic understanding of the medium of thought, based on the colonial abstraction of value in the prosthetic extension of the slave-machine. It explores the nonphilosophical envisioning of automation in terms of a counterfactual theorisation of the negative negation of the medium and argues for a nonoptical darkness entering the space of thinking. Philosophy and automation are neither coupled nor set in opposition as if in a ceaseless mirroring. Instead, both philosophy and automation must transform their self-determining axiomatics in order to host the heretic activities of machine propositions. (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)

Humans grasp discrete infinities within several cognitive domains, such as in language, thought, social cognition and tool-making. It is sometimes suggested that any such generative ability is based on a computational system processing hierarchical and recursive mental representations. One view concerning such generativity has been that each of the mind’s modules defining a cognitive domain implements its own recursive computational system. In this paper recent evidence to the contrary is reviewed and it is proposed that there is only (...) one supramodal computational system with recursion in the human mind. A recursion thesis is defined, according to which the hominin cognitive evolution is constituted by a recent punctuated genetic mutation that installed the general, supramodal capacity for recursion into the human nervous system on top of the existing, evolutionarily older cognitive structures, and it is argued on the basis of empirical evidence and theoretical considerations that the recursion thesis constitutes a plausible research program for cognitive science. (shrink)

It has been suggested that hierarchically structured symbols, a remarkable feature of human language, are produced via the operation of recursive combination. Recursive combination is frequently observed in human behavior, not only in language but also in action sequences, mind-reading, technology, et cetera.; in contrast, it is rarely observed in animals. Why is it that only humans use this operation? What is the adaptability of recursive combination? We aim (1) to identify the environmental feature(s) in which (...) class='Hi'>recursive combination is effective for survival and reproduction, and that has facilitated the evolution of this ability, and (2) to demonstrate the possible evolutionary processes of recursive combination. To achieve this, we constructed an evolutionary simulation of agents that generated products using recursive combination and used the results to explore the types of fitness functions (that reflect the kinds of adaptive environments) that give rise to this ability. We identified two types of adaptability of the recursive combination: (1) diversifiability of production and (2) diversifiability of products. Through the former, recursive combination promotes robustness against failure of production caused by inaccurate manipulations or irreversible changes. In an environment in which diversified products are preferable, sharing a portion of the production process for these products entails producing multiple products in which recursive combination plays a key role. We suppose that recursive combination works as a driving force of material culture. Finally, we discuss the possible evolutionary scenarios of recursive combination that is later generalized to encompass many aspects of human cognition, including human language. (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.

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)

The paper characterizes the second order arithmetic theorems of a set theory that features a recursively Mahlo universe; thereby complementing prior proof-theoretic investigations on this notion. It is shown that the property of being recursively Mahlo corresponds to a certain kind of β-model reflection in second order arithmetic. Further, this leads to a characterization of the reals recursively computable in the superjump functional.

The recursive aspect of process reliabilism has rarely been examined. The regress puzzle, which illustrates infinite regress arising from the combination of the recursive structure and the no-defeater condition incorporated into it, is a valuable exception. However, this puzzle can be dealt with in the framework of process reliabilism by reconsidering the relationship between the recursion and the no-defeater condition based on the distinction between prima facie and ultima facie justification. Thus, the regress puzzle is not a basis (...) for abandoning process reliabilism. A genuinely intractable problem for recursive reliabilism lies in the gap between the reliability of the entire path to a belief and that of its parts. Confronted with this puzzle, reliabilists can orient themselves toward ‘reliable-as-a-whole reliabilism’ instead of ‘reliable-in-every-part reliabilism’, including recursive reliabilism, which is found to be not well-motivated. (shrink)

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

A successivity in a linear order is a pair of elements with no other elements between them. A recursive linear order with recursive successivities U is recursively categorical if every recursive linear order with recursive successivities isomorphic to U is in fact recursively isomorphic to U . We characterize those recursive linear orders with recursive successivities that are recursively categorical as precisely those with order type k 1 + g 1 + k 2 + (...) g 2 +…+ g n -1 + k n where each k n is a finite order type, non-empty for i ϵ{2,…, n -1} and each g i is an order type from among {ω,ω * ,ω+ω * }∪{ k ·η: k. (shrink)

In mathematics, various representations of real numbers have been investigated. All these representations are mathematically equivalent because they lead to the same real structure – Dedekind-complete ordered field. Even the effective versions of these representations are equivalent in the sense that they define the same notion of computable real numbers. Although the computable real numbers can be defined in various equivalent ways, if “computable” is replaced by “primitive recursive” , these definitions lead to a number of different concepts, which (...) we compare in this article. We summarize the known results and add new ones. In particular we show that there is a proper hierarchy among p. r. real numbers by nested interval representation, Cauchy representation, b -adic expansion representation, Dedekind cut representation, and continued fraction expansion representation. Our goal is to clarify systematically how the primitive recursiveness depends on the representations of the real numbers. (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)

The paper discusses different approaches to the concept of recursion and its evolution from mathematics to cognitive studies. Such approaches are observed as: self‑embedded structures, multiple hierarchical levels using the same rule, and embedding structures within structures. The paper also discusses the concept of meta‑recursion. Examining meta‑recursion may enable understanding of the ability to apply recursive processes to multilayered hierarchies, with recursive procedures acting as generators. These types of recursive processes could be the fundamental elements of general (...) cognition. The paper also briefly discusses the role of probability in current recursive approaches to cognition. It is conjenctured that the hierarchical mechanism of cognition demonstrates a kind of meta‑recursion in the sense that recursive neural loops may support some primitive recursive cognitive processes, which in turn account for recursiveness of language grammars, space orientation, social cognition, etc. The study indicates that using multiple approaches to understand the phenomenon of recursion can provide a more complete understanding of the complexity of recursion, as it plays a significant role in fields like language, mathematics, and cognitive science. (shrink)

Hird, G.R., Recursive properties of relations on models, Annals of Pure and Applied Logic 63 241–269. We prove general existence theorems for recursive models on which various relations have specified recursive properties. These capture common features of results in the literature for particular algebraic structures. For a useful class of models with new relations R, S, where S is r.e., we characterize those for which there is a recursive model isomorphic to on which the relation corresponding (...) to S remains r.e., while that corresponding to R is not r.e.; immune; hyperimmune. The results are applied to vector spaces, Boolean algebras and abelian groups. In the case of vector spaces, this leads to a new kind supermaximal subspace of V∞. (shrink)

Transfinite recursion is an essential component of set theory. In this paper, we seek intrinsically justified reasons for believing in recursion and the notions of higher computation that surround it. In doing this, we consider several kinds of recursion principles and prove results concerning their relation to one another. We then consider philosophical motivations for these formal principles coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while the iterative (...) conception of set has been widely recognized as insufficient to establish replacement and recursion, its supplementation by considerations pertaining to algorithms suggests a new and philosophically well-motivated reason to believe in such principles. (shrink)