Unrecognizable Sets of Numbers

Publisher Website
Google Scholar
Abstract
When is a set A of positive integers, represented as binary numbers, “regular” in the sense that it is a set of sequences that can be recognized by a finite-state machine? Let π A ( n ) be the number of members of A less than the integer n . It is shown that the asymptotic behavior of π A ( n ) is subject to severe restraints if A is regular. These constraints are violated by many important natural numerical sets whose distribution functions can be calculated, at least asymptotically. These include the set P of prime numbers for which π P ( n ) @@@@ n /log n for large n , the set of integers A ( k ) of the form n k for which π A ( k ) n ) @@@@ n P/k , and many others. The technique cannot, however, yield a decision procedure for regularity since for every infinite regular set A there is a nonregular set A′ for which | π A ( n ) — π A′ ( n ) | ≤ 1, so that the asymptotic behaviors of the two distribution functions are essentially identical.

This publication has 2 references indexed in Scilit: