Theorem 5.8 (Intermediate compilation): is effective, safe, productive, of order , and iff the schemes disagree at some address
ProvedTreeEquivalenceHORS.Equivalence.theorem_5_8compilerscomputabilityhigher-order-recursion-schemesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
The construction is effective and produces well-formed, safe, productive schemes of order at most four over . Moreover, writing for the start symbol of each scheme,
This is the lower-bound reduction before the final change of alphabet.
Differences from the source:
- 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: standard computable injective encodings of finite syntax by natural numbers, with total computable decoders that return syntax or reject → the derived
Encodableinstances ofTy,Tm,HORS,Instr(and their products, lists, options); a code on whichEncodable.decodereturnsnoneis malformed; reason: the derived encoding is injective with a total, structurally recursive decoder; computability classes of predicates on ℕ do not depend on which such encoding is fixed - encoding: Σ₀ = {z:0, a:1, b:3}, Σ₂ = {e:0, d:2} →
sigma0 = [0, 1, 3](terminals 0 = z, 1 = a, 2 = b) andsigma2 = [0, 2](0 = e, 1 = d); reason: a ranked alphabet is its list of arities, terminals named by position
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Compiler
Formal statement
namespace TreeEquivalenceHORS.Equivalence
/-- **Theorem 5.8 (Intermediate compilation)** (printed p. 20 / PDF p. 22). The construction
`M ↦ (G^L_M, G^R_M)` is effective (its action on codes is total computable) and produces
well-formed safe productive schemes of order at most four over `Σ₀`; moreover
`M↓ ⟺ ∃ w ∈ ℕ* ∃ a, b ∈ Σ₀, a ≠ b ∧ Obs_{G^L_M}(S, w, a) ∧ Obs_{G^R_M}(S, w, b)`. -/
theorem theorem_5_8 :
Computable (fun n : ℕ => Encodable.encode
((Encodable.decode n : Option Machine).map fun M => (compile .L M, compile .R M))) ∧
(∀ (M : Machine) (side : Side),
(compile side M).Valid ∧ (compile side M).Safe ∧ (compile side M).Prod ∧
(compile side M).alphabet = sigma0 ∧ (compile side M).order ≤ 4) ∧
∀ M : Machine, M.Halts ↔
∃ (w : List ℕ) (a b : ℕ), a < sigma0.length ∧ b < sigma0.length ∧ a ≠ b ∧
(compile .L M).Obs (.nt (compile .L M).start) w a ∧
(compile .R M).Obs (.nt (compile .R M).start) w b := 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, Theorem 5.8, printed p. 20 / PDF p. 22
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.