Randomness of Index Sets

Jul 17, 2024 1 min read

Let $U$ be a universal prefix-free Turing machine.

Given $X\subset\omega$, let $\Omega[X]=\sum_{U(\sigma)\downarrow\in X}2^{-|\sigma|}$.

The following are straight forward observations:

$\{\Omega[X]:X\subset\omega\}=[0,\Omega]$.
For each $n$ there is a $\Delta^0_{n+1}$ set $X$ such that $A[X]$ is $n$-random.
For each $n$ there is a $\Sigma^0_n$-hard and $\Delta^0_{n+1}$ set such that $A[X]$ is rational.

One can show the following:

If $n\geq 2$ and $X$ is $\Sigma^0_n$ then $\Omega[X]$ is not $n$-random. [Reference]
If $X$ is $\Sigma^0_n$-complete then $\Omega[X]$ is random. [Reference]

Question. If $X$ is $\Sigma^0_3$-complete, can $A[X]$ be $2$-random? Can $A[X]$ be not $2$-random?