On the Length of Programs for Computing Finite Binary Sequences

Chaitin, G. J. (1969). On the Length of Programs for Computing Finite Binary Sequences. Journal of the ACM, 16(1), 145-159.

Type

Journal article

Intellectual base

Primary research

Year

1969

DOI

10.1145/321356.321363

Link

https://doi.org/10.1145/321356.321363

Cited from

information_theory, mathematics

Cited by

2 citations across 2 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Compression

  • This sourceIndependent founding of algorithmic information theory / algorithmic randomness. Tier C (bibliography only). DOI verified.

• Randomness
  • … flag is justified: practical use of randomness (gambling, divination, fair allocation by lot) precedes any mathematical theory by millennia, and even the formal theory has multiple distinct origin points — Kolmogorov's (1965) complexity-theoretic definition (with parallel independent work by Chaitin (1969)

    This source(Originating treatment of Chaitin's omega and algorithmic randomness; parallel independent work to Kolmogorov and Solomonoff.)

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:257117d01140 · see in the full table