Double Recursion¶
A nested two-level numerical recursion scheme that can feed earlier values into lower-row functions while preserving well-founded dependencies.
Core Idea¶
In the nested numerical convention, double recursion defines a natural-number family through an initial row, a row-start rule and a step that can feed an earlier current-row value into a lower-row function. Recursive accesses decrease the outer index, or keep it and decrease the inner one; parameters need not decrease. Finite substitution terms and total helpers give totality, effective helpers additionally support computation, and some instances exceed primitive recursion while others remain primitive recursive.[^ref-eb982a4bdfb8]
Scope of Application¶
Péter's original article supplies two unlike mathematical constructions within numerical recursion theory, rather than two experiments or independent replications:
- Majorization: A nested family supplies rows that bound primitive-recursive functions.[^ref-eb982a4bdfb8]
- Uniform evaluation: A different construction encodes outputs of an enumeration of binary primitive-recursive functions.[^ref-eb982a4bdfb8]
Clarity¶
Two arguments or two self-calls alone do not establish this scheme. Identify the ranked indices, any parameters, given helpers, complete initial row, next-row start and permitted nested step. “Earlier” concerns the rank pair, so a lower-row call can use a much larger numerical argument. Péter's historical nichtrekursiv means outside the restricted class now called primitive recursive; it does not mean uncomputable.[^ref-eb982a4bdfb8]
Manages Complexity¶
Separate the reusable dependency pattern from each example's output. For the majorizing family, renamed \(M\), the three clauses are
The previous current-row value becomes an input to a lower-row function. Each fixed row is primitive recursive, but the uniform family is not; each unary primitive-recursive function has some row above it at every input. A compact rule does not promise small values or efficient evaluation.[^ref-eb982a4bdfb8]
Abstract Reasoning¶
Use row induction: with the whole initial row and total helpers given, establish each next row's start and then its inner steps; decreasing ranks cannot repair a divergent helper. Péter's parameterized carrier \(\psi(m,n,a)\) uses explicit prime-power coding and selectors to pass earlier current-row values through lower-row calls, with decoding recovering a uniform evaluator whose non-primitive-recursiveness has a separate diagonal proof.[^ref-eb982a4bdfb8]
Knowledge Transfer¶
Transfer between the majorant and coded evaluator preserves the six roles while changing the helpers and output meaning. The dependency guarantee uses a well-founded relation: every nonempty set of rank pairs has a member with least outer coordinate and then least inner coordinate in that row; the scheme is not itself a binary relation. Parameters, helper totality and effectivity remain separate; constant-zero clauses may remain primitive recursive, while Ackermann functions, mutual recursion and numberings have different identities.[^ref-eb982a4bdfb8]
Relationships to Other Abstractions¶
Current abstraction Double Recursion Domain-specific
Parents (1) — more general patterns this builds on
-
Double Recursion presupposes Well-founded set Domain-specific
Double Recursion presupposes the well-founded lexicographic relation on its two natural-number recursion indices.
Hierarchy path (1) — routes to 1 parentless root
- Double Recursion → Well-founded set
Neighborhood in Abstraction Space¶
Double Recursion sits in a sparse region of the domain-specific corpus (91st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Indiscernibles — 0.80
- Cylindrification — 0.80
- Natural Number — 0.79
- Slow-Growing Hierarchy — 0.79
- Factorial Number System — 0.78
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-eb982a4bdfb8]: Rózsa Péter, “Konstruktion nichtrekursiver Funktionen,” Mathematische Annalen 111 (1935), 42–60. DOI: 10.1007/BF01472200. Full original published-page facsimile, 19 pages, retained from a third-party mirror. General term conventions and historical usage: printed pp. 42–45. Prime/exponent conventions: p. 45. Enumeration and diagonal argument: pp. 48–49. General scheme: p. 50, eq. (5). Evaluator reduction, helpers and coding: pp. 51–53, especially eqs. (8)–(9); these are PDF pp. 10–12. Majorization and the renamed \(M\): §3, especially pp. 56 and 59; \(0^0=1\): p. 58. The general functional-slot display and role tables are explanatory analysis; the numerical constructions and helper formulas follow the original article. Both positive examples are formal constructions, not experimental studies.