Machine learning algorithms reshape how people communicate, exchange, and associate; how institutions sort them and slot them into social positions; and how they experience life, down to the most ordinary and intimate aspects. In this article, we draw on examples from the field of social media to review the commonalities, interactions, and contradictions between the dispositions of people and those of machines as they learn from and make sense of each other.

First published in Essays: Second Series in 1844, Ralph Waldo Emerson’s “Experience” has long been considered an enigmatic touchstone of the Emersonian corpus. This essay seems to point to many difficult—and key—questions as to the aims and implications of Emerson’s literary style, intellectual methods, and philosophical inquiries. Conventionally viewed as evidence of a hinge in Emerson’s intellectual development from youthful innocence to middle-aged experience, this essay has often been understood as an arena for the contestation of Emersonian ideas about self-reliance, (...) philosophical idealism, and self-knowledge; as with ancient gladiatorial spectacles, not all of these ideas may walk out of the arena alive.1 .. (shrink)

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)

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)

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.

We give recursion-theoretic characterizations of the counting class \(\textsf {\#P} \), the class of those functions which count the number of accepting computations of non-deterministic Turing machines working in polynomial time. Moreover, we characterize in a recursion-theoretic manner all the levels \(\{\textsf {\#P} _k\}_{k\in {\mathbb {N}}}\) of the counting hierarchy of functions \(\textsf {FCH} \), which result from allowing queries to functions of the previous level, and \(\textsf {FCH} \) itself as a whole. This is done in the style of (...) Bellantoni and Cook’s safe recursion, and it places \(\textsf {\#P} \) in the context of implicit computational complexity. Namely, it relates \(\textsf {\#P} \) with the implicit characterizations of \(\textsf {FPTIME} \) (Bellantoni and Cook, Comput Complex 2:97–110, 1992) and \(\textsf {FPSPACE} \) (Oitavem, Math Log Q 54(3):317–323, 2008), by exploiting the features of the tree-recursion scheme of \(\textsf {FPSPACE} \). (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.

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)

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.

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)

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

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

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.

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

We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of recursively enumerable sets with inclusion. (...) We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions. (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.

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.

Recursivity and Contingency. By Hui Yuk.

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)

In previous work the author has introduced a lambda calculus SLR with modal and linear types which serves as an extension of Bellantoni–Cook's function algebra BC to higher types. It is a step towards a functional programming language in which all programs run in polynomial time. In this paper we develop a semantics of SLR using BCK -algebras consisting of certain polynomial-time algorithms. It will follow from this semantics that safe recursion with arbitrary result type built up from N and (...) ⊸ as well as recursion over trees and other data structures remains within polynomial time. In its original formulation SLR supported only natural numbers and recursion on notation with first-order functional result type. (shrink)

We prove a recursion theoretic characterization of the Topological Vaught Conjecture in the Zermelo‐Fraenkel set theory by using tools from effective descriptive set theory and by revisiting the result of Miller that orbits in Polish G‐spaces are Borel sets.

Presents a new framework for the complexity of algorithms, for all readers interested in the theory of computation.

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)

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.

This fascinating popular science journey explores key concepts in information theory in terms of Conway's "Game of Life" program. The author explains the application of natural law to a random system and demonstrates the necessity of limits. Other topics include the limits of knowledge, paradox of complexity, Maxwell's demon, Big Bang theory, and much more. 1985 edition.

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)

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)

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.

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)

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)

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)

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 (p. r., for short), 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)

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)

We give a novel proof that primitive recursive functions are closed under nested simple recursion. This new presentation is supplied with a detailed proof which can be easily formalized in small fragments of Peano 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)

The capacity to generate recursive sequences is a marker of rich, algorithmic cognition, and perhaps unique to humans. Yet, the precise processes driving recursive sequence generation remain mysterious. We investigated three potential cognitive mechanisms underlying recursive pattern processing: hierarchical reasoning, ordinal reasoning, and associative chaining. We developed a Bayesian mixture model to quantify the extent to which these three cognitive mechanisms contribute to adult humans’ performance in a sequence generation task. We further tested whether recursive rule discovery depends upon relational (...) information, either perceptual or semantic. We found that the presence of relational information facilitates hierarchical reasoning and drives the generation of recursive sequences across novel depths of center embedding. In the absence of relational information, the use of ordinal reasoning predominates. Our results suggest that hierarchical reasoning is an important cognitive mechanism underlying recursive pattern processing and can be deployed across embedding depths and relational domains. (shrink)

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

We state some general facts on r.e. structures, e.g. we show that the free countable structures in quasivarieties are r.e. and construct acceptable numerations and universal r.e. structures in quasivarieties. The last facts are similar to the existence of acceptable numerations of r.e. sets and creative sets. We state a universality property of the acceptable numerations, classify some index sets and discuss their relation to other decision problems. These results show that the r.e. structures behave in some respects better than (...) the recursive structures. (shrink)

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)

We prove a converse to one of the theorems from [F], giving a description in terms of Turing complexity of sets which can be coded into recursive and r.e. quotient Boolean algebras.

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.

This volume focuses on recursion and reveals a host of new theoretical arguments, philosophical perspectives, formal representations, and empirical evidence from parsing, acquisition, and computer models, highlighting its central role in modern science. Noam Chomsky, whose work introduced recursion to linguistics and cognitive science, and other leading researchers in the fields of philosophy, semantics, computer science, and psycholinguistics in showing the profound reach of this concept into modern science. Recursion has been at the heart of generative grammar from the outset. (...) Recent work in minimalism has put it at center-stage with a wide range of consequences across the intellectual landscape. The contributors to this volume both advance the field and provide a cross-sectional view of the place that recursion takes in modern science. (shrink)

We study topological constructions in the recursion theoretic framework of the lattice of recursively enumerable open subsets of a topological space X. Various constructions produce complemented recursively enumerable open sets with additional recursion theoretic properties, as well as noncomplemented open sets. In contrast to techniques in classical topology, we construct a disjoint recursively enumerable collection of basic open sets which cannot be extended to a recursively enumerable disjoint collection of basic open sets whose union is dense in X.

The aim of this paper is to critically review the traditional typology of argument macrostructures, particularly, the dichotomy between linked and convergent structure. We have found an argument structure that does not fall under one of those five traditional categories: basic, serial, divergent, linked and convergent. We show that the new argument structure, which we call the recursive structure, is not rare-earth, but ubiquitous in real argumentation. Then, we propose and justify a new approach to diagramming arguments of the structure. (...) The new argument structure is really new because arguments of the new structure are analyzed and evaluated differently from those of the other structures, especially from hybrid arguments considered in the literature. In light of the new argument structure, we present a hypothesis why assumptions and exceptions of a defeasible argument play different roles in dialectical settings. (shrink)