Two-Way Counter Machines and Diophantine Equations
Eitan M. Gurari, Óscar H. Ibarra · Journal of the ACM · 1982
Let Q be the class of determmistlc two-way l-counter machines accepting only bounded languages Each machine m Q has the property that m every accepting computation, the counter makes at most a fixed number of reversals It is shown that the emptiness problem for Q is decidable.When the counter is unrestricted or the machine is prowded with two reversal-bounded counters, the emptiness problem becomes undecidable.The decidability of the emptmess problem for Q is useful in proving the solvabdity of some number-theoreuc problems It can also be used to prove that the language L = {u~u21 ~ >-0} cannot be accepted by any machme in Q (u~ and u2 are &stmct symbols).The proof techmque ~s new m that it does not employ the usual "pumpmg," "counting," or "thagonal" argument.Note that L can be accepted by a deterministic two-way machine with two counters, each of which makes exactly one reversal Categories and Subject Descriptors.F. 1.1 IComputation by Abstract Devicesl: Modds of