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

Volume

16

Issue

1

Pages

145-159

DOI

10.1145/321356.321363

DOI registrant

Association for Computing Machinery

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. 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.)

    Supported in partVerified against the publisher's abstract

    The abstract shows Chaitin's paper proposes defining a patternless sequence from information theory and recursive-function concepts, but it says nothing about independent parallel work to Kolmogorov.

    “An application to the problem of defining a patternless sequence is proposed in terms of the concepts here developed.”

    Read by an automated reader; not a human review. How support was checked

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 2 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

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