The frequent paucity of trivial strings

A 1976 theorem of Chaitin can be used to show that arbitrarily dense sets of 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...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2014-11, Vol.114 (11), p.643-645
Main Author: Lutz, Jack H.
Format: Article
Language:English
Subjects:
Complexity
Complexity theory
Data processing
Information processing
Kolmogorov complexity
Probabilistic methods
Probability distribution
Proof theory
Proving
Strings
Studies
Theorems
Theory of computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A 1976 theorem of Chaitin can be used to show that arbitrarily dense sets of 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, and it gives a tighter paucity bound. •We give a new, very simple proof of a 1976 theorem on Kolmogorov complexity.•The new proof uses the probabilistic method.•The new proof significantly tightens the old theorem's paucity bound.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2014.05.006