§3.2 (Minsky) — halting is undecidable for 2-counter machines
ProvedDistLTLSynth.Char.section_3_2_minskycomputabilitycounter-machinesp2o-gran-per-chapterp2o-plan-paperp2o-v1
The set of (codes of) 2-counter machines whose run from reaches a halting state is not computable:
This is the cited result [Min67] from which the undecidability direction of Theorem 1.2 reduces.
Differences from the source:
- encoding: 2-counter machines as inputs of a decision problem → CMCode = (s, q₀, F, Δ) with states Fin (s+1); out-of-range numbers read modulo, missing instructions read as a default increment; reason: every finite 2-counter machine is, up to renaming its states, described by a code, and decoding is primitive recursive
- encoding: undecidable → ¬ ComputablePred; reason: Mathlib's notion
Preamble
import Mathlib import Definitions.Def_DistLTLSynth_Char_CounterMachine
Formal statement
namespace DistLTLSynth.Char
/-- §3.2 ([Min67]): halting (from the zero configuration) is undecidable for 2-counter
machines, given by their finite descriptions. -/
theorem section_3_2_minsky :
¬ ComputablePred (fun c : CMCode => (c.toMachine 2 (by norm_num)).Halts) := by sorry
end DistLTLSynth.Char
Source
Bollig, Bouyer-Decitre, Függer, Ghosh, Nowak, Sznajder, Distributed LTL Synthesis under Arbitrary Message Adversaries, STOC 2027 submission (PDF sha256 71476b49…), p. 8 (PDF 9), §3.2 (citing [Min67, p. 255–258])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.