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.

Filter by
Sorted by
Tagged with
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 ...
XL _At_Here_There's user avatar
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 ...
XL _At_Here_There's user avatar