Pointed computations and Martin-Löf randomness

Abstract

Schnorr showed that a real X is Martin-Löf random if and only if $\mathit{K}\mathrm{(}\mathit{X}{\upharpoonright }_{\mathit{n}}\mathrm{)}⩾\mathit{n}-\mathit{c}$ for some constant c and all n, where K denotes the prefix-free complexity function. Fortnow (unpublished) and Nies, Stephan and Terwijn [J. Symbolic Logic70 (2005), 515–535] observed that the condition $\mathit{K}\mathrm{(}\mathit{X}{\upharpoonright }_{\mathit{n}}\mathrm{)}⩾\mathit{n}-\mathit{c}$ can be replaced with $\mathit{K}\mathrm{(}\mathit{X}{\upharpoonright }_{{\mathit{r}}_{\mathit{n}}}\mathrm{)}⩾{\mathit{r}}_{\mathit{n}}-\mathit{c}$ , for any fixed increasing computable sequence $\mathrm{(}{\mathit{r}}_{\mathit{n}}\mathrm{)}$ , in this characterization. The purpose of this note is to establish the following generalisation of this fact. We show that X is Martin-Löf random if and only if $\exists \mathit{c}\forall \mathit{n}\mathit{K}\mathrm{(}\mathit{X}{\upharpoonright }_{{\mathit{r}}_{\mathit{n}}}\mathrm{)}⩾{\mathit{r}}_{\mathit{n}}-\mathit{c}$ , where $\mathrm{(}{\mathit{r}}_{\mathit{n}}\mathrm{)}$ is any fixed pointedly X-computable sequence, in the sense that ${\mathit{r}}_{\mathit{n}}$ is computable from X in a self-delimiting way, so that at most the first ${\mathit{r}}_{\mathit{n}}$ bits of X are queried in the computation of ${\mathit{r}}_{\mathit{n}}$ . On the other hand, we also show that there are reals X which are very far from being Martin-Löf random, but for which there exists some X-computable sequence $\mathrm{(}{\mathit{r}}_{\mathit{n}}\mathrm{)}$ such that $\forall \mathit{n}\mathit{K}\mathrm{(}\mathit{X}{\upharpoonright }_{{\mathit{r}}_{\mathit{n}}}\mathrm{)}⩾{\mathit{r}}_{\mathit{n}}$ .