Logic Seminar

Russell Miller, Queens College - City University of New York

"Effective Classification of Computable Structures”

Many classes of computable structures can be enumerated computably. For example, one readily gives a uniformly computable list of all computable linear orders, simply by enumerating the c.e. sub- sets of a single computable dense linear order. Of course, this list includes infinitely many computable copies of each computable linear order. To give a computable classification (up to isomorphism) of these linear orders would require computing such a list so that no two linear orders on the list are (classically) isomorphic to each other. This is known to be impossible.

The paradigm of a computable classification was given by Friedberg, who produced a uniformly computable listing of all c.e. sets, with no set appearing more than once in the listing. That is, he gave a computable classification of the c.e. sets up to equality. In joint work, Lange, Steiner, and the speaker have applied his method to yield a computable classification of the computable algebraic fields, up to (classical) isomorphism. We also follow Goncharov and Knight in showing that certain other classes have no computable classification.

Additionally, we give a 0’-computable classification of the computable equivalence structures. This result, which extends (and uses) more work of Goncharov and Knight, means that there is a uniformly 0’-computable listing of all computably presentable equivalence structures, with no isomorphisms be- tween any two distinct structures on the list; however, the structures on the list are only 0’-computable, not necessarily computable. We conjecture that there is no computable classification of the computable equivalence structures.

M3-4206