A 1976 theorem of Chaitin, strengthening a 1969 theorem of Meyer,says that infinitely many lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs. It also gives a tighter paucity bound, and it shows that the set of lengths n at which there is a paucity of trivial strings is not only infinite, but has positive Schnirelmann density.
展开▼
