SAS

Abstract

Let $X$ be an infinite sequence of $0$'s and $1$'s, i.e., $X\in\{0,1\}^\mathbb{N}$. Even if $X$ is not Martin-Löf random, we can nevertheless quantify the amount of partial randomness which is inherent in $X$. Many researchers including Calude, Hudelson, Kjos-Hanssen, Merkle, Miller, Reimann, Staiger, Tadaki, and Terwijn have studied partial randomness. We now present some new results due to Higuchi, Hudelson, Simpson and Yokoyama concerning propagation of partial randomness. Our results say that if $X$ has a specific amount of partial randomness, then $X$ has an equal amount of partial randomness relative to certain Turing oracles. More precisely, let $\mathrm{KA}$ denote a priori Kolmogorov complexity, i.e., $\mathrm{KA}(\sigma)=-\log_2m(\sigma)$ where $m$ is Levin's universal left-r.e. semimeasure. Note that $\mathrm{KA}$ is similar but not identical to the more familiar prefix-free Kolmogorov complexity. Given a computable function $f:\{0,1\}^*\to[0,\infty)$, we say that $X\in\{0,1\}^\mathbb{N}$ is strongly $f$-random if $\exists c\,\forall n\,(\mathrm{KA}(X{\upharpoonright}\{1,\ldots,n\})>f(X{\upharpoonright}\{1,\ldots,n\})-c)$. Two of our results read as follows.

Theorem 1. Assume that $X$ is strongly $f$-random and Turing reducible to $Y$ where $Y$ is Martin-Löf random relative to $Z$. Then $X$ is strongly $f$-random relative to $Z$.

Theorem 2. Assume that $\forall i\,(X_i$ is strongly $f_i$-random$)$. Then, we can find a $\mathrm{PA}$-oracle $Z$ such that $\forall i\,(X_i$ is strongly $f_i$-random relative to $Z)$.

We also show that Theorems 1 and 2 fail badly with $\mathrm{KA}$ replaced by $\mathrm{KP}=$ prefix-free complexity.