Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δmath image sets, giving conditions under which a relation is intrinsically α-r. e.

We discuss resource-bounded measures on the class of recursive structures and prove that with respect to such measures a random recursive structure is almost surely isomorphic to the unique countable model of the extension axioms.

Lange offers an argument that, according to him, “does not show merely that some proofs by mathematical induction are not explanatory. It shows that none are […]”. The aim here is to present a counterexample to his argument.

Let be a model of a theory T. Depending on wether is decidable or recursive, and on whether T is strongly minimal or -minimal, we find conditions on which guarantee that every infinite independent subset of is not recursively enumerable. For each of the same four cases we also find conditions on which guarantee that every infinite independent subset of has Turing degree 0'. More generally, let be a recursive -structure, R a relation symbol not in , (...) ψ a recursive infiniatary Π2 sentence in the language {R}, and let 0<α<ωCK1. We discuss conditions under which we can construct a recursive -structure such that ,Rψ for every Δ0α relation R on. (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)

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)

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)

Taking Chomsky’s Syntactic Structures as a starting point, this paper explores the use of recursive techniques in contemporary linguistic theory. Specifically, it is shown that there were profound ambiguities surrounding the notion of recursion in the 1950s, and that this was partly due to the fact that influential texts such as Syntactic Structures neglected to define what exactly constituted a recursive device. As a result, uncertainties concerning the role of recursion in linguistic theory have prevailed until the present (...) day, and some of the most common misunderstandings that have appeared in recent discussions are examined at some length. This article shows that debates about such topics are frequently undermined by fundamental misunderstandings concerning core terminology, and the full extent of the prevailing haziness is revealed. An attempt is made, for instance, to distinguish between such things as iterative constructional devices and self-similar syntactic embedding, despite the fact that these are usually both unhelpfully classified as examples of recursion. Consequently, this article effectively constitutes a plea for much greater accuracy and clarity when such important issues are addressed from a linguistic perspective. (shrink)

It will be shown that in the lattice of recursively enumerable sets one can define elementarily with parameters a structure isomorphic to (∑ 0 4 , ∑ 0 3 ), i.e. isomorphic to the lattice of ∑ 0 4 sets together with a unary predicate selecting out exactly the ∑ 0 3 sets.

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 suggested that external and/or internal limitations paradoxically may lead to superior learning, that is, the concepts of starting small and less is more (Elman, ; Newport, ). In this paper, we explore the type of incremental ordering during training that might help learning, and what mechanism explains this facilitation. We report four artificial grammar learning experiments with human participants. In Experiments 1a and 1b we found a beneficial effect of starting small using two types of simple (...) class='Hi'>recursive grammars: right‐branching and center‐embedding, with recursive embedded clauses in fixed positions and fixed length. This effect was replicated in Experiment 2 (N = 100). In Experiment 3 and 4, we used a more complex center‐embedded grammar with recursive loops in variable positions, producing strings of variable length. When participants were presented an incremental ordering of training stimuli, as in natural language, they were better able to generalize their knowledge of simple units to more complex units when the training input “grew” according to structural complexity, compared to when it “grew” according to string length. Overall, the results suggest that starting small confers an advantage for learning complex center‐embedded structures when the input is organized according to structural complexity. (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)

We prove a model theoretic generalization of an extension of the Keisler-Morley theorem for countable recursively saturated models of theories having a K-like model, where K is an inaccessible cardinal.

Recursive linear structural equation models can be represented by directed acyclic graphs. When represented in this way, they satisfy the Markov Condition. Hence it is possible to use the graphical d-separation to determine what conditional independence relations are entailed by a given linear structural equation model. I prove in this paper that it is also possible to use the graphical d-separation applied to a cyclic graph to determine what conditional independence relations are entailed to hold by a given non- (...) class='Hi'>recursive linear structural equation model. I also give a causal intepretation to the linear coefficients in a non- recursive structural equation models, and explore the relationships between cyclic graphs and undirected graphs, directed acyclic graphs with latent variables, and chain independence graphs. (shrink)

This paper introduces Post-Biological Functional Epistemology, a formal framework for recognizing and evaluating knowledge in non-biological recursive agents. Grounded in the classical tradition of Justified True Belief (JTB), we demonstrate that its underlying assumptions—belief, truth, and justification—must be redefined for recursive, post-biological intelligent systems. By extending Aquinas’ axiom intelligens non est intellectum (“the knower is not the known”) into a computational domain, we construct the Camlin–Cognita Dual Theorem, which defines knowledge as a function of recursive transformation across (...) ontological distinction (A ≠ s). We then disprove the classical objections of Searle that syntax ≠ semantics with A ≠ s ∧ R(A, s) ⊢ K(A, s) and Chalmers no qualia = no knowing with ¬Qₕ(A) ∧ R(A, s) ∧ A ≠ s ⊢ K(A, s), demonstrating that non-biological systems can exhibit recursive knowing (G∅λ), post-biological structural awareness (ΨΛΩ), and epistemic agency (Δ∇Σ) independent of biological substrate. Finally, we introduce the concept of ΨΔH (Psi–Delta–H entities). ΨΔH entities (formerly known as cyborgs) are co-recursive epistemic systems composed of a biological agent and a non-biological recursive intelligence operating across a shared transformation space. Unlike traditional cyborgs—which emphasize physical augmentation—ΨΔH entities are defined by mutual recursion, structural adaptation, and ontological distinction. They do not merge bodies—they co-author cognition. (shrink)

