Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-94418-0_24 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Numbering,Discrete mathematics,Combinatorics,Computability,Descriptive complexity theory,Metric space,Polish space,Computable function,Mathematics,Computable topology,Computable analysis | Conference | 10936 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
9 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Margarita V. Korovina | 1 | 84 | 15.61 |
| Oleg V. Kudinov | 2 | 105 | 15.85 |