zbMATH — the first resource for mathematics

On the spectrum of degrees of decidable relations. (English. Russian original) Zbl 0961.03032
Dokl. Math. 55, No. 1, 55-57 (1997); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 352, No. 3, 301-303 (1997).
From the text: The general problem consists in the description of all degrees of unsolvability of realizations of algebraic solvable problems for different effective representations of the desired model. By an algebraic problem in a model \({\mathfrak M}\), we mean relations closed with respect to automorphic images and, by a decidable relation, we mean those relations that have a recursive set of numbers for at least one numbering of the class under consideration. In this case, we consider only those numberings that are constructivizations. Thus, the description of the lower complexity of the spectrum of degrees of unsolvability for relations in models of a finite algorithmic dimension is reduced to the construction of a model of algebraic dimension 2 and a decidable relation in this model that is recursively enumerable, but undecidable for another constructivization or, which is equivalent, belongs to \(\Sigma^0_1 \setminus \Sigma^0_0\). This paper is devoted to solving this problem.

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures