The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
A Theory of Program Size Formally Identical to Information Theory
Open accessAbstract
A new definition of program-size complexity is made.H(A,B/C,D) is defined to be the size in bits of the shortest self-delimiting program for calculating strings A and B if one is given a minimal-size self-delimiting program for calculating strings C and D. This differs from previous definitions: (1) programs are required to be self-delimiting, i.e. no program is a prefix of another, and (2) instead of being given C and D directly, one is given a program for calculating them that is minimal in size.Unlike previous definitions, this one has precisely the formal properties of the entropy concept of information theory.For example, H(A,B) = H(A) + H(B/A) -~ 0(1).Also, if a program of length k is assigned measure 2 -k, then H(A) = -log2 (the probability that the standard universal computer will calculate A) -{-0(1).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
ASH, R. B. (1966) · Cited by 3,990
Perceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,720
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679 · cited 1×
“See [17–32] for other applications of information/entropy concepts.”
BackgroundComputation: Finite and Infinite Machines.
Clarke, D. A., & Minsky, M. L. (1968) · The American Mathematical Monthly · doi:10.2307/2313471 · Cited by 2,583
Three approaches to the quantitative definition of information*
Kolmogorov, A. N. (1968) · International Journal of Computer Mathematics · doi:10.1080/00207166808803030 · Cited by 2,031
A formal theory of inductive inference. Part II
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90131-7 · Cited by 1,758
A formal theory of inductive inference. Part I
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90223-2 · Cited by 1,192
Universal codeword sets and representations of the integers
Elias, P. (1975) · IEEE Transactions on Information Theory · doi:10.1109/tit.1975.1055349 · Cited by 1,165
Information Theory and Coding.
Good, I. J., & Abramson, N. (1964) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2343598 · Cited by 1,068
On the Length of Programs for Computing Finite Binary Sequences: statistical considerations
Chaitin, G. J. (1969) · Journal of the ACM · doi:10.1145/321495.321506 · Cited by 918
Self-citation
Research works printed but not linked: 10
- ~OLMOGOROV , A.N. On the logical foundations of information theory and probability theory. Problems of Inform. Transmission 5, 3 (July-Sept . 1969 ), 1-4. ~OLMOGOROV, A.N. On the logical foundations of information theory and probability theory. Problems of Inform. Transmission 5, 3 (July-Sept. 1969), 1-4.
- LOVELAND , D.W . A variant of the Kolmogorov concept of complexity . Inform. and Contr. 15 ( 1969 ), 510 - 526 . LOVELAND, D.W. A variant of the Kolmogorov concept of complexity. Inform. and Contr. 15 (1969), 510-526. · doi:10.1016/s0019-9958(69)90538-5
- COVER , T.M. Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin. Rep. No. 12, Statistics Dep., Stanford U., Stanford , Calif. , 1974 . Submitted to Ann. Statist. COVER, T.M. Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin. Rep. No. 12, Statistics Dep., Stanford U., Stanford, Calif., 1974. Submitted to Ann. Statist.
- WEISS , B . The isomorphism problem in ergodic theory . Bull. Amer. Math. Soc. 78 ( 1972 ), 668 - 684 . WEISS, B. The isomorphism problem in ergodic theory. Bull. Amer. Math. Soc. 78 (1972), 668-684. · doi:10.1090/s0002-9904-1972-12979-3
- COVER , T.M . On determining the irrationality of the mean of a random variable . Ann. Statist. 1 ( 1973 ), 862 - 471 . COVER, T.M. On determining the irrationality of the mean of a random variable. Ann. Statist. 1 (1973), 862-471. · doi:10.1214/aos/1176342507
- LE vis, M . Mathematical Logic for Computer Scientists. Rep. TR-131 , M.I.T. Project MAC , 1974 , pp. 145 - 147 , 153. LEvis, M. Mathematical Logic for Computer Scientists. Rep. TR-131, M.I.T. Project MAC, 1974, pp. 145-147, 153.
- SCHWARTZ , J . T . On Programming : An Interim Report on the SETL Project. Installment I: Generalities. Lecture Notes, Courant Institute , New York University , New York , 1973 , pp. 1 - 20 . SCHWARTZ, J .T . On Programming: An Interim Report on the SETL Project. Installment I: Generalities. Lecture Notes, Courant Institute, New York University, New York, 1973, pp. 1-20.
- DALEY R .P . The extent and density of sequences within the minimal-program complexity hierarchies. J. Comput. and Syst. Scis. (to appear). 10.1016/S0022-0000(74)80004-8 DALEY R .P . The extent and density of sequences within the minimal-program complexity hierarchies. J. Comput. and Syst. Scis. (to appear). 10.1016/S0022-0000(74)80004-8 · doi:10.1016/s0022-0000(74)80004-8
- ELIAS P. Minimum times and memories needed to compute the values of a function. J. Cornput. and Syst. Scis. (to appear). 10.1016/S0022-0000(74)80007-3 ELIAS P. Minimum times and memories needed to compute the values of a function. J. Cornput. and Syst. Scis. (to appear). 10.1016/S0022-0000(74)80007-3 · doi:10.1016/s0022-0000(74)80007-3
- HELLMAN , M.E. The information theoretic approach to cryptography . Center for Systems Research , Stanford U. , Stanford, Calif., 1974 . HELLMAN, M.E. The information theoretic approach to cryptography. Center for Systems Research, Stanford U., Stanford, Calif., 1974.
Cited by
On the Complexity of Finite Sequences
Lempel, A., & Ziv, J. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055501 · Cited by 2,717
The thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006
A Universal Prior for Integers and Estimation by Minimum Description Length
Rissanen, J. (1983) · The Annals of Statistics · doi:10.1214/aos/1176346150 · Cited by 1,672
Theory and application of trapdoor functions
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.95 · Cited by 1,008
Algorithmic Information Theory
Chaitin, G. J. (1977) · IBM Journal of Research and Development · doi:10.1147/rd.214.0350 · Cited by 982
Self-citationTheory and application of trapdoor functions
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.45 · Cited by 968
Information Science and Statistics
Andersen, E. B. (1986) · COMPSTAT · doi:10.1007/978-3-642-46890-2_1 · Cited by 899
Inductive Inference: Theory and Methods
Angluin, D., & Smith, C. H. (1983) · ACM Computing Surveys · doi:10.1145/356914.356918 · Cited by 887
Complexity measures of supervised classification problems
Ho, T. K., & Basu, M. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.990132 · Cited by 734
Statistics of local complexity in amino acid sequences and sequence databases
Wootton, J. C., & Federhen, S. (1993) · Computers & Chemistry · doi:10.1016/0097-8485(93)85006-x · Cited by 729
Bennett, C. H., Gacs, P., Li, M., Vitanyi, P. M. B., & Zurek, W. H. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.681318 · Cited by 506
Minimum complexity density estimation
Barron, A. R., & Cover, T. M. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.86996 · Cited by 497
Predictability, Complexity, and Learning
Bialek, W., Nemenman, I., & Tishby, N. (2001) · Neural Computation · doi:10.1162/089976601753195969 · Cited by 504
A complexity theoretic approach to randomness
Sipser, M. (1983) · Proceedings of the fifteenth annual ACM symposium on Theory of computing - STOC '83 · doi:10.1145/800061.808762 · Cited by 460
Complexity-based induction systems: Comparisons and convergence theorems
Solomonoff, R. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055913 · Cited by 388
Bennett, C. H., & Gill, J. (1981) · SIAM Journal on Computing · doi:10.1137/0210008 · Cited by 381
Universal prediction of individual sequences
Feder, M., Merhav, N., & Gutman, M. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.144706 · Cited by 373
Algorithmic randomness and physical entropy
Zurek, W. H. (1989) · Physical Review A · doi:10.1103/physreva.40.4731 · Cited by 364
Statistical and Inductive Inference by Minimum Message Length
(2005) · Information Science and Statistics · doi:10.1007/0-387-27656-4 · Cited by 349
Rissanen, J. (1987) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1987.tb01694.x · Cited by 339
Thermodynamic cost of computation, algorithmic complexity and the information metric
Zurek, W. H. (1989) · Nature · doi:10.1038/341119a0 · Cited by 279
Information-geometric approach to inferring causal directions
Janzing, D., Mooij, J., Zhang, K., Lemeire, J., Zscheischler, J., Daniušis, P., Steudel, B., & Schölkopf, B. (2012) · Artificial Intelligence · doi:10.1016/j.artint.2012.01.002 · Cited by 259
Randomness conservation inequalities; information and independence in mathematical theories
Levin, L. A. (1984) · Information and Control · doi:10.1016/s0019-9958(84)80060-1 · Cited by 256
Probabilistic Incremental Program Evolution
Salustowicz, R., & Schmidhuber, J. (1997) · Evolutionary Computation · doi:10.1162/evco.1997.5.2.123 · Cited by 249
On the Measure of Intelligence
Chollet, F. (2019) · arXiv · doi:10.48550/arxiv.1911.01547 · Cited by 218
Gödel Machines: Fully Self-referential Optimal Universal Self-improvers
Schmidhuber, J. (2007) · Cognitive Technologies · doi:10.1007/978-3-540-68677-4_7 · Cited by 110
Prebiotically plausible mechanisms increase compositional diversity of nucleic acid sequences
Derr, J., Manapat, M. L., Rajamani, S., Leu, K., Xulvi-Brunet, R., Joseph, I., Nowak, M. A., & Chen, I. A. (2012) · Nucleic Acids Research · doi:10.1093/nar/gks065 · Cited by 74
Schmidhuber, J. (2003) · arXiv · doi:10.48550/arxiv.cs/0309048 · Cited by 24
Predicting phenotype transition probabilities via conditional algorithmic probability approximations
Dingle, K., Novev, J. K., Ahnert, S. E., & Louis, A. A. (2022) · Journal of the Royal Society Interface · doi:10.1098/rsif.2022.0694 · Cited by 13
(2003) · doi:10.71910/supsi.7059 · Cited by 11
Metadata
- Authors
- Chaitin, G. J.
- Venue
- Journal of the ACM
- Published
- 1975-07
- Volume
- 22
- Issue
- 3
- Pages
- 329-340
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2020311636
- Cited by
- 849
- References
- 24
- FWCI
- 11.09
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.