How can we show that Halting Problem for one-counter additive machines is decidable ?
$\begingroup$
$\endgroup$
-
4$\begingroup$ What is a "one-counter additive machine"? $\endgroup$ – dkaeae Mar 6 '19 at 12:13
-
$\begingroup$ 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. $\endgroup$ – Hendrik Jan Mar 6 '19 at 14:31
-
3$\begingroup$ 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. $\endgroup$ – John L. Mar 6 '19 at 19:22
-
$\begingroup$ 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. $\endgroup$ – David Richerby Mar 6 '19 at 20:30
-
$\begingroup$ More on counter automata vs pushdown automata in: Which languages are recognized by one-counter machines? $\endgroup$ – Hendrik Jan Mar 7 '19 at 1:56
$\begingroup$
$\endgroup$
A simple way is the following:
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.
