|
Relative Complexity for Computable Representations of the Conventional Linear Order on the Set of Naturals
S. Yu. Podzorov Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
Abstract:
In the present article, we study the relationship between computable representations of the set of naturals with the conventional linear order. Two reducibility relations are introduced on the set of all such representations. Each of these relations determines a certain partially ordered set of degrees. We consider some questions concerning the algebraic structure of these posets and the interlocation of various degrees.
Key words:
computable function, computable representation, linear order, reducibility, degrees of unsolvability.
Received: 27.03.2001
Citation:
S. Yu. Podzorov, “Relative Complexity for Computable Representations of the Conventional Linear Order on the Set of Naturals”, Mat. Tr., 5:1 (2002), 114–128; Siberian Adv. Math., 12:4 (2002), 44–56
Linking options:
https://www.mathnet.ru/eng/mt103 https://www.mathnet.ru/eng/mt/v5/i1/p114
|
Statistics & downloads: |
Abstract page: | 205 | Full-text PDF : | 89 | References: | 45 | First page: | 1 |
|