The class of sets (or rather, degrees of sets) $D$ separating $A$ and $B$ is a well-studied class in computability theory called `PA degrees'. Indeed there PA degrees that are low (hence below $0'$), other that are hyperimmune-free (hence below $0'$), etc.

For the bonus part: it is known that for every PA degree $\mathbf{a}$ there is another PA-degree $\mathbf{b}$ stricly below $\mathbf{a}$ (via an easy adaptation of the argument given by Carl Mummert on this other forum). As to the last question: if you build a separator $D$ probabilistically as proposed, then with probability $1$ you'll have $D \geq 0'$. Indeed, suppose you have built a $D$ in such a manner. You want to know if some program $p$ halts. You can computably find countably many distinct arithmetical statements that express that $p$ halts. If $p$ really does halt, the corresponding bits of $D$ will all be equal to $1$. If $p$ does not halt, then the corresponding bits of $D$ will either all be $0$ (if PA proves that $p$ does not halt) or will be $0-1$ with probability $1/2-1/2$ (if PA cannot decide the halting status of $p$). It thus suffices to sample enough bits of $D$ and if you see a single $0$, you know that $p$ does not halt. Otherwise, you know that with high probability that $p$ does. And you can make the probability of success as high as you want, even across all programs. Thus $D$ computes $0'$ with probability $1$.

The class of sets (or rather, degrees of sets) $D$ separating $A$ and $B$ is a well-studied class in computability theory called `PA degrees'. Indeed there PA degrees that are low (hence below $0'$), other that are hyperimmune-free (hence incomparable with $0'$), etc.

For the bonus part: it is known that for every PA degree $\mathbf{a}$ there is another PA-degree $\mathbf{b}$ stricly below $\mathbf{a}$ (via an easy adaptation of the argument given by Carl Mummert on this other forum). As to the last question: if you build a separator $D$ probabilistically as proposed, then with probability $1$ you'll have $D \geq 0'$. Indeed, suppose you have built a $D$ in such a manner. You want to know if some program $p$ halts. You can computably find countably many distinct arithmetical statements that express that $p$ halts. If $p$ really does halt, the corresponding bits of $D$ will all be equal to $1$. If $p$ does not halt, then the corresponding bits of $D$ will either all be $0$ (if PA proves that $p$ does not halt) or will be $0-1$ with probability $1/2-1/2$ (if PA cannot decide the halting status of $p$). It thus suffices to sample enough bits of $D$ and if you see a single $0$, you know that $p$ does not halt. Otherwise, you know that with high probability that $p$ does. And you can make the probability of success as high as you want, even across all programs. Thus $D$ computes $0'$ with probability $1$.

The class of sets (or rather, degrees of sets) $D$ separating $A$ and $B$ is a well-studied class in computability theory called `PA degrees'. Indeed there PA degrees that are low (hence below $0'$), other that are hyperimmune-free (hence below $0'$), etc.

For the bonus part: it is known that for every PA degree $\mathbf{a}$ there is another PA-degree $\mathbf{b}$ stricly below $\mathbf{a}$ (via an easy adaptation of the argument given by Carl Mummert on this other forum). As to the last question: if you build a separator $D$ probabilistically as proposed, then with probability $1$ you'll have $D \geq 0'$. Indeed, suppose you have built a $D$ in such a manner. You want to know if some program $p$ halts. You can computably find countably many distinct arithmetical statements that express that $p$ halts. If $p$ really does halt, the corresponding bits of $D$ will all be equal to $1$. If $p$ does not halt, then the corresponding bits of $D$ will either all be $0$ (if PA proves that $p$ does not halt) or will be $0-1$ with probability $1/2-1/2$ (if PA cannot decide the halting status of $p$). It thus suffices to sample enough bits of $D$ and if you see a single $0$, you know that $p$ does not halt. Otherwise, you know that with high probability that $p$ does. And you can make the probability of success as high as you want, even across all programs. Thus $D$ computes $0'$ with probability $1$.

The class of sets (or rather, degrees of sets) $D$ separating $A$ and $B$ is a well-studied class in computability theory called `PA degrees'. Indeed there PA degrees that are low (hence below $0'$), other that are hyperimmune-free (hence below $0'$), etc.

For the bonus part: it is known that for every PA degree $\mathbf{a}$ there is another PA-degree $\mathbf{b}$ stricly below $\mathbf{a}$ (via an easy adaptation of the argument given by Carl Mummert on this other forum). As to the last question: if you build a separator $D$ probabilistically as proposed, then with probability $1$ you'll have $D \geq 0'$. Indeed, suppose you have built a $D$ in such a manner. You want to know if some program $p$ halts. You can computably find countably many distinct arithmetical statements that express that $p$ halts. If $p$ really does halt, the corresponding bits of $D$ will all be equal to $1$. If $p$ does not halt, then the corresponding bits of $D$ will either all be $0$ (if PA proves that $p$ does not halt) or will be $0-1$ with probability $1/2-1/2$ (if PA cannot decide the halting status of $p$). It thus suffices to sample enough bits of $D$ and if you see a single $0$, you know that $p$ does not halt. Otherwise, you know that with high probability that $p$ does. And you can make the probability of success as high as you want, even across all programs. Thus $D$ computes $0'$ with probability $1$.