Speed-ups by changing the order in which sets are enumerated (Preliminary Version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Speed-ups by changing the order in which sets are enumerated (Preliminary Version)

Full text

Pdf (286 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the first annual ACM symposium on Theory of computing table of contents

Marina del Rey, California, United States

Pages: 89 - 92

Year of Publication: 1969

Author

Paul R. Young

Purdue University, Lafayette, Indiana

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 12, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/800169.805424 What is a DOI?

ABSTRACT

In a suitably general context, the following analogue of the Blum Speed-up Theorem is proven: There are some infinite sets which are so difficult to enumerate that, given any order for enumerating the set, there is some other order, and some one method of enumerating the set in this second order which is much faster than any method of enumerating the set in the first ordering. It may be possible to interpret this result as a statement about the relative merits of “hardware” vs. “programming” speed-ups. The proof itself is one of the first nontrivial applications of priority methods to questions of computational complexity. As such, it perhaps represents an advance in bringing the results and techniques of contemporary “pure” recursion theory to bear on questions of computational complexity. In this paper we shall prove, in a suitably general context, the following analogue of the Blum Speed-up Theorem, [B1]: There are some infinite sets which are so difficult to enumerate that, given any order for enumerating the set, there is some other order, and some one method of enumerating the set in this second order which is much faster than any method of enumerating the set in the first ordering.

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	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	2	Blum, Manuel, On the size of machines, Inf. and Control, 11 (1967), 257-265.
	3	Meyer, A. R., and Fischer, P.C., On computational speed-up, to appear.
	4	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	5	Paul R. Young, Toward a Theory of Enumerations, Journal of the ACM (JACM), v.16 n.2, p.328-348, April 1969 [doi>10.1145/321510.321525]

CITED BY 3

	Manuel Blum, On Effective Procedures for Speeding Up Algorithms, Journal of the ACM (JACM), v.18 n.2, p.290-305, April 1971
	Robert L. Constable, The Operator Gap, Journal of the ACM (JACM), v.19 n.1, p.175-183, Jan. 1972
	E. M. McCreight , A. R. Meyer, Classes of computable functions defined by bounds on computation: Preliminary Report, Proceedings of the first annual ACM symposium on Theory of computing, p.79-88, May 05-07, 1969, Marina del Rey, California, United States