Total computability of the exact finite prefix on encoded inputs
ProvedTreeEquivalenceHORS.Equivalence.exact_prefix_algorithmcomputabilityrecursion-schemes
There is a total computable function on a scheme code, a term code, and a depth, returning the encoded exact prefix whenever the scheme is valid and the term is closed and ground.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_FiniteSemantics
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem exact_prefix_algorithm :
∃ 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.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