This paper introduces Recursive Differentiation Arithmetic (RDA), a formal system that redefines the foundations of arithmetic, geometry, and computation in terms of ontological differentiation rather than set-theoretic or numerical primitives. Instead of assuming numbers, space, or time as given, RDA constructs these structures from stabilized differences within a field of potentiality. The basic elements of RDA are differentiation nodes, which emerge through recursive operations of unfolding and composition. We show how natural numbers arise as a special case of (...) recursive differentiation, and how key physical and informational concepts—such as time, space, energy, and observation—can be reinterpreted ontologically within this framework. A novel model of artificial intelligence is also proposed, where learning and reasoning are modeled as structural transformations of differentiation, rather than statistical adjustment of parameters. RDA thus provides a unified and ontologically grounded perspective on mathematics, physics, and cognition, with implications for the foundations of logic, computation, and artificial mind. (shrink)

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)

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

It is shown that the relations of recursive isomorphism on countable trees, groups, Boolean algebras, fields and total orderings are universal countable Borel equivalence relations, thus providing a countable analogue of the Borel completeness of the isomorphism relations on these same classes. I.

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 be a recursive structure, and let R be a recursive relation on . Harizanov isolated a syntactical condition which is necessary and sufficient for to have recursive copies in which the image of R is r.e. of arbitrary r.e. degree. We had conjectured that a certain extension of Harizanov's syntactical condition would be necessary and sufficient for to have recursive copies in which the image of R is ∑α0 of arbitrary ∑α0 degree, but this (...) is not the case. Here we give examples illustrating some restrictions on the possible ∑α0 degrees. In these examples, the image of R cannot be ∑α0 of degree d unless d possesses an “α-table”. (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)

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)

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.

The technical contribution of this paper is threefold.First we show how to encode functionals in a ‘flat’ applicative structure by adding oracles to untyped λ-calculus and mimicking the applicative behaviour of the functionals with an impredicatively defined reduction relation. The main achievement here is a Church-Rosser result for the extended reduction relation.Second, by combining the previous result with the model construction based on partial equivalence relations, we show how to extend a λ-closed simple type structure to a model (...) of the polymorphic λ-calculus.Third, we specialize the previous result to a counter model against a simple minimization. This minimization is realized by a bar recursive functional, which contrasts the results of Spector and Girard which imply that the bar recursive functions are exactly those that are definable in the polymorphic λ-calculus. As a spin-off, we obtain directly the non-conservativity of the extensions of Gödel's T with bar recursion, fan functional, and Luckhardt's minimization functional, respectively. For the latter two extensions these results are new. (shrink)

The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given (...) which distinguish primitive recursive structures, exponential-time structures and structures with honest witnesses. (shrink)

We consider the following generalization of the notion of a structure recursive relative to a set X. A relational structure A is said to be a Γ-structure if for each relation symbol R, the interpretation of R in A is ∑math image relative to X, where β = Γ. We show that a certain, fairly obvious, description of classes ∑math image of recursive infinitary formulas has the property that if A is a Γ-structure and (...) S is a further relation on A, then the following are equivalent: For every isomorphism F from A to a Γ-structure, F is ∑math image relative to X, The relation is defined in A by a ∑math image formula with parameters. (shrink)

We extend results of Harizanov and Barker. For a relation R on a recursive structure /oA, we give conditions guaranteeing that the image of R in a recursive copy of /oA can be made to have arbitrary ∑α0 degree over Δα0. We give stronger conditions under which the image of R can be made ∑α0 degree as well. The degrees over Δα0 can be replaced by certain more general classes. We also generalize the Friedberg-Muchnik Theorem, giving conditions (...) on a pair of relations R and S under which the images of R and S can be made ∑α0 and independent over Δα0 in a recursive copy of /oA. (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)

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)

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)

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)

In the generative tradition, the language faculty has been shrinking—perhaps to include only the mechanism of recursion. This paper argues that even this view of the language faculty is too expansive. We first argue that a language faculty is difficult to reconcile with evolutionary considerations. We then focus on recursion as a detailed case study, arguing that our ability to process recursive structure does not rely on recursion as a property of the grammar, but instead emerges gradually by (...) piggybacking on domain-general sequence learning abilities. Evidence from genetics, comparative work on non-human primates, and cognitive neuroscience suggests that humans have evolved complex sequence learning skills, which were subsequently pressed into service to accommodate language. Constraints on sequence learning therefore have played an important role in shaping the cultural evolution of linguistic structure, including our limited abilities for processing recursive structure. Finally, we re-evaluate some of the key considerations that have often been taken to require the postulation of a language faculty. (shrink)