Lemma 5.7 (Productivity): both compiled schemes are productive
ProvedTreeEquivalenceHORS.Equivalence.lemma_5_7higher-order-recursion-schemesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1productivity
For every two-counter program and side , the compiled scheme is productive: its start term is productive to every depth. This includes the arithmetic observation subtrees, illegal candidate branches and branches whose signed weight is zero.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Compiler
Formal statement
namespace TreeEquivalenceHORS.Equivalence /-- **Lemma 5.7 (Productivity)** (printed p. 20 / PDF p. 22). Both compiled schemes are productive. -/ theorem lemma_5_7 (M : Machine) (side : Side) : (compile side M).Prod := by sorry end TreeEquivalenceHORS.Equivalence
Source
Mingkun Xiao, Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, STOC 2027 submission #421 (October 2026), source.pdf SHA-256 e875d09ced029e3f5cb114abba049e4a2b1bdaa9b064c98b0d71f2ec7451c7af, Lemma 5.7, printed p. 20 / PDF p. 22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.