Two-Way Counter Machines and Diophantine Equations

✍ Scribed by Gurari, Eitan M.; Ibarra, Oscar H.

• Book ID: 115461416
• Publisher: Association for Computing Machinery
• Year: 1982
• Tongue: English
• Weight: 548 KB
• Volume: 29
• Category: Article
• ISSN: 0004-5411
• DOI: 10.1145/322326.322340

✦ Synopsis

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.