Correctness of the finite-address reader from head adequacy
ProvedTreeEquivalenceHORS.Equivalence.exact_read_of_head_adequacycomputabilityrecursion-schemes
For a valid scheme satisfying head adequacy on its closed ground terms, the address reader terminates and returns the corresponding label of the value tree.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_FiniteSemantics
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem exact_read_of_head_adequacy {G : HORS} (hG : G.Valid)
(adequate : ∀ t : Tm, G.typeOf [] t = some .o →
(G.den [] G.etaStar [] t = .bit true ↔ ∃ c us, G.HeadConv t c us))
(t : Tm) (ht : G.typeOf [] t = some .o) (w : List ℕ) :
G.read t w = Part.some (G.BTat t w) := by sorry
end TreeEquivalenceHORS.EquivalenceSource
Mingkun Xiao and Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, §§3 and 5.6. https://arxiv.org/html/2610.39678v1