×

On the algorithmic dimension of unars. (Russian) Zbl 0668.03015

Models may have constructivizations with different algorithmic properties. To compare the constructivizations various algorithmic reducibilities and equivalences are introduced.
The author studies autoequivalence and essential equivalence of constructivizations and program reducibility and homogeneous reducibility introduced by V. A. Uspenskij [V. A. Uspenskij and A. L. Semenov: Theory of algorithms: basic discoveries and applications (Russian) (1987; Zbl 0632.68037)]. The author constructs some examples of unars with various combinations of numbers of non-equivalent (in the senses above) classes of constructivizations and some additional properties.
Reviewer: A.Morozov

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
03D30 Other degrees and reducibilities in computability and recursion theory

Citations:

Zbl 0632.68037