Scoped full-termination conjecture for pure recursive calculi

Let RR be an operator-only Pure Recursive Calculus with a recursor rule of the form

rec(b,s,σ(n))f(s,rec(b,s,n)).\mathrm{rec}(b,s,\sigma(n))\to f(s,\mathrm{rec}(b,s,n)).

The step argument ss is unrestricted, and an internally definable measure means a measure satisfying Definition~, without external axioms, imported arithmetic, or meta-level encodings. Scoped full-termination conjecture. No internally definable measure currently known proves termination of such an RR for the full calculus when ss is unrestricted. The audited family excludes additive and polynomial methods, as well as standard path orders such as LPO, RPO, and MPO when they rely on the universal subterm property f(t)>tf(t)>t as an imported structural axiom.

This is a scoped impossibility claim rather than a theorem of absolute nonexistence: the cited machine-checked barriers cover the audited families, while the canonical computable SafeStep certificate remains available as an internal measure for the relevant restricted setting. Whether some other internally definable method proves full-calculus termination under unrestricted duplication remains open.

Sources & referencesView supporting material

Primary source

Moses Rahnama, “The Orientation Boundary for Step-Duplicating Recursors: Mechanized Impossibility, Escape, and Certification”, arXiv:2512.00081 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.