Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat
Sign Up
Cited by 849

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

A Theory of Program Size Formally Identical to Information Theory

Open access
Chaitin, Gregory J.·1975·Journal of the ACM
DOI 10.1145/321892.321894
Open this paper in CoChat — free account

Abstract

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/321892.321894

Cites

3 of 3 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 3 references

Research works printed but not linked: 29

  1. KOLMOGOROV , A.N . Three approaches to the quantitative definition of information . Problems of Inform. Transmission 1 , 1 (Jam- March 1965 ), 1-7. KOLMOGOROV, A.N. Three approaches to the quantitative definition of information. Problems of Inform. Transmission 1, 1 (Jam-March 1965), 1-7.
  2. 10.1145/321495.321506 · DOI · Paper page
  3. ~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.
  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
  5. SCHNORR , C.P . Process complexity and effective random tests . J. Comput. and Syst. Scis. 7 ( 1973 ), 376 - 388 . SCHNORR, C.P. Process complexity and effective random tests. J. Comput. and Syst. Scis. 7 (1973), 376-388. · DOI · Paper page
  6. CHAITIN , G.J. On the difficulty of computations. 1EEE Trans. IT-16 ( 1970 ), 5-9. CHAITIN, G.J. On the difficulty of computations. 1EEE Trans. IT-16 (1970), 5-9.
  7. FEINSTEIN , A. Foundations of Information Theory . McGraw-Hill , New York , 1958 . FEINSTEIN, A. Foundations of Information Theory. McGraw-Hill, New York, 1958.
  8. FANO , R. M. Transmission of Information . Wiley , New Nork , 1961 . FANO, R. M. Transmission of Information. Wiley, New Nork, 1961.
  9. ABRAMSON , N. Information Theory and Coding . McGraw-Hill , New York , 1963 . ABRAMSON, N. Information Theory and Coding. McGraw-Hill, New York, 1963.
  10. AsH, R. Information Theory . Wiley-Interscience , New York , 1965 . AsH, R. Information Theory. Wiley-Interscience, New York, 1965.
  11. 10.1145/321574.321578 · DOI
  12. ZVONKIN , A. K. , AN n LE VlN , L. A. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Survs. 25, 6 (Nov.-Dec . 1970 ), 83-124. ZVONKIN, A. K., ANn LEVlN, L.A. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Survs. 25, 6 (Nov.-Dec. 1970), 83-124.
  13. 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.
  14. 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
  15. R~NYI , A. Foundations of Probability . Holden-Day , San Francisco , 1970 . R~NYI, A. Foundations of Probability. Holden-Day, San Francisco, 1970.
  16. FINE , T . L . Theories of Probability: An Examination of Foundations . Academic Press , New York , 1973 . FINE, T .L . Theories of Probability: An Examination of Foundations. Academic Press, New York, 1973.
  17. 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
  18. CHAITIN , G . J . Information-theoretic computational complexity . IEEE Trans. IT-20 ( 1974 ), 10 - 15 . CHAITIN, G .J . Information-theoretic computational complexity. IEEE Trans. IT-20 (1974), 10-15.
  19. 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.
  20. 10.1145/321832.321839 · DOI
  21. MINSKY , M. L. Computation: Finite and Infinite Machines . Prentice-Hall , Englewood Cliffs, N. J. , 1967 , pp. 54 , 55, 66. MINSKY, M. L. Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, N. J., 1967, pp. 54, 55, 66.
  22. MINSK~ , M. , AND PAPERT , S. Perceptrons: An Introduction to Computational Geometry . M.I.T. Press , Cambridge, Mass ., 1969 , pp. 150 , 153. MINSK~, M., AND PAPERT, S. Perceptrons: An Introduction to Computational Geometry. M.I.T. Press, Cambridge, Mass., 1969, pp. 150, 153.
  23. 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.
  24. BENNETT , C.H . Logical reversibility of computation . IBM J. Res. Develop. 17 ( 1973 ), 525 - 532 . BENNETT, C.H. Logical reversibility of computation. IBM J. Res. Develop. 17 (1973), 525-532. · DOI · Paper page
  25. 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
  26. 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
  27. 10.1109/TIT.1975.1055349 · DOI · Paper page
  28. 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.
  29. CHAITI~ , G.J. Randomness and mathematical proof. Sc/. Amer. ~35, 5 (May 1975 ), in press. CHAITI~, G.J. Randomness and mathematical proof. Sc/. Amer. ~35, 5 (May 1975), in press.

Cited by

See all 849

Metadata

Authors
Chaitin, G. J.
Venue
Journal of the ACM
Publisher
Association for Computing Machinery (ACM)
Published
1975-07
Volume
22
Issue
3
Pages
329-340
ISSN
  • 0004-5411 (ISSN-L)
  • 1557-735X
DOI
10.1145/321892.321894
OpenAlex
W2020311636
Cited by
849
References
3
FWCI
11.09
Type
journal article
Language
en
Open access
bronze
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)

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

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: A Theory of Program Size Formally Identical to Information Theory. https://app.cochat.ai/papers/10.1145/321892.321894
The paper
Chaitin, G. J. (1975). A Theory of Program Size Formally Identical to Information Theory. Journal of the ACM. https://doi.org/10.1145/321892.321894

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.