Lemma 6.2 (Exact prefixes): the reader returns the exact label, or absence, and exact prefixes are total computable
ProvedTreeEquivalenceHORS.Equivalence.lemma_6_2computabilitydomain-theoryhigher-order-recursion-schemesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For every well-formed scheme , closed ground term and finite address , the reader of Section 6.4 terminates and returns exactly the label, the bottom node, or the absence at address in . Consequently the exact prefixes of every specified finite depth are total computable: some total computable function maps the codes of , and to the code of whenever is well formed and closed ground.
No productivity, safety or order bound is assumed; empty terminal alphabets are included.
Differences from the source:
- encoding: the reader returns a label, ⊥ or †, and terminates →
readis a Mathlib partial computation (Part Lab); "terminates and returns ℓ" isread G t w = Part.some ℓ; reason: termination of the budget search is a conclusion, so the reader is defined as a partial function - encoding: exact prefixes of any specified finite depth are total computable → there is a
Computable f : ℕ × ℕ × ℕ → ℕwithf (encode G, encode t, d) = encode (Pref G t d)for every valid G and closed ground t; reason: computability of the prefix map on codes under the 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
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_FiniteSemantics
Formal statement
namespace TreeEquivalenceHORS.Equivalence
/-- **Lemma 6.2 (Exact prefixes)** (printed p. 25 / PDF p. 27). For every well-formed `G`, closed
ground `t` and finite address `w`, the reader `read_G(t, w)` terminates and returns exactly the
label, bottom node or absence at `w` in `BT_G(t)`. Consequently the exact prefixes
`Pref(G, t, d)` of every finite depth `d` are total computable from the codes of `G`, `t` and `d`. -/
theorem lemma_6_2 :
(∀ G : HORS, G.Valid → ∀ t : Tm, G.typeOf [] t = some .o →
∀ w : List ℕ, G.read t w = Part.some (G.BTat t w)) ∧
∃ f : ℕ × ℕ × ℕ → ℕ, Computable f ∧
∀ (G : HORS) (t : Tm) (d : ℕ), G.Valid → G.typeOf [] t = some .o →
f (Encodable.encode G, Encodable.encode t, d) = Encodable.encode (G.Pref t d) := 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 6.2, printed p. 25 / PDF p. 27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.