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. 数据集的标准编号。