Iskander Sh. Kalimullin

This paper shows that the degree spetrum of any algebrai struture is equal to the degree spetrum of a linear ordering enrihed with an additional equivalene relation. The tehnique used in the proof allowed us to obtain results and formulate several problems onerning other aspets of the algorithmi universality of lasses of algebrai strutures with linearordering, inluding those related to the deidability of elementary theories and their bounded fragments

The paper is devoted to the study of punctual structures such that any isomorphism between any of its punctual copies is primitive recursively reducible to a fixed 0, 1-valued oracle function. To estimate the complexity of such punctual structures and isomorphisms between them we introduce and investigate the weak (0, 1-valued) jump operation. In the paper we establish that there is a rigid punctual structure for which all isomorphisms are low under the weak jump, and at least one of them is not primitive recursive. Also we construct a rigid punctual structure with every isomorphism reducible to the weak jump of the zero function, and with at least one having a high degree.

We study the classes of Turing degrees of selector functions in which a rigid computable structure is relatively computably categorical. It is proved that for some structures such classes of degrees can be represented as the unions of upper cones of c.e. degrees. In addition we show that there are non-c.e. upper cones realized as the degrees in which some computable structure is relatively computably categorical.

We describe constructions that are used in the proof of the main result of the first part of the article. They are based on automorphisms and properties of the Cantor space.