@cody Just literally the join of the reals coding them. Roughly, this is the binary sequence whose $2k$th bit is 1 iff the first structure satisfies the $k$th second-order sentence, and whose $2k+1$th bit is 1 iff the second structure satisfies the $k$th second-order sentence. (This isn't quite right because I actually want to look at second-order formulas being satisfied at tuples of elements, but meh.) So roughly, I'm asking about how being able to query each structure's second-order theory differs from being able to query the second-order theory of the "sum" of the structures.

Let $\mathcal{R}$ be the subring of $\mathcal{P}(\omega)/\mathit{Fin}$ consisting of (classes containing) sets of asymptotic density zero. Does this work?

@FarmerS Just some computable copy. Clarifying ...

@FarmerS I just realized what you're asking, sorry for the misunderstanding.

@FarmerS Oops, good catch, fixing!

@FarmerS A model (with domain $\mathbb{N}$) whose whole elementary diagram is computable. For example, $(\mathbb{N};+,\times)$ is a computable structure (= atomic diagram is computable) which is not decidable.

@PeterGerdes Yes, that's correct. More generally, every computable tree is isomorphic to one whose membership problem is polytime-decidable by a similar padding trick.

@DanTuretsky Whoops, good catch! Luckily the argument still works; we just need an infinite $\Pi^0_2$ set with no infinite $\Sigma^0_2$ subset. Fixed!

@JoelDavidHamkins Yes, that's right.