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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Perceptrons: An Introduction to Computational Geometry
Minsky, M., & Papert, S. A. (1969) · Cited by 3,266
Computation: 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-citationOn the Length of Programs for Computing Finite Binary Sequences
Chaitin, G. J. (1966) · Journal of the ACM · doi:10.1145/321356.321363 · Cited by 913
Self-citationZvonkin, A. K., & Levin, L. A. (1970) · Russian Mathematical Surveys · doi:10.1070/rm1970v025n06abeh001269 · Cited by 665
Randomness and Mathematical Proof
Chaitin, G. J. (1975) · Scientific American · doi:10.1038/scientificamerican0575-47 · Cited by 656
Self-citationFano, R. M., & Wintringham, W. T. (1961) · Physics Today · doi:10.1063/1.3057290 · Cited by 536
(2012) · SpringerReference · doi:10.1007/springerreference_205344 · Cited by 447
Feinstein, A., & Fano, R. M. (1962) · Journal of the American Statistical Association · doi:10.2307/2281659 · Cited by 360
Theories of Probability: An Examination of Foundations
Fine, T. L. (1973) · International Linear Collider · Cited by 328
Foundations of Information Theory
Feinstein, A., & Weiss, G. (1958) · Physics Today · doi:10.1063/1.3062338 · Cited by 308
Process complexity and effective random tests
Schnorr, C. P. (1973) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(73)80030-3 · Cited by 257
Information-Theoretic Limitations of Formal Systems
Chaitin, G. J. (1974) · Journal of the ACM · doi:10.1145/321832.321839 · Cited by 216
Self-citationINFORMATION-THEORETIC COMPUTATIONAL COMPLEXITY
Chaitin, G. J. (1987) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789814434058_0003 · Cited by 119
Self-citationInformation-theoretic characterizations of recursive infinite strings
Chaitin, G. J. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90005-0 · Cited by 87
Self-citationOn the difficulty of computations
Chaitin, G. J. (1970) · IEEE Transactions on Information Theory · doi:10.1109/tit.1970.1054390 · Cited by 53
Self-citationComputational Complexity and Probability Constructions
Willis, D. G. (1970) · Journal of the ACM · doi:10.1145/321574.321578 · Cited by 49
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
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
Minimum complexity density estimation
Barron, A. R., & Cover, T. M. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.86996 · Cited by 497
Bennett, C. H., & Gill, J. (1981) · SIAM Journal on Computing · doi:10.1137/0210008 · Cited by 381
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.