Abstract
It is known that the set of powers of two is recognizable by a finite automaton if the notational base used for representing numbers is itself a power of two but is unrecognizable in all other bases. On the other hand, the set of multiples of two is recognizable no matter what the notational base. It is shown that the latter situation is the exception, the former the rule: the only sets recognizable independently of base are those which are ultimately periodic; others, if recognizable at all, are recognizable only in bases which are powers of some fixed positive integer.
Similar content being viewed by others
References
J. R. Büchi, Weak second-order arithmetic and finite automata,Z. Math. Logik Grundlagen Math. 6 (1960), 66–92.
J. W. S. Cassels,An Introduction to Diophantine Approximation, Cambridge University Press, 1957.
M. Minsky andS. Papert, Unrecognizable sets of numbers,J. Assoc. Comput. Mach. 13 (1966), 281–286.
M. O. Rabin andD. Scott, Finite automata and their decision problems,IBM J. Res. Develop. 3 (1959), 114–125.
Author information
Authors and Affiliations
Additional information
A somewhat weaker theorem, namely, that a set which is recognizable inn-ary notation for alln ≥ 2 is necessarily ultimately periodic, has been established independently by J. Nievergelt using arguments which are simpler than those used here. The proof of the stated theorem given here is itself a substantial simplification over an earlier proof of mine which appeared as IBM Research Note NC-577, “Sets Definable by Finite Automata-III”, Jan. 1966. The second formulation of the theorem was pointed out by the referee.
Rights and permissions
About this article
Cite this article
Cobham, A. On the base-dependence of sets of numbers recognizable by finite automata. Math. Systems Theory 3, 186–192 (1969). https://doi.org/10.1007/BF01746527
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01746527