Computable syntactic restrictions on encoded pairs of recursion schemes
ProvedTreeEquivalenceHORS.Equivalence.syntax_and_code_testscomputabilityrecursion-schemes
A total numerical test decides pair validity, the fixed binary alphabet and order bound when requested, and safety when requested. There is a computable numerical projection to the start term, and every successfully decoded pair re-encodes to its input code.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_Languages
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem syntax_and_code_tests :
(∃ q : ℕ → ℕ → Bool, Computable₂ q ∧ ∀ k n, q k n = true ↔
∃ G H : HORS, Encodable.decode n = some (G,H) ∧ ValidPair G H ∧
(0 < k → G.alphabet = sigma2 ∧ G.order ≤ 4 ∧ H.order ≤ 4) ∧
(k = 3 → G.Safe ∧ H.Safe)) ∧
(∃ start : ℕ → ℕ, Computable start ∧ ∀ G : HORS,
start (Encodable.encode G) = Encodable.encode (Tm.nt G.start)) ∧
(∀ n (G H : HORS), Encodable.decode n = some (G,H) → Encodable.encode (G,H) = n) := 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