B. Khoussainov et Ra. Shore, COMPUTABLE ISOMORPHISMS, DEGREE SPECTRA OF RELATIONS, AND SCOTT FAMILIES, Annals of pure and applied Logic, 93(1-3), 1998, pp. 153-193
The spectrum of a relation R on a computable structure is the set of T
uring degrees of the image of R under all isomorphisms between A and a
ny other computable structure B. The relation R is intrinsically compu
tably enumerable (c.e.) if its image under all such isomorphisms is c.
e. We prove that any computable partially ordered set is isomorphic to
the spectrum of an intrinsically c.e. relation on a computable struct
ure. Moreover, the isomorphism can be constructed in such a way that t
he image of the minimum element (if it exists) of the partially ordere
d set is computable. This solves the spectrum problem. The theorem and
modifications of its proof produce computably categorical structures
whose expansions by finite number of constants are not computably cate
gorical and, indeed, ones whose expansions can have any finite number
of computable isomorphism types. They also provide examples of computa
bly categorical structures that remain computably categorical under ex
pansions by constants but have no Scott family. (C) 1998 Published by
Elsevier Science B.V. All rights reserved.