Information-theoretic computation complexity
- 1 January 1974
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 20 (1) , 10-15
- https://doi.org/10.1109/tit.1974.1055172
Abstract
This paper attempts to describe, in nontechnical language, some of the concepts and methods of one school of thought regarding computational complexity. It applies the viewpoint of information theory to computers. This will first lead us to a definition of the degree of randomness of individual binary strings, and then to an information-theoretic version of Gödel's theorem on the limitations of the axiomatic method. Finally, we will examine in the light of these ideas the scientific method and yon Neumann's views on the basic conceptual problems of biology.Keywords
This publication has 7 references indexed in Scilit:
- Selforganization of matter and the evolution of biological macromoleculesThe Science of Nature, 1971
- Computational complexity and Gödel's incompleteness theoremACM SIGACT News, 1971
- To a mathematical definition of 'life'ACM SIGACT News, 1970
- On the difficulty of computationsIEEE Transactions on Information Theory, 1970
- Logical basis for information theory and probability theoryIEEE Transactions on Information Theory, 1968
- A formal theory of inductive inference. Part IInformation and Control, 1964
- Statistical Independence in Probability, Analysis, and Number TheoryPublished by American Mathematical Society (AMS) ,1959