Journal of the ACM Bibliography
Gregory J. Chaitin.
Information-theoretic limitations of formal systems. Journal of
the ACM, 21(3):403-424, July 1974.
[BibTeX entry]
Additional Key Words and Phrases:
complexity of sets, computational complexity, difficulty of
theorem-proving, entropy of sets, formal systems, G\"odel's
incompleteness theorem, halting problem, information content of sets,
information content of axioms, information theory, information time
trade-offs, metamathematics, random strings, recursive functions,
recursively enumerable sets, size of proofs, universal computers
Selected references
- Shen Lin and Tibor Rado. Computer studies of Turing machine
problems. Journal of the ACM, 12(2):196-212, April
1965.
- D. W. Loveland. A variant
of the Kolmogorov concept of complexity. Information and
Control, 15(6):510-526, December 1969.
- D. W. Loveland. On minimal-program
complexity measures. In Conference Record of ACM Symposium on
Theory of Computing, pages 61-65, Marina del Rey, California, 5-7
May 1969.
- David G. Willis. Computational complexity and
probability constructions. Journal of the ACM,
17(2):241-259, April 1970.
Shortcuts: