Recursive Properties of Abstract Complexity Classes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Recursive Properties of Abstract Complexity Classes

Full text

Pdf (643 KB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 2 (April 1972) table of contents

Pages: 296 - 308

Year of Publication: 1972

ISSN:0004-5411

Authors

L. H. Landweber	Computer Science Department, University of Wisconsin, 1210 West Dayton Street, Madison, WI
E. L. Robertson	University of Wisconsin, Madison, Wisconsin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 15, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/321694.321702 What is a DOI?

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	BORODIN, A. Complexity classes of recursive functions and the existence of complexity gaps. Conf. Record of ACM Syrup. on Theory of Computing, Marina del Rey, Calif., May 1969, pp. 67 78.
	3	DAVIS, MARTIN. Computability and Unsolvability. McGraw-Hill, New York, 1958.
	4	DEKKER, J. C. E., AND MYIfILL, J. Some theorems oil classes of recursively enmnerable sets. Tra~s. Amer. Math. Soc. 89 (Sept. 1958), 25-59.
	5	HARTMANIS, J ., AND STEARNS, R .E . On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (May 1965), 285 306.
	6	F. D. Lewis, Unsolvability considerations in computational complexity, Proceedings of the second annual ACM symposium on Theory of computing, p.22-30, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805145]
	7	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 [doi>10.1145/800169.805423]
	8	POST, EMIL L. Recursively enumerable sets of positive integers and their decision problems. Bnll. Amer. Math. Soc. 50 (1944), 284-316.
	9	RicE, H.G. Classes of recursively enumerable sets and their decision problems. Trans. Amer. Soc. 89 (March 1953), 25-59.
	10	RICE, H. G. On completely recursively enumerable classes and their key arrays. J . Symbolic Logic 21, 3 (Sept. 1956), 304-341.
	11	Edward L. Robertson, Complexity classes of partial recursive functions (Preliminary Version), Proceedings of the third annual ACM symposium on Theory of computing, p.258-266, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805055]
	12	RO(~ERS, H. G()del numberings of partial recursive functions. J. Symbolic Lo(lic 23, 3 (Sept. 1958), 331-341.
	13	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]
	14	YOUNG, P .R . A note OR dense and non-dense families of complexity classes. Tech. Rep. 40, Comput. Sci. I)ep., Purdue U., Lafayette, Ind., Aug. 1969.
	15	McCREIGHT, E.M. Ph.D. thesis, Carnegie-Mellon U., Pittsburgh, Pa., 1969.

CITED BY 6

	Edward L. Robertson, Structure of complexity in the weak monadic second-order theories of the natural numbers, Proceedings of the sixth annual ACM symposium on Theory of computing, p.161-171, April 30-May 02, 1974, Seattle, Washington, United States
	Shimon Even , Alan L. Selmen , Yacov Yacobi, Hard-core theorems for complexity classes, Journal of the ACM (JACM), v.32 n.1, p.205-217, Jan. 1985
	John Gill , Manuel Blum, On Almost Everywhere Complex Recursive Functions, Journal of the ACM (JACM), v.21 n.3, p.425-435, July 1974
	Andrea Asperti, The intensional content of Rice's theorem, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Leonard Bass , Paul Young, Ordinal Hierarchies and Naming Complexity Classes, Journal of the ACM (JACM), v.20 n.4, p.668-686, Oct. 1973
	Thomas Zeugmann , Sandra Zilles, Learning recursive functions: A survey, Theoretical Computer Science, v.397 n.1-3, p.4-56, May, 2008