An Example of Information and Computation Resource Trade-Off

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Example of Information and Computation Resource Trade-Off

Full text

Pdf (589 KB)

Source

Journal of the ACM (JACM) archive
Volume 20 , Issue 4 (October 1973) table of contents

Pages: 687 - 695

Year of Publication: 1973

ISSN:0004-5411

Author

Robert P. Daley

Committee on the Information Sciences, The University of Chicago, Chicago, Illinois

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

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/321784.321794 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	BARZDIN, J. Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set. Soviet Math. Dokl. 9, 5 (1968), 1251-1254.
	2	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]
	3	Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM (JACM), v.13 n.4, p.547-569, Oct. 1966 [doi>10.1145/321356.321363]
	4	Gregory J. Chaitin, On the Length of Programs for Computing Finite Binary Sequences: statistical considerations, Journal of the ACM (JACM), v.16 n.1, p.145-159, Jan. 1969 [doi>10.1145/321495.321506]
	5	DALEY, R. Minimal-program complexity of pseudo-recursive and pseudo-random sequences. Dept. of Math. Rep. 71-28, Carnegie Mellon U., 1971.
	6	DALEY, R. Minimal-program complexity of sequences with restricted resources. ICR Rep. No. 30, U. of Chicago, 1971.
	7	KANOVI~, M. On the complexity of Boolean function minimization. Soviet Math. Dokl. 12, 3 (1971), 720-724.
	8	KhNOVI~, M., AND PnTRI, N. Some theorems on the complexity of normal algorithms and computations. Soviet Malh. Dokladi 10, 1 (1969), 233-234.
	9	KOLMOGOROV, A. Three approaches for defining the concept of information quantity. Information Transmission I (1965), 3-11.
	10	LOVELAND, D. A variant of the Kolmogorov concept of complexity. Inform. Contr. 15 (1969), 510-526.
	11	D. W. Loveland, On minimal-program complexity measures, Proceedings of the first annual ACM symposium on Theory of computing, p.61-78, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805422]
	12	MAaKOV, A. Theory of Algorithms (English Transl.), National Science Foundation, Washington, D.C., 1961.
	13	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	14	SCI-INORR, C. Optimal G6del numberings. Proc. 1971 IFIP Cong., Ljubljana, Yugoslavia, TA-2, pp. 12-14.
	15	SOLOMONOV, R. A formal theory of inductive inference. Part I. Inform. Co~tr. 7 (1964), 1-22.

CITED BY 2

	Fred G. Abramson , Yuri Breitbart , Forbes D. Lewis, Complex Properties of Grammars, Journal of the ACM (JACM), v.27 n.3, p.484-498, July 1980
	Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983