Finite prefixes detect failure of productivity
ProvedTreeEquivalenceHORS.Equivalence.productive_iff_prefixes_no_bottomcomputabilityrecursion-schemes
A closed ground term in a valid scheme is productive at every depth exactly when no finite prefix contains a bottom node.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_FiniteSemantics
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem productive_iff_prefixes_no_bottom (G : HORS) (vg : G.Valid) (t : Tm)
(ht : G.typeOf [] t = some .o) :
(∀ d, G.ProdDepth t d) ↔ ∀ d, ∀ p ∈ G.Pref t d, p.2 ≠ .bot := by sorry
end TreeEquivalenceHORS.EquivalenceSource
Mingkun Xiao and Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, §§3 and 5.6. https://arxiv.org/html/2610.39678v1