Simple counter machines and number-theoretic problems

摘要

The class of deterministic two-way finite automata augmented by reversal-bounded counters operating on inputs over a one-letter alphabet is studied. It is shown that every machine in this class can effectively be reduced to an equivalent (ordinary) finite automaton. Thus, all questions about finite automata that are decidable are also decidable when asked about machines in this class. Applications to some number-theoretic problems are given.