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

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 access
Chaitin, Gregory J. · 1975 · Journal of the ACM

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

24 of 24 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

Research works printed but not linked: 10

  1. ~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.
  2. 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
  3. 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.
  4. 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
  5. 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
  6. 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.
  7. 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.
  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 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
  9. 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
  10. 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

See all 849

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.