Unrecognizable Sets of Numbers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Unrecognizable Sets of Numbers

Full text

Pdf (376 KB)

Source

Journal of the ACM (JACM) archive
Volume 13 , Issue 2 (April 1966) table of contents

Pages: 281 - 286

Year of Publication: 1966

ISSN:0004-5411

Authors

Marvin Minsky	Massachusetts Institute of Technology, Cambridge, Massachusetts and Both of Department of Electrical Engineering and Project MAC
Seymour Papert	Massachusetts Institute of Technology, Cambridge, Massachusetts and Both of Department of Electrical Engineering and Project MAC

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 39, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321328.321337 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	RABIN, M., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114-125.
	2	KIEENE, S.C. Representation of events in nerve nets and finite automata. In Automata Studies, Shannon, C. E., and McCarthy, J. (Eds.), Princeton U. Press, Princeton, N. J., 1956, pp. 3-41.
	3	Robert W. Ritchie, Finite Automata and the Set of Squares, Journal of the ACM (JACM), v.10 n.4, p.528-531, Oct. 1963 [doi>10.1145/321186.321196]

CITED BY 2

	J. Hartmanis , H. Shank, On the Recognition of Primes by Automata, Journal of the ACM (JACM), v.15 n.3, p.382-389, July 1968
	Marcel Paul Schutzenberger, A Remark on Acceptable Sets of Numbers, Journal of the ACM (JACM), v.15 n.2, p.300-303, April 1968