Nonhalting is equivalent to equality of the two intermediate value trees
ProvedTreeEquivalenceHORS.Equivalence.nonhalting_iff_compiled_tree_equalitycomputabilityrecursion-schemes
For every zero-start two-counter machine, nonhalting is equivalent to equality of the value trees produced by its left and right intermediate schemes.
Preamble
import Definitions.Def_TreeEquivalenceHORS_Equivalence_Compiler
Formal statement
namespace TreeEquivalenceHORS.Equivalence
theorem nonhalting_iff_compiled_tree_equality (M : Machine) :
¬ M.Halts ↔ (compile .L M).BT = (compile .R M).BT := 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