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.
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 |