Реферат: 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.

Библиографическая ссылка: 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

Идентификаторы БД:

Scopus:	2-s2.0-85051112382
OpenAlex:	W2811297303

Цитирование в БД:

БД	Цитирований
Scopus	1
OpenAlex	1

Альметрики: