Problems in Randomness
- 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$.
- 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.
- 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.