Counter Machine (Halting Problem)

How can we show that Halting Problem for one-counter additive machines is decidable ?

• What is a "one-counter additive machine"? – dkaeae Mar 6 at 12:13
• Machines with an integer storage, and operations +1, -1 and zero test, can be emulated by a push-down automaton. Store the absolute value of the counter on the stack, and the sign in the finite state of the PDA. – Hendrik Jan Mar 6 at 14:31
• Please edit the question to add a reference to "counter machine" and the definition of "a one-counter additive machine". @HendrikJan's explanation is nice; however, I am afraid it is neither formal nor detailed enough. – Apass.Jack Mar 6 at 19:22
• I deleted my answer because I'd misread the question and suggested how to prove that the problem is undecidable, which is no use. Thanks @Apass.Jack for pointing that out. – David Richerby Mar 6 at 20:30
• More on counter automata vs pushdown automata in: Which languages are recognized by one-counter machines? – Hendrik Jan Mar 7 at 1:56

Suppose that the increments are $$+1, -1$$; the number of states of the machine is $$m$$ and the current value of the counter is $$n$$.
You can notice that if the counter reaches $$n+m+1$$ without hitting the $$0$$, then by the pigeonhole principle the machine from value $$n$$ to $$n+m+1$$ has entered the same state $$s_i$$ two times ($$s_i \to ... \to s_i$$), and the difference in the counter value is positive; so it will continue to repeat the same loop and increase the counter.
After hitting the $$0$$ - for the same reason - if the counter reaches $$m+1$$ then the machine will never halt.
So it's enough to simulate the machine up to $$m(n+m+1)$$ steps; if it doesn't halt in that time it will never halt: it will loop forever on the same values $$(s_i,c_j) \to ... \to (s_i,c_j)$$ or increase forever the counter: $$(s_i,c_j) \to ...\to (s_i,c_k) \to ...;\; c_k > c_j+m$$ .
If the increments are $$\pm v, v \in [1,h]$$ then the machine can be reduced to an equivalent one with $$\pm 1$$ increments.