Open questions from ARA

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

[Adam Day] Is the class of difference random degrees convex? How about the difference random \(\Delta_2\) degrees?

Computable analysis, effective ergodic theory

A ML-random real is called density random if it satisfies the simplest effective version of the Lebesgue density theorem: every effectively closed class containing the real has density one at the real.

Let \(T\) be a computable measure-preserving transformation on Cantor space. Let \(f\) be lower semicomputable. Is every density random a Birkhoff point of \(f\)?

Effective analog of Rademacher’s theorem.

Suppose \(z\in [0,1]^n\) is computably random. Is each computable Lipschitz function \(f \colon \, [0,1]^n \rightarrow\mathbb R\) is differentiable at \(z\)?

Also converse.

[Bienvenu, Allen, Slaman] Are the zeroes of ML random Brownian motion closed upwards under \(K\)-reducibility?

Randomness notions

\(Z\) is Oberwolfach random iff \(Z\) is ML-random and fails to compute some \(K\)-trivial.

[Greenberg, Miller, Nies, Turetsky] Can we separate Oberwolfach randomness from density randomness?

Also: Characterize lowness for Oberwolfach randomness. This strictly contains strongly jump traceable, and implies \(K\)-trivial.

Is there an LR-hard Oberwolfach random?

[Calvert, Franklin] Is there a weakly 1-random real that is uniform distribution (UD-)random but not Schnorr random?


[Miyabe] Does the difficult direction of van Lambalgen’s theorem hold for uniform weak 2-randomness?

Randomness, image measures, effective measurability

[Rute] Assume \(f:2^\omega \rightarrow 2^\omega\) is truth-table computable. Denote the pushforward measure of \(f\) (along the Lebesgue measure \(\lambda\)) as \(\lambda_f\). Assume \(Y\) is Schnorr random (resp. computably random) on \(\lambda_f\). Is there some Schnorr random (resp. computably random) \(X\) such that \(f(X)=Y\)?

Note this last question is true for Martin-Löf randomness. It can also be made more general by allowing \(f\) to be effectively measurable or a.e. computable.

Kolmogorov complexity

We proved that \(K^X\geq_T X\) for all \(X\) (Turetsky, Miller; Bienvenu). Can this be done uniformly? Actually, if we build the universal oracle machine ourselves, we can code in such a way that decoding is uniform. But this leaves open:

  • Can we uniformly compute \(\emptyset’\) from \(K^{\emptyset’}_U\) given an index for the universal machine \(U\) and an index for its universality?
  • Can we uniformly compute \(X\) from \(K^X_U\) given \(X\), an index for the universal machine \(U\) and an index for its universality?

[Bauwens] Given three strings, can we find an oracle that halves their complexity? Various variants regarding the precision.

By Romaschchenko and Shen (CCR 2012), such an oracle exists for two strings.


A set \(Z\) is \(X\)-limitwise computable if there is an \(X\)-computable limit wise monotonic function \(f\) such that \(Z\) is the range of \(f\). Let \(LM(X)\) be the sets which are \(X\)-limitwise computable. It is known that for \(X <_T Y\), we have \(LM(X) \subset LM(Y)\).

[Kalimullin, Turetsky] If \(X \mid_T Y\), is \(LM(X) \neq LM(Y) \)?

A similar question was asked for linear orders by Kalimullin. In other words, are there \(X \mid_T Y\) that compute the same linear order-types?

[Franklin] Is there a universal \(X\)-limitwise computable set? That is, a \(Z \in LM(X)\) such that if \(Z \in LM(Y)\), then \(LM(X) \subseteq LM(Y)\)? Does one exist for some noncomputable \(X\)? For every noncomputable \(X\)?

Reverse Maths, Weihrauch lattice

[Gherardi] Are the Weihrauch degrees of weak weak Koenig’s Lemma and Vitali’s lemma the same?

They are known to be equivalent in reverse mathematics, but the computational complexity of the proof is trivial.

[Source: ARA 2013 website]

One thought on “Open questions from ARA

Leave a Reply