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

  • 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$ 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$ Mar 6 '19 at 20:30
  • $\begingroup$ More on counter automata vs pushdown automata in: Which languages are recognized by one-counter machines? $\endgroup$ Mar 7 '19 at 1:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.