By "structure," I mean "countable first-order structure in a computable language." And I'm comfortable with whatever set-theoretic hypotheses make things most interesting, should such things be relevant.
This is a question of computable structure theory; basically, I'm asking for a natural example of the inequivalence of two natural notions of relative complexity of structures.
Intuitively, one structure should be "computable relative to" another if there is an algorithm for converting the latter into the former. This is a bit messy to make precise, however, since we only have a good computability theory for sets of natural numbers rather than arbitrary structures. We can largely repair this by talking about copies (with domain $\subseteq\omega$) instead: say that $\mathcal{A}$ is simpler than $\mathcal{B}$ if every copy of $\mathcal{B}$ computes a copy of $\mathcal{A}$.
There is still a subtlety here, namely: what level of uniformity do we demand? On one side we have the fully-uniform reducibility, Medvedev (or strong) reducibility: $\mathcal{A}\le_s\mathcal{B}$ if there is some Turing machine $\Phi_e$ such that $\Phi_e^B$ is a copy of $\mathcal{A}$ whenever $B$ is a copy of $\mathcal{B}$ (here conflating $B$ with the set of natural numbers coding its atomic diagram). On the other side we have the fully-nonuniform reducibility, Muchnik (or weak) reducibility: $\mathcal{A}\le_w\mathcal{B}$ if for every copy $B$ of $\mathcal{B}$, there is some $e\in\omega$ such that $\Phi_e^B$ is a copy of $\mathcal{A}$.
It's easy to see that these behave quite differently. However, they are not the only options. One particularly interesting intermediate reducibility is Medvedev modulo parameters: $\mathcal{A}\le_{s/p}\mathcal{B}$ if there is some finite tuple $\overline{c}\in\mathcal{B}$ such that $\mathcal{A}\le_s(\mathcal{B},\overline{c})$, where $(\mathcal{B},\overline{c})$ denotes the structure gotten by adding constant symbols to explicitly name the elements of $\overline{c}$.
A reasonable (and apparently common) guess is that $\le_{s/p}$ is just $\le_w$. However, this turns out to be wrong: while a standard forcing argument shows that if $\mathcal{A}\le_w\mathcal{B}$ then there is some tuple $\overline{c}$ and some $e\in\omega$ such that $\Phi_e^{B}$ is a copy of $\mathcal{A}$ whenever $B$ is a sufficiently generic copy of $(\mathcal{B}, \overline{c})$, it turns out that the genericity requirement is crucial (note that there are times it can be removed).
The only counterexample I know is due to Kalimullin, and while quite nice is definitely artificial. My question is:
Are there any natural examples of structures $\mathcal{A},\mathcal{B}$ such that $\mathcal{A}\le_w\mathcal{B}$ but $\mathcal{A}\not\le_{s/p}\mathcal{B}$?
Incidentally, in light of Kalimullin's counterexample I think $\le_{s/p}$ is much more mysterious than it may appear. For example, I don't think it's known whether it is in fact transitive despite the notation (and I suspect it isn't transitive in general).
More interestingly, I would love to know hypotheses which guarantee good behavior: e.g. for what $\mathcal{B}$ do we have $\mathcal{A}\le_w\mathcal{B}\iff\mathcal{A}\le_{s/p}\mathcal{B}$? But I think such questions are probably extremely hard, so I'm focusing on the concrete one above.
