Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4661644 | Annals of Pure and Applied Logic | 2016 | 4 Pages |
Abstract
The combined universal probability M(D)M(D) of strings x in sets D is close to maxx∈DM({x})maxx∈DM({x}): their ∼logs differ by at most D 's information j=I(D:H)j=I(D:H) about the halting sequence HH. Thus if all x have complexity K(x)≥kK(x)≥k, D carries ≥i bits of information on each x where i+j∼ki+j∼k. Note, there are no ways (whether natural or artificial) to generate D with significant I(D:H)I(D:H).
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Leonid A. Levin,