Tree equivalence is undecidable for all four scheme languages
ProvedTreeEquivalenceHORS.Equivalence.four_tree_equivalence_languages_undecidablecomputabilityrecursion-schemes
Each of the four tree-equivalence languages is undecidable and every co-c.e. predicate many-one reduces to it. The same computable map works for all four, and produces safe, productive order-at-most-four pairs over the fixed binary alphabet.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_Languages
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem four_tree_equivalence_languages_undecidable :
∀ P ∈ [EqHORS, Eq4Sigma2, Eq4Sigma2Prod, Eq4Sigma2SafeProd],
(∀ A : ℕ → Prop, CoCE A → A ≤₀ P) ∧ ¬ ComputablePred P := 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