A total numerical algorithm computes the finite-semantics head test
ProvedTreeEquivalenceHORS.Equivalence.finite_head_test_computablecomputabilityrecursion-schemes
There is a total computable Boolean function on pairs of numerical scheme and term codes. On every valid scheme and closed ground term it returns true exactly when the specified final finite denotation is the positive bit.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_FiniteSemantics
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem finite_head_test_computable :
∃ b : ℕ × ℕ → Bool, Computable b ∧ ∀ (G : HORS) (t : Tm), G.Valid → G.typeOf [] t = some .o →
(b (Encodable.encode G, Encodable.encode t) = true ↔ G.den [] G.etaStar [] t = .bit true) := 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