论文标题
在算法维度，免疫力和Medvedev学位的新概念上
On New Notions of Algorithmic Dimension, Immunity, and Medvedev Degree
论文作者
论文摘要
我们证明了通过可计算理论的共同线程共同连接的各种结果。首先，我们研究了一个新的算法维度概念，即不可避免的维度，该尺寸位于有效的Hausdorff和填料维度之间。我们还研究了它的概括，将图灵程度嵌入到维度概念中。 然后，我们研究了在先前研究过程中产生的可计算性理论免疫的新概念，即一组无可相互衡量子集的自然数。我们演示了$π^0_1 $ -Immunity的这个概念如何连接到其他免疫概念，并在整个高/低/低和Ershov层次结构中构造$π^0_1 $ -MMUNE REALS。我们还研究那些无法计算或无法共归因于$π^0_1 $ -MMMUNE集的学位。最后，我们通过利用这样一个事实，即将Kolmogorov的随机输入转换为Martin-Löf随机输出，即通过利用这样一个事实，即这种KL随机本身就是ML随机，我们将讨论了最近发现的真相表减少。我们表明，没有更好的算法依靠这一事实，即，没有积极，线性或有限的真理表个子的减少。我们还将这些结果推广到从无限多个输入中输出随机性的问题，其中一些是随机的。
We prove various results connected together by the common thread of computability theory. First, we investigate a new notion of algorithmic dimension, the inescapable dimension, which lies between the effective Hausdorff and packing dimensions. We also study its generalizations, obtaining an embedding of the Turing degrees into notions of dimension. We then investigate a new notion of computability theoretic immunity that arose in the course of the previous study, that of a set of natural numbers with no co-enumerable subsets. We demonstrate how this notion of $Π^0_1$-immunity is connected to other immunity notions, and construct $Π^0_1$-immune reals throughout the high/low and Ershov hierarchies. We also study those degrees that cannot compute or cannot co-enumerate a $Π^0_1$-immune set. Finally, we discuss a recently discovered truth-table reduction for transforming a Kolmogorov--Loveland random input into a Martin-Löf random output by exploiting the fact that at least one half of such a KL-random is itself ML-random. We show that there is no better algorithm relying on this fact, i.e., there is no positive, linear, or bounded truth-table reduction which does this. We also generalize these results to the problem of outputting randomness from infinitely many inputs, only some of which are random.
