A string \(x\) is \(c-\text{incompressible}\) if \[K(x) \geq |x| - c \], for some constant \(c\) where \(K(.)\) stands for Kolmogorov Complexity

In the language \(\Sigma^* \) where \(\Sigma = \{ 0, 1 \} \), what is the minimum possible number of strings of length \(8\) that are \(3\)-incompressible?

×

Problem Loading...

Note Loading...

Set Loading...