Is complexity a source of incompleteness?

Algorithmic Information Theory

Gregory J. Chaitin · IBM Journal of Research and Development · 1977 · 1K citations

Computing, Computer Science, Mathematics +13

A Theory of Program Size Formally Identical to Information Theory

Gregory J. Chaitin · Journal of the ACM · 1975 · 884 citations · Full text

Computing, Computer Science, Information Theory +8

Handbook of mathematical logic, edited by Jon Barwise with the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis, and A. S. Troelstra, Studies in logic and the foundations of mathematics, vol. 90, North-Holland Publishing Company, Amsterdam, New York, and Oxford, 1978 (© 1977), xi + 1165 pp. - C. Smoryński. D.1. The incompleteness theorems. Pp. 821–865. - Helmut Schwichtenberg. D.2. Proof theory: some applications of cut-elimination. Pp. 867–895. - Richard Statman. D.3. Herbrand's theorem and Gentzen's notion of a direct proof. Pp. 897–912. - Solomon Feferman. D.4. Theories of finite type related to mathematical practice. Pp. 913–971. - A. S. Troelstra. D.5. Aspects of constructive mathematics. Pp. 973–1052. - Michael P. Fourman. D.6. The logic of topoi. Pp. 1053–1090. - Henk P. Barendregt. D.1. The type free lambda calculus. Pp. 1091–1132. - Jeff Paris and Leo Harrington. D.8. A mathematical incompleteness in Peano arithmetic. Pp. 1133–1142.

William A. Howard · Journal of Symbolic Logic · 1984 · 840 citations

Computing, Computer Science, Mathematics +11

Randomness and Mathematical Proof

Gregory J. Chaitin · Scientific American · 1975 · 677 citations

Natural Sciences, Mathematics, Probability Theory +10

Book Review: An introduction to Kolmogorov Complexity and its Applications Second Edition, 1997 by Ming Li and Paul Vitanyi (Springer (Graduate Text Series))

William Gasarch · ACM SIGACT News · 1997 · 587 citations · Full text

Computing, Computer Science, Algorithms +12