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.
Fulltext:
PDF file (1419 kB)