Problems in Randomness

  1. Is there an injective oneway function on the reals?
Is there a partial computable real function $f$ such that
  • $f$ is injective and preserves randomness
  • the domain of $f$ has positive Lebesgue measure
  • $f(x) <_T x$ for almost all $x$ in the domain of $f$.
  1. Is the jump operator on the Turing degrees strictly monotone almost everywhere?
The question is non-trivial for 2-randomness:
  • Are there 2-random reals $x<_T y$ with $x' \equiv_T y'$?

  • is there a Turing ideal which is generated by an infinite chain of 2-random reals that starts with $x$, and contains no real that is 2-random relative to $x$?

  • Are there 2-random reals $x<_T y$ with $x \equiv_K y$?

This is related to question 1: from an injective oneway function we can obtain an infinite chain of 2-random degrees with the same jump.

  1. Is every c.e. set equivalent to a c.e. set of even numbers, with respect to initial segment Kolmogorov complexity?
This can be formalized with respect to plain, prefix-free or conditional Kolmogorov complexity. Given a c.e. set $A$ is there a c.e. set $B$ of even numbers such that
  • $K(A\upharpoonright_n) = K(B\upharpoonright_n)$ where $K$ is the prefix-free Kolmogorov complexity
  • $C(A\upharpoonright_n) = C(B\upharpoonright_n)$ where $C$ is the plain Kolmogorov complexity
  • $C(A\upharpoonright_n \mid B\upharpoonright_n)= C(B\upharpoonright_n \mid A\upharpoonright_n) = O(1)$

where equalities hold for all $n$ up to a constant.