Lemma 5.6 (Operational correspondence):
ProvedTreeEquivalenceHORS.Equivalence.lemma_5_6compilershigher-order-recursion-schemesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a closed argument tuple with . Then for every natural number (normalized to ), every address and every terminal ,
This turns the head-rewriting behaviour of the compiled scheme into the explicit output trees of Equation (23), including padding and absent addresses.
Differences from the source:
- encoding: V_o = partial maps ℕ* ⇀ Σ₀ with † for undefined →
Val .o = List ℕ → Option (Fin 3),none= †,Fin 3indexing z, a, b; reason: same set of partial maps
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Compiler
Formal statement
namespace TreeEquivalenceHORS.Equivalence
/-- **Lemma 5.6 (Operational correspondence)** (printed p. 19 / PDF p. 21). If `Reg_m(t⃗; R)`, then for
every address `w` and terminal `a` of `Σ₀`, `Obs_{G^⋄_M}(F_î t⃗, w, a) ⟺ T^⋄(m, i, R)(w) = a`,
for every natural `i` (normalized to `î`). -/
theorem lemma_5_6 (side : Side) (M : Machine) (m i : ℕ) (t : StateArgs) (R : PairState)
(hR : Reg (compile side M) m t R) (w : List ℕ) (a : Fin 3) :
(compile side M).Obs (callF M i t.toList) w a.val ↔ Tmap side M m i R w = some a := 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.6, printed p. 19 / PDF p. 21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.