Weak reduction principle and computable metric spaces Full article
| Conference |
14th Conference on Computability in Europe 30 Jul - 3 Aug 2018 , Keil |
||||
|---|---|---|---|---|---|
| Journal |
Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349 |
||||
| Output data | Year: 2018, Volume: 10936 LNCS, Pages: 234-243 Pages count : 10 DOI: 10.1007/978-3-319-94418-0_24 | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
This paper is a part of the ongoing research on developing a foundation for studying arithmetical and descriptive complexity of partial computable functions in the framework of computable topology. We propose new principles for computable metric spaces. We start with a weak version of Reduction Principle (WRP) and prove that the lattice of the effectively open subsets of any computable metric space meets WRP. We illustrate the role of WRP within partial computability. Then we investigate the existence of a principal computable numbering for the class of partial computable functions from an effectively enumerable space to a computable metric space. We show that while in general such numbering does not exist in the important case of a perfect computable Polish space it does. The existence of a principal computable numbering gives an opportunity to make reasoning about complexity of well-known problems in computable analysis in terms of arithmetical and analytic complexity of their index sets. © 2018, Springer International Publishing AG, part of Springer Nature.
Cite:
Korovina M.
, Kudinov O.
Weak reduction principle and computable metric spaces
Lecture Notes in Computer Science. 2018. V.10936 LNCS. P.234-243. DOI: 10.1007/978-3-319-94418-0_24 Scopus OpenAlex
Weak reduction principle and computable metric spaces
Lecture Notes in Computer Science. 2018. V.10936 LNCS. P.234-243. DOI: 10.1007/978-3-319-94418-0_24 Scopus OpenAlex
Identifiers:
| Scopus: | 2-s2.0-85051112382 |
| OpenAlex: | W2811297303 |