Lemma 4.2 (Control correspondence):
ProvedTreeEquivalenceHORS.Equivalence.lemma_4_2counter-machineshalting-problemp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For every two-counter program (including the empty one),
where is halting from under the source step relation.
This identifies source halting with a halting candidate of nonzero weight, the event the two compiled schemes disagree on.
Differences from the source:
- encoding: candidate words over {1, 2}; virtual configurations in ℕ × ℤ² →
List ChoicewithChoice.one= 1,Choice.two= 2, read left to right; configurationsℕ × ℤ × ℤ; δ (undefined outside I_M) returns its argument there; reason: the value of δ outside I_M is never used on candidates, which extend only active prefixes
Preamble
import Mathlib import Definitions.Def_TreeEquivalenceHORS_Equivalence_Machines
Formal statement
namespace TreeEquivalenceHORS.Equivalence
/-- **Lemma 4.2 (Control correspondence)** (printed p. 13 / PDF p. 15).
`M↓ ⟺ ∃ v ∈ C_M, pc_M(v) ∉ I_M ∧ W_M(v) ≠ 0`. -/
theorem lemma_4_2 (M : Machine) :
M.Halts ↔ ∃ v : List Choice, M.IsCand v ∧ ¬ M.Active (M.pc v) ∧ M.weight v ≠ 0 := by sorry
end TreeEquivalenceHORS.Equivalence
Source
Mingkun Xiao, Yixuan Sun, Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable, STOC 2027 submission #421 (October 2026), source.pdf SHA-256 e875d09ced029e3f5cb114abba049e4a2b1bdaa9b064c98b0d71f2ec7451c7af, Lemma 4.2, printed p. 13 / PDF p. 15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.