Paper Info
Title
Computable elements and functions in effectively enumerable topological spaces.
Abstract
This paper is a part of the ongoing program of analysing the complexity of various problems in computable analysis in terms of the complexity of the associated index sets. In the framework of effectively enumerable topological spaces, we investigate the following question: given an effectively enumerable topological space whether there exists a computable numbering of all its computable elements. We present a natural sufficient condition on the family of basic neighbourhoods of computable elements that guarantees the existence of a principal computable numbering. We show that weakly-effective omega-continuous domains and the natural numbers with the discrete topology satisfy this condition. We prove weak and strong analogues of Rice's theorem for computable elements. Then, we construct principal computable numberings of partial majorant-computable real-valued functions and co-effectively closed sets and calculate the complexity of index sets for important problems such as root verification and function equality. For example, we show that, for partial majorant-computable real functions, the equality problem is Pi(1)(1)-complete.
Year
DOI
Venue
2017
10.1017/S0960129516000141
MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE
Field
DocType
Volume
Discrete mathematics,Maximal set,Topological space,Recursive set,Recursively enumerable set,Recursively enumerable language,Topological vector space,Computable number,Topological tensor product,Mathematics
Journal
27
Issue
ISSN
Citations 
8
0960-1295
2
PageRank 
References 
Authors
0.38
13
2
Name
Order
Citations
PageRank
Margarita V. Korovina18415.61
Oleg V. Kudinov210515.85