The subject of computable model theory gives real substance to the phenomenon you describe, and in the context of countable structures at least, takes it to the next level. The question shouldn't be merely that two objects are isomorphic (or equivalent), but "there is no known computable isomorphism", but rather: you should want there provably to be no computable isomorphism. This is precisely the topic of much of computable model theory. In computable model theory, one undertakes to do model theory, but with a view to the computability of the structures and theories that arise. In particular, in computable model theory one pays very much attention to the question of whether isomorphisms might be computable.

• A good example: any two computable presentations of the rational order (a countable endless dense linear order) are isomorphic by a computable isomorphism. Thus, the rational order is computably categorical.

• bad examples: it gets as bad as you could possibly want. Namely, Goncharov proved that for each n<=ω, there is a computable structure with dimension n. This means that the computable presentations split into n nonempty classes of structures, such that all the structures are classically isomorphic, but computable isomorphisms exist only within the classes and never between the classes. (See S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra i Logika, 19 (1980), 621-639.)

I believe that Goncharov's theorem is a sweeping answer to your question, at least in the case of countable structures. And to summarize more generally, the fact that there are myriad provably distinct isomorphism notions in the context of computability, I believe, is one way of looking at what your question is really about.

The subject of computable model theory gives real substance to the phenomenon you describe, and in the context of countable structures at least, takes it to the next level. The question shouldn't be merely that two objects are isomorphic (or equivalent), but "there is no known" computable isomorphism, but rather: you should want there provably to be no computable isomorphism. This is precisely the topic of much of computable model theory. In computable model theory, one undertakes to do model theory, but with a view to the computability of the structures and theories that arise. In particular, in computable model theory one pays very much attention to the question of whether isomorphisms might be computable.

Some good examples:

• Dense linear orders. Any two computable endless dense linear orders (such as the rationals) are isomorphic by a computable isomorphism. Thus, the rational order is computably categorical.

• Atomless Boolean algebras. Any two computable atmoless Boolean algebras are computably isomorphic.

• Algebraically closed fields. This is a decidable theory and therefore has computable models (in any given characteristic). Ershov proved that an ACF is computably categorical iff it has finite transcendence degree over its prime subfield. Thus, for example, any two computable presentations of the algebraic numbers are computably isomorphic.

Some bad examples:

• It gets as bad as you could possibly want. Goncharov proved that for each n<=ω, there is a computable structure with dimension n. This means that the computable presentations split into n nonempty classes of structures, such that all the structures are classically isomorphic, but computable isomorphisms exist only within the classes and never between the classes. (See S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra i Logika, 19 (1980), 621-639.)

• Goncharov and others have used this method to produce examples of groups, partially orders sets, unary and other algebras of any computable dimension n. See this survey paper.

• The Natural numbers (N,<) have a computable presentation in which the successor function is not computable. See Shore's article.

• More generally, the spectrum of a model is the collection of Turing degrees of the presentations of that model. Knight proved that every non-trivial structure A has isomorphic copies of any higher Turing degree. See this presentation.

This last fact provides universal examples of your phenomenon, because it shows that any nontrivial structure (group, graph, partial order, etc.) will have isomorphic copies for which there is no computable isomorphism, even with oracles for one of the structures.

Thus, I take Knight's and Goncharov's theorems as a sweeping answer to your question, at least in the case of countable structures. And to summarize more generally, the fact that there are myriad provably distinct isomorphism notions in the context of computability, I believe, is one way of looking at what your question is really about.

The subject of computable model theory gives real substance to the phenomenon you describe, and indeed, takes it to the next level. The question shouln't be merely that two objects are isomorphic (or equivalent), but "there is no known computable isomorphism", but rather: you should want there provably to be no computable isomorphism. This is precisely the topic of much of computable model theory. In computable model theory, one undertakes to do model theory, but with a view to the computability of the structures and theories that arise. In particular, in computable model theory one pays very much attention to the question of whether isomorphisms might be computable.

