# Algorithmic Randomness Given a string $s$, the algorithmic complexity of $s$ is the size of the smallest program that outputs $s$. The string $s$ is random if the algorithmic complexity has the same size as the size of $s$. One advantage of this definition is that it is not use the language of probability. Another, is that this definition avoid the uncomfortable of explaining string that are valid in the Bernoulli-trial-randomness like a string that contains just 0's. For example, let $s$ have repeated 1000 times the substring "101" - then a short program can generate it which is much smaller than $s$ and so it is not random. Another example: $s$ is the results of 1000 Bernoulli tests will probably not be shorter than $s$ and so is random. If $s$ is random then also the program that generates it is random. otherwise we would have a short program that generates the program that generates $s$. Reference [[@What is Random? Chance and Order in Mathematics and Life]] ## Created 2023-12-01 13:43