Computable elements and functions in effectively enumerable topological spaces
Computable elements and functions in effectively enumerable topological spaces
复制标题
有效可枚举拓扑空间中的可计算元素和函数
DOI：
10.1017/s0960129516000141
复制
发表时间：
2016
影响因子：
0.5
通讯作者：
O. Kudinov
中科院分区：
文献类型：
--
作者：
M. Korovina;O. Kudinov
本文是正在进行的程序的一部分，分析的复杂性，在可计算分析的各种问题的复杂性，在相关的索引集。在有效可计算拓扑空间的框架下，我们研究了以下问题：给定一个有效可计算拓扑空间，是否存在其所有可计算元素的可计算编号。我们提出了一个自然的充分条件家庭的基本邻域的可计算元素，保证存在一个主要的可计算编号。我们证明了弱有效ω-连续域和具有离散拓扑的自然数满足这个条件。我们证明弱和强类似的赖斯定理的可计算元素。然后，我们构造了部分优可计算实值函数和余有效闭集的主可计算数，并计算了根验证和函数等式等重要问题的指标集的复杂性。例如，我们表明，部分优可计算的真实的功能，等式问题是101 1-完全的。
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 ω–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 Π1 1-complete.