Category Archives: Open problems

No-randomness-from-nothing for computable randomness

Leave a reply

I recently added the short article “No-randomness-from-nothing for computable randomness” to the 2014 PDF Logic Blog.

There are two important properties that one would like a notion of algorithmic randomness to have.  The first is called randomness preservation.  It says that if $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is a computable measure-preserving map and $X \in \{0,1\}^\mathbb{N}$ is random, then so is $T(X)$.  While this property holds for most randomness notions—Kurtz randomness, Schnorr randomness, Martin-Löf randomness, weak $n$-randomness, difference randomness, Demuth randomness, Oberwolfach randomness, and $n$-randomness—it fails for computable randomness. (Nonetheless, I have work in preparation—extending previous work—showing that randomness preservation for computable randomness holds for all “naturally occurring” computable measure-preserving maps, but this is not the purpose of this article.)

The purpose of this article to show that the dual property, no-randomness-from-nothing, holds for computable randomness.

Theorem (No-randomness-from-nothing for computable randomness).  Assume $\mu$ is a computable measure and $T:\{0,1\}^\mathbb{N} \rightarrow \{0,1\}^\mathbb{N}$ is an a.e. computable measure-preserving map.  If $Y \in \{0,1\}^\mathbb{N}$ is computably random, then there is some $X \in \{0,1\}^\mathbb{N}$ such that $T(X)=Y$.

(The proof can be found in the PDF Logic Blog.)

It is previously known that no-randomness-from-nothing holds for Martin-Löf randomness, weak $n$-randomness ($n\geq2$), and $n$-randomness.  This theorem answers a question of Bienvenu and Porter, who asked if it is true for Schnorr and computable randomness. The Schnorr randomness case still remains open.

Open question.  Does no-randomness-from-nothing hold for Schnorr randomness?

(Although, once again, I have work in preparation showing that no-randomness-from-nothing for Schnorr randomness holds for all “naturally occurring” computable measure-preserving maps.)

CCR 2014: Open questions

Leave a reply

For a slightly more detailed discussion of the following questions, see the PDF version of the Logic Blog.

Computable randomness

Let $\mathrm{CR}$ denote the class of computably random sets.

Question. (van Lambalgen’s theorem for $\mathrm{CR}$) Let $X$ be computably random, and let $Y$ be computably random relative to $X$. Is $X \oplus Y$ computably random?

Question. (Joseph Miller) Let $X$ be computably random. Is there an incomputable oracle $A$ such that $X$ is computably random relative to $A$?

 

Let $\textrm{High}(\textrm{CR}, \textrm{MLR})$ denote the class of oracles $A$ such that $\textrm{CR}^A \subseteq \textrm{MLR}$.

Question. (Joseph Miller) Is every set in  $\mathrm{High}(\mathrm{CR}, \mathrm{MLR})$ PA-complete?

 

We write $A \le_{\mathrm{CR}} B$ if $\mathrm{CR}^B \subseteq \mathrm{CR}^A$.

Question.  (Nies) Is $\le_{\mathrm{CR}}$ equivalent to $\le_\mathrm{T}$?

 

Martin-Löf randomness

Let $A \triangle B$ denote the symmetric difference of sets $A$, $B$.

Definition. (Kihara) We say that $A$ is ML-additive if $Z \in \mathrm{MLR}$ implies $Z \triangle A\in \mathrm{MLR}$ for each $Z$.

Clearly every low for ML-random is ML-additive.

Question. Is every ML-additive oracle low for ML-randomness?

 

Definition. (Yu) We say $A$ is absolutely low for $R$ if for all $Y$,

$R \in \mathrm{MLR}^Y \rightarrow R\in\mathrm{MLR}^{Y\oplus A}.$

Fact. (Stephan and Yu) Let  $A$ be $K$-trivial. Then $A$ is absolutely low for $\Omega$.

Question. (Yu) Is every set that is absolutely low for $\Omega$ $K$-trivial?

Definition. (Merkle) We say an oracle $A$ is super-absolutely low for $\Omega$  if for each oracle  $Y$ which is low for $\Omega$,

$\forall n(K^Y(n)=K^{A\oplus Y}(n)+O(1)).$

Note that every such set  is  absolutely low for $\Omega$ by definition. In fact it  must be  low for $K$, by letting $Y= \emptyset$. We ask the converse.

Question. (Merkle) Is every low for $K$ set super-absolutely low for $\Omega$?

A first open question

1 Reply

First of all: thanks to Rupert for putting up this blog. It looks great! My first post will be a question which I stumbled upon while working on effective Brownian motion with Kelty Allen:

Let $X$ be an ML random real and $Y$ some real. Is there always a sequence $R$ of rationals converging to $Y$ such that $X$ is random relative to $R$?

Of course the only interesting case is when $X$ is not ML-random relative to $Y$. Note that the answer is no if we further ask $R$ to be nondecreasing (take $X=\Omega$ and $Y=1-\Omega$: any nondecreasing sequence converging to $1-\Omega$ computes $1-\Omega$ so it derandomizes $X$)

Open questions from ARA

1 Reply

A list of open problems as discussed during the 2013 La Mothe retreat and during ARA 2013 in Nancy.

Computable randomness

If \(X\) is computably random and \(Y\) is \(X\)-computably random, is \(X \oplus Y\) computably random?

[J. Miller] Is there a computably random \(X\) such that for every non-computable \(Y\), \(X\) is not \(Y\)-computably random?

Randomness and Turing degrees

Continue reading →