Halting is equivalent to a terminal disagreement in the intermediate schemes
ProvedTreeEquivalenceHORS.Equivalence.halts_iff_compiled_observationscomputabilityrecursion-schemes
For every two-counter machine started with both counters zero, the machine halts if and only if there is a finite address at which its left and right compiled schemes expose distinct terminals of the intermediate alphabet. The compared observations are made from the respective start symbols at the same address.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_Compiler
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem halts_iff_compiled_observations (M : Machine) :
M.Halts ↔ ∃ (w : List ℕ) (a b : ℕ), a < sigma0.length ∧ b < sigma0.length ∧ a ≠ b ∧
(compile .L M).Obs (.nt (compile .L M).start) w a ∧
(compile .R M).Obs (.nt (compile .R M).start) w b := by sorry
end TreeEquivalenceHORS.EquivalenceSource
Mingkun Xiao and Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, Theorem 5.8 (operational correspondence clause), printed p. 20. https://arxiv.org/html/2610.39678v1#S5.SS5