That's fantastic, thanks! I was able to get the upper bound of $2^{n+1}\cdot n^2$ using the probabilistic method and some optimization. The lower bound seems a lot more mysterious, but now I know where to look.

@GerryMyerson That's a beautiful example, thanks! This suggests that the rest of my upper bounds are pretty terrible.

@NoahSchweber is right. For example, how would you translate WKL into a Weihrauch problem? It should take a tree in $2^{<\omega}$ to an infinite path through the tree. That's a partial multifunction.

Peter: Yes, exactly. The coding is a little trickier because you need all of the sets to simultaneously tell you whether you're forcing truth or falsity. The second and third proofs mentioned in 喻 良's answer use different tricks to ensure that this is possible.

I don't know why 喻 良 is being so cheeky. The multiple degree version of Posner–Robinson is Theorem 3 in the Posner–Robinson paper. And he knows of two Jockusch–Shore style proofs (unpublished, as of yet)

It's true that wlad gave a very natural problem that can't be computably solved, can be solved with the halting problem, and which doesn't require the halting problem. However, the problem doesn't naturally have a Turing degree; put differently, there is no least Turing degree solution. To some extent, it depends on what you mean by "problem". Wlad's problem has Muchnik degree (or Medvedev degree), but doesn't give us a "natural" noncomputable Turing degree below the halting problem.

I really like the last point, Ted. Similarly, the theory of $\mathcal{R}_X$ is decided on-a-cone. But since we can't hope to pick out the parameters that code $X$, it must be the case that on-a-cone not every element of $\mathcal{R}_X$ can be definable (in $\mathcal{R}_X$). Which is still open for $\mathcal{R}$, I think.

I assume that @1.. wants the Kolmogorov complexity notion to apply to finite dimensional density matrices. Classical Kolmogorov complexity is a bad fit for this.

The notion was introduced by Reimann and Slaman. They say that $A$ is never continuously random (NCR) if there is no continuous measure $\mu$ such that $A$ is Martin-Löf random with respect to $\mu$, where $\mu$ is used both as an oracle for the test and to measure the size of the test elements. To be precise, we don't use $\mu$ as an oracle, but discrete "names" of $\mu$; if for every name $m$ of $\mu$ there is a $\mu$-ML test relative to $m$ that covers $A$, then $A$ is not Martin-Löf random with respect to $\mu$.