Computational Complexity and Probability Constructions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computational Complexity and Probability Constructions

Full text

Pdf (1.40 MB)

Source

Journal of the ACM (JACM) archive
Volume 17 , Issue 2 (April 1970) table of contents

Pages: 241 - 259

Year of Publication: 1970

ISSN:0004-5411

Author

David G. Willis

Stanford University, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/321574.321578 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	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]
	3	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]
	4	FANO, R.M. Transmission of Information. MIT Press, Cambridge, Mass., and Wiley, New York, 1961 (published jointly).
	5	GOLDMAN, S. Information Theory. Prentice-Hall, Englewood Cliffs, N. J., 1953.
	6	GREEN, M.W. A lower bound on Rado's sigma function for binary Turing machines. Switching Circuit Theory and Logical Design, IEEE Pub. S-164, 1964, pp. 91-94.
	7	HARTMANIS, J., AND STEARNS, ~:~. E. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (May 1965), 285-306.
	8	KOLMOGOROV, A. N. Grundbegriffe der Wahrscheinlichkeitsrechnung. Springer, Berlin, 1933; translated, ed., Foundations of the Theory of Probability, Morrison, Nathan, transl., Chelsea, New York, 1956.
	9	----. On tables of random numbers. Sankhyd. The Indian Journal of Statistics {A}, 25, 4 (1963), 369-376.
	10	----. Three approaches to the quantitative definition of information. Inform. Transmission 1 (1965), 3-11.
	11	, ----. Logical basis for information theory and probability theory. IEEE Trans. IT-14, 5 (Sept. 1968), 662-664.
	12	MARTIN-LoF, P. The definition of random sequences. Inform. Control 9 (1966), 602-619.
	13	Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
	14	RITCHIE, R.W. Classes of predictably computable functions. Trans. Amer. Math. Soc. 106 (1963), 139-173.
	15	RUSSELL, B. A.W. Les paradoxes de la logique. Revue de M~taphysique el de Morale 14 (1906), 627-650.
	16	SHANNON, C.E. A mathematical theory of communication. Bell Syst. Tech. J. 27 (1948), 379-423.
	17	--. A universal Turing machine with two internal states. In Automata Studies, Shannon, C. E., and McCarthy, J. (Eds.), Princeton U. Press, Princeton, N. J., 1956, pp. 157-165.
	18	SOLOMONOFF, R. J. A formal theory of inductive inference, Pt. I. Inform. Control. 7 (1964), 1-22.
	19	STEARNS, R. E., HARTMANIS, J., AND LEWIS, P.M. Hierarchies of memory limited computations. IEEE Conf. Rec. on Switching Circuit Theory and Logical Design, IEEE Pub. 16C13, 1965, 179-190.
	20	TURING, A.M. On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. {2}, 42 (1936-1937), 230-265; correction in Proc. London Math. Soc. {2}, 43 (1937), 544-546.
	21	VON MISES R. Probability, Statistics and Truth. William Hodge, London, 1939.
	22	WILLIS, D. G. The Mechanism of Inductive Inference. Stanford U., Stanford, Calif., June 3, 1968.

CITED BY 6

	Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM (JACM), v.22 n.3, p.329-340, July 1975
	L. K. Schubert, Iterated Limiting Recursion and the Program Minimization Problem, Journal of the ACM (JACM), v.21 n.3, p.436-445, July 1974
	Gregory J. Chaitin, Information-Theoretic Limitations of Formal Systems, Journal of the ACM (JACM), v.21 n.3, p.403-424, July 1974
	Gianni Amati , Cornelis Joost Van Rijsbergen, Probabilistic models of information retrieval based on measuring the divergence from randomness, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.357-389, October 2002
	B. R. Gaines, Fuzzy reasoning and the logics of uncertainty, Proceedings of the sixth international symposium on Multiple-valued logic, p.179-188, May 25-28, 1976, Logan, Utah, United States
	L. K. Schubert, Iterated limiting recursion and the program minimization problem, Proceedings of the 3rd international joint conference on Artificial intelligence, p.513-523, August 20-23, 1973, Stanford, USA