We study relative precompleteness in the context of the theory of numberings, and relate this to a notion of lowness. We introduce a notion of divisibility for numberings, and use it to show that for the class of divisible numberings, lowness and relative precompleteness coincide with being computable. We also study the complexity of Skolem functions arising from Arslanov's completeness criterion with parameters. We show that for suitably divisible numberings, these Skolem functions have the maximal possible Turing degree. In particular this holds for the standard numberings of the partial computable functions and the c.e. sets.


翻译:我们从数字理论的角度研究相对不完整的问题,并将其与低度概念联系起来。我们引入了数字可分化的概念,并用它来表明,对于可分数的类别,低和相对不完整与可计算一致。我们还研究了Arslanov完整性标准产生的Skolem函数的复杂性和参数。我们证明,对于适当可分数的编号,这些Skolem函数具有最大可能的图灵度。特别是,这可以用于部分可分数函数和 c.e. 数据集的标准编号。

0
下载
关闭预览

相关内容

最新【深度生成模型】Deep Generative Models,104页ppt
专知会员服务
69+阅读 · 2020年10月24日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
论文浅尝 | Global Relation Embedding for Relation Extraction
开放知识图谱
12+阅读 · 2019年3月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
7+阅读 · 2018年10月12日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年3月18日
Arxiv
3+阅读 · 2018年4月3日
Arxiv
6+阅读 · 2017年12月7日
VIP会员
相关VIP内容
相关资讯
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
论文浅尝 | Global Relation Embedding for Relation Extraction
开放知识图谱
12+阅读 · 2019年3月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
已删除
将门创投
7+阅读 · 2018年10月12日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员