Questions tagged [algorithmic-randomness]
Martin-Löf randomness and other randomness notions arising from computable tests; as well as related concepts such as Kolmogorov complexity, K-triviality, and effective Hausdorff dimension.
2
questions
3
votes
1
answer
287
views
Relationship between P-noncomputable and P-random sets
$P$ means polynomial complexity.
$S_p$ is the class of all $P$_random set, and $S_{pc}$ is the class of all $P$ noncomputable sets, is $S_p \bigcap S_{pc}$ empty? If not empty, any example?
what is ...
8
votes
1
answer
2k
views
What is the precise relation between Kolmogorov complexity and Shannon's entropy?
Consider the discrete case:
Shannon's entropy is $H(x)=-\sum\limits_i^n p(x_i) log\space p(x_i)$.
Probability based on prefix-free Kolmogorov complexity is $R(x_i)=2^{-K(x_i)}$ where $K(x_i)$ is ...