It turns out that there is a twisted knot of variations on the concept of isomorphism and categoricity when computability enters the picture. For example, we know what it means to say that two countable structures A and B are isomorphic. But what should it mean to say that they are computably isomorphic? Let us suppose that A and B have underlying set ω. Do you mean that there is a computable bijection of ω that is an isomorphism of A with B? What if A and B have computable presentations, and all of them happen to be isomorphic? Do you insist that the witnessing isomorphisms be computable? What if they have computable presentations, which are all isomorphic, but not all of those isomorphisms are computable? What if the isomorphism class of the computable presentations of A splits into subclasses determined by whether there is a computable isomorphism or not? A similar picture arises with categoricity. Classicially, a theory is countably categorical if all its countable models are isomorphic. In computable model theory, what should we mean by computable cateogoricity? Do we mean only that all computable models of the theory are isomorphic? Do you insist that all computable models of the theory be isomorphic by computable isomorphsism? etc. etc. etc.

The jumble is by now, of course, sorted out by the practitioners, and there is an established terminology to cover these diverse situations. For example, here you find that two computable structures A and B are of the same computable isomorphism type if there is computable isomorphism taking A to B. The dimension of a structure A is the number of computable isomorphism types of computable structures (classically) isomorphic to A. A computable structure A is computably categorical if every computable structure isomorphic to A is computably isomorphic to A, or equivalently, if the dimension of A is 1.

• A good example: any two computable presentations of the rational order (a countable endless dense linear order) are isomorphic by a computable isomorphism. Thus, the rational order is computably categorical.

• bad examples: it gets as bad as you could possibly want. Namely, Goncharov proved that for each n<=ω, there is a computable structure with dimension n. This means that the computable presentations split into n nonempty classes of structures, such that all the structures are classically isomorphic, but computable isomorphisms exist only within the classes and never between the classes. (See S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra i Logika, 19 (1980), 621-639.)

I believe that Goncharov's theorem is a sweeping answer to your question. And to summarize more generally, the fact that there are myriad provably distinct isomorphism notions in the context of computability, I believe, is exactly the phenomenon that your question is about.

The subject of computable model theory gives real substance to the phenomenon you describe, and in the context of countable structures at least, takes it to the next level. The question shouldn't be merely that two objects are isomorphic (or equivalent), but "there is no known computable isomorphism", but rather: you should want there provably to be no computable isomorphism. This is precisely the topic of much of computable model theory. In computable model theory, one undertakes to do model theory, but with a view to the computability of the structures and theories that arise. In particular, in computable model theory one pays very much attention to the question of whether isomorphisms might be computable.

It turns out that there is a twisted knot of variations on the concept of isomorphism and categoricity when computability enters the picture. For example, we know what it means to say that two countable structures A and B are isomorphic. But what should it mean to say that they are computably isomorphic? Let us suppose that A and B have underlying set ω. Do you mean that there is a computable bijection of ω that is an isomorphism of A with B? What if A and B have computable presentations, and all of them happen to be isomorphic? Do you insist that the witnessing isomorphisms be computable? What if they have computable presentations, which are all isomorphic, but not all of those isomorphisms are computable? What if the isomorphism class of the computable presentations of A splits into subclasses determined by whether there is a computable isomorphism or not? A similar picture arises with categoricity. Classicially, a theory is countably categorical if all its countable models are isomorphic. In computable model theory, what should we mean by computable cateogoricity? Do we mean only that all computable models of the theory are isomorphic? Do you insist that all computable models of the theory be isomorphic by computable isomorphsism? etc. etc. etc.

The jumble is by now, of course, sorted out by the practitioners, and there is an established terminology to cover these diverse situations. For example, here you find that two computable structures A and B are of the same computable isomorphism type if there is computable isomorphism taking A to B. The dimension of a structure A is the number of computable isomorphism types of computable structures (classically) isomorphic to A. A computable structure A is computably categorical if every computable structure isomorphic to A is computably isomorphic to A, or equivalently, if the dimension of A is 1.

• A good example: any two computable presentations of the rational order (a countable endless dense linear order) are isomorphic by a computable isomorphism. Thus, the rational order is computably categorical.

• bad examples: it gets as bad as you could possibly want. Namely, Goncharov proved that for each n<=ω, there is a computable structure with dimension n. This means that the computable presentations split into n nonempty classes of structures, such that all the structures are classically isomorphic, but computable isomorphisms exist only within the classes and never between the classes. (See S. S. Goncharov, The Problem of the Number Of Non-Self-Equivalent Constructivizations, Algebra i Logika, 19 (1980), 621-639.)

I believe that Goncharov's theorem is a sweeping answer to your question, at least in the case of countable structures. And to summarize more generally, the fact that there are myriad provably distinct isomorphism notions in the context of computability, I believe, is one way of looking at what your question is really about.