Classification of the four tree-equivalence languages from depth tests and a uniform reduction
ProvedTreeEquivalenceHORS.Equivalence.theorem_1_1_of_tests_and_compilercomputabilityrecursion-schemes
Computable tests at every depth and one computable reduction of universal nonhalting into valid, binary, order-four, safe, productive pairs suffice for co-c.e.-completeness and undecidability of all four equivalence languages.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_Languages
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem theorem_1_1_of_tests_and_compiler
(tests : ∀ P ∈ [EqHORS, Eq4Sigma2, Eq4Sigma2Prod, Eq4Sigma2SafeProd],
∃ test : ℕ → ℕ → Bool, Computable₂ test ∧ ∀ n, P n ↔ ∀ d, test n d = true)
(F : ℕ → HORS × HORS) (hF : Computable (fun n => Encodable.encode (F n)))
(good : ∀ n, ∀ G ∈ [(F n).1, (F n).2],
G.Valid ∧ G.alphabet = sigma2 ∧ G.order ≤ 4 ∧ G.Prod ∧ G.Safe)
(correct : ∀ n, (¬ (Nat.Partrec.Code.eval (Denumerable.ofNat Nat.Partrec.Code n.unpair.1) n.unpair.2).Dom) ↔ (F n).1.BT = (F n).2.BT) :
(CoCEComplete EqHORS ∧ ¬ ComputablePred EqHORS) ∧
(CoCEComplete Eq4Sigma2 ∧ ¬ ComputablePred Eq4Sigma2) ∧
(CoCEComplete Eq4Sigma2Prod ∧ ¬ ComputablePred Eq4Sigma2Prod) ∧
(CoCEComplete Eq4Sigma2SafeProd ∧ ¬ ComputablePred Eq4Sigma2SafeProd) := 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