Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs (Q494650): Difference between revisions

Algorithmic randomness considers various ways to express that an infinite sequence of \(0\)s and \(1\)s, usually called a `real number', are `arbitrary', `lawless' or `random'. Two particularly important approaches are Martin-Löf randomness and incompressibility. Roughly, being Martin-Löf random means not being contained in a set of measure \(0\) that can be effectively approximated, while incompressibility means that the lengths of the shortest programs for computing initial segments do not grow smaller than the lengths of the initial segments themselves. Martin-Löf (ML) randomness can be relativized by allowing approximations relative to an oracle, and chosing this oracle to be the Turing jump \(0^{\prime}\), one obtains \(2\)-randomness. Incompressibility, on the other hand, comes in two versions, depending on the complexity measure used. If \(s\) is a (finite) binary string, then \(K(s)\) denotes the prefix-free complexity of \(s\), while \(C(s)\) denotes the plain complexity of \(s\). Finally, the `randomness deficiency' \(d(x)\) of a real number \(x\) intuitively is a measure for how far \(x\) is from being random. Like ML-randomness, \(d\) can be considered relative to oracles. An important result in algorithmic randomness is that, for a binary string \(s=(s_{i}:i\in\omega)\), the inferior limit of \(n-C(s_{0}s_{1}\dots s_{n})\) is finite if and only if \(s\) is \(2\)-random. This can be refined to the statement that this limit uniformly only differs by a constant from \(d^{0^{\prime}}(s)\). Considering prefix-free complexity, it is known that \(s\) is \(2\)-random if and only if the inferior limit of \(n+K(n)-K(s_{0}\dots s_{n})\) is finite. The paper under review contains short and simplified proofs of these results. The methods developed along the way are finally used to prove a new refinement of the statement for prefix-free complexity, namely that \(d^{0^{\prime}}(s)\) uniformly only differs by a constant from the inferior limit of \(n+K(n)+K(s_{0}\dots s_{n})\). The paper requires a background in algorithmic randomness and recursion theory on the part of the reader.