Paper Info
Title
Unrecognizable Sets of Numbers
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 &pgr; A(n) be the number of members of A less than the integer n. It is shown that the asymptotic behavior of &pgr; 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 &pgr; P(n) @@@@ n/log n for large n, the set of integers A(k) of the form nk for which &pgr; A(k)n) @@@@ nP/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 | &pgr; A(n) — &pgr; A′(n) | ≤ 1, so that the asymptotic behaviors of the two distribution functions are essentially identical.
Year
DOI
Venue
1966
10.1145/321328.321337
J. ACM
Keywords
Field
DocType
important natural numerical set,asymptotic behavior,infinite regular set,Unrecognizable Sets,integers A,integer n,binary number,set P,distribution function,large n,log n
Integer,Discrete mathematics,Combinatorics,Computer science,Binary number
Journal
Volume
Issue
ISSN
13
2
0004-5411
Citations 
PageRank 
References 
12
12.43
2
Authors
2
Name
Order
Citations
PageRank
Marvin Minsky1407263.42
Seymour Papert216465.93