The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Propagation of partial randomness

Simpson, S (Pennsylvania State University)
Tuesday 03 July 2012, 09:00-10:00

Seminar Room 1, Newton Institute


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.


[pdf ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