Lemma 5.9 (Binary output encoding): productive -schemes translate effectively to productive -schemes with
ProvedTreeEquivalenceHORS.Equivalence.lemma_5_9higher-order-recursion-schemesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1tree-encodings
There is an effective translation such that every productive HORS over is sent to a productive HORS over with
where is the constructor encoding of Equation (26); if is safe, then is safe. For any productive HORS over ,
The input schemes are arbitrary productive schemes over , of any order, not only compiler outputs.
Differences from the source:
- reading: "every productive HORS G over Σ₀" → every well-formed (
Valid) scheme G with alphabet Σ₀ andProd G; reason: a HORS in the source is always a well-formed scheme (Section 3) - encoding: the construction is effective / total computable →
Computable(Mathlib) of the induced map on natural-number codes: decode, apply the construction, encode (malformed codes go to the code ofnone); reason: the standard meaning of effectiveness of a syntax transformation under fixed encodings - encoding: possibly infinite ranked trees over Σ ∪ {⊥:0} → label functions
List ℕ → Labgiving at every addressterm c,botorabsent; reason: a ranked tree is determined by its labels at all finite addresses; infinite trees are included
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Encoding import Definitions.Def_TreeEquivalenceHORS_Equivalence_Syntax
Formal statement
namespace TreeEquivalenceHORS.Equivalence
/-- **Lemma 5.9 (Binary output encoding)** (printed p. 21 / PDF p. 23). There is an effective
translation `G ↦ G^E` such that every productive scheme `G` over `Σ₀` is sent to a productive
scheme over `Σ₂` with `ord(G^E) ≤ max{1, ord(G)}` and `BT(G^E) = E(BT(G))`, safe whenever `G` is
safe; and for productive `G, H` over `Σ₀`, `BT(G^E) = BT(H^E) ⟺ BT(G) = BT(H)`. -/
theorem lemma_5_9 :
∃ f : HORS → HORS,
Computable (fun n : ℕ => Encodable.encode ((Encodable.decode n : Option HORS).map f)) ∧
(∀ G : HORS, G.Valid → G.alphabet = sigma0 → G.Prod →
(f G).Valid ∧ (f G).alphabet = sigma2 ∧ (f G).Prod ∧ (f G).order ≤ max 1 G.order ∧
(f G).BT = encAt G.BT ∧ (G.Safe → (f G).Safe)) ∧
∀ G H : HORS, G.Valid → H.Valid → G.alphabet = sigma0 → H.alphabet = sigma0 →
G.Prod → H.Prod → ((f G).BT = (f H).BT ↔ G.BT = H.BT) := 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.9, printed p. 21 / PDF p. 23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.