Theorem 1.1 (Tree equivalence): tree equivalence of HORS is undecidable and -complete, also for safe productive order-four schemes over
ProvedTreeEquivalenceHORS.Equivalence.theorem_1_1Tree equivalence of deterministic higher-order recursion schemes is undecidable and, more precisely, -complete (co-c.e.-complete) under total computable many-one reductions. This remains true when both schemes are required simultaneously to be safe and productive, to have order at most four, and to use the fixed ranked alphabet .
Precisely, each of the four languages of Section 3,
is co-c.e., every co-c.e. predicate on many-one reduces to it by a total computable function, and it is not computable.
The general language allows arbitrary alphabets, arbitrary finite orders and nonproductive schemes. The restricted languages impose their conditions on both schemes, and productivity is part of membership.
Differences from the source:
- reading: "Tree equivalence … is … Π⁰₁-complete …; this remains true when both schemes are required simultaneously to be safe and productive, to have order at most four, and to use Σ₂" → the conclusion stated for each of the four languages Eq_HORS, Eq_{4,Σ₂}, Eq^prod_{4,Σ₂}, Eq^{safe,prod}_{4,Σ₂} of Section 3; reason: these are the languages the paper defines for the headline and proves the theorem for (Sections 5.6, 6.4)
- encoding: Π⁰₁-complete under total computable many-one reductions; undecidable →
CoCEComplete P(REPredof the complement, andManyOneReducible A Pfor every co-c.e. A) and¬ ComputablePred P; reason: Mathlib's conventional computability notions on ℕ - encoding: standard computable injective encodings of finite syntax by natural numbers, with total computable decoders that return syntax or reject → the derived
Encodableinstances ofTy,Tm,HORS,Instr(and their products, lists, options); a code on whichEncodable.decodereturnsnoneis malformed; reason: the derived encoding is injective with a total, structurally recursive decoder; computability classes of predicates on ℕ do not depend on which such encoding is fixed - encoding: Σ₀ = {z:0, a:1, b:3}, Σ₂ = {e:0, d:2} →
sigma0 = [0, 1, 3](terminals 0 = z, 1 = a, 2 = b) andsigma2 = [0, 2](0 = e, 1 = d); reason: a ranked alphabet is its list of arities, terminals named by position
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Languages
namespace TreeEquivalenceHORS.Equivalence
/-- **Theorem 1.1 (Tree equivalence)** (printed p. 1 / PDF p. 3). Tree equivalence of deterministic
higher-order recursion schemes is undecidable and `Π⁰₁`-complete (co-c.e.-complete) under total
computable many-one reductions; this remains true when both schemes are required simultaneously
to be safe and productive, to have order at most four, and to use the alphabet `Σ₂ = {e : 0, d : 2}`.
Stated for each of the four languages of Section 3: `Eq_HORS`, `Eq_{4,Σ₂}`, `Eq^prod_{4,Σ₂}` and
`Eq^{safe,prod}_{4,Σ₂}`. -/
theorem theorem_1_1 :
(CoCEComplete EqHORS ∧ ¬ ComputablePred EqHORS) ∧
(CoCEComplete Eq4Sigma2 ∧ ¬ ComputablePred Eq4Sigma2) ∧
(CoCEComplete Eq4Sigma2Prod ∧ ¬ ComputablePred Eq4Sigma2Prod) ∧
(CoCEComplete Eq4Sigma2SafeProd ∧ ¬ ComputablePred Eq4Sigma2SafeProd) := by sorry
end TreeEquivalenceHORS.Equivalence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.