Information-Theoretic Limitations of Formal Systems
- 1 July 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 21 (3) , 403-424
- https://doi.org/10.1145/321832.321839
Abstract
An attempt is made to apply information-theoretic computational complexity to meta-mathematics. The paper studies the number of bits of instructions that must be given to a computer for it to perform finite and infinite tasks, and also the time it takes the computer to perform these tasks. This is applied to measuring the difficulty of proving a given set of theorems, in terms of the number of bits of axioms that are assumed, and the size of the proofs needed to deduce the theorems from the axioms.Keywords
This publication has 12 references indexed in Scilit:
- Information-theoretic computation complexityIEEE Transactions on Information Theory, 1974
- Abbreviating proofs by adding new axiomsBulletin of the American Mathematical Society, 1971
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMSRussian Mathematical Surveys, 1970
- Computational Complexity and Probability ConstructionsJournal of the ACM, 1970
- A variant of the Kolmogorov concept of complexityInformation and Control, 1969
- Algorithms and RandomnessRevue de l'Institut International de Statistique / Review of the International Statistical Institute, 1969
- Logical basis for information theory and probability theoryIEEE Transactions on Information Theory, 1968
- ParadoxScientific American, 1962
- Heuristic Reasoning in the Theory of NumbersThe American Mathematical Monthly, 1959
- Mathematical SievesScientific American, 1958