Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples.We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian _p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated.

Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we describe some recent work on classification in computable structure theory.Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work.

Makkai [10] produced an arithmetical structure of Scott rank ω₁^CK. In [9], Makkai's example is made computable. Here we show that there are computable trees of Scott rank ω₁^CK. We introduce a notion of “rank homogeneity”. In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated “group trees” of [10] and [9], Using the same kind of trees, we obtain one of rank ω₁^CK that is “strongly computably approximable”. We also develop some technology that may yield further results of this kind.