I am interested in the following decision problem:

Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$ are isomorphic.

(A structure $A=(Dom(A),R_1,...,R_k)$ is represented by a tuple of formulas $(φ_{\sim},φ_1,...,φ_k)$ describing the interpretation in the expected way (namely, $φ_{\sim}$ defines an equivalence relation $\sim$ on a subset $V⊆\mathbb N^d$ for some $d\ge 0$, $Dom(A)=V/{\sim}$ is the set of its equivalence classes, and $φ_i$ is a formula describing the pullback of $R_i$ under the quotient mapping $V\rightarrow Dom(A)$; $φ_i$ has $n\cdot d$ free variables if $R_i$ has arity $n$.)

The structures $A,B$ are ω-categorical and therefore, whenever they are non-isomorphic, there is a sentence φ which distinguishes A from B. Since it can be effectively tested whether φ holds in A and in B, it follows that non-isomorphicity is recursively enumerable. Therefore, the question which remains is whether there is an effective witness of isomorphicity, which would probably require some form of structure theorem for these structures.

These structures are ω-categorical, ω-stable, and moreover they are coordinatized by indiscernible sets, as in the eponymous paper by Lachlan, so perhaps the structure theory developed in this paper could be of use. (In this question I ask if those two classes coincide:ω-categorical, ω-stable structure with trivial geometry not definable in the pure set).

My question could be generalized to structures which interpret in other structures with decidable first order theory, e.g., the dense linear order.