论文标题
限制复杂性，最少的描述和$ n $ - 随意性
Limit Complexities, Minimal Descriptions, and $n$-Randomness
论文作者
论文摘要
令$ k $表示前kolmogorov复杂性，而$ k^a $表示相对于甲骨文$ a $。我们表明，对于任何$ n $，$ k^{\ emptySet^{（n）}} $纯粹是根据不删除的概念$ k $定义的。众所周知，2随机是$ k $（和普通的复杂性$ c $），因为那些经常具有最大复杂性的真实性。我们可以使用我们的表征来表明$ n $ - 随意性纯粹是$ k $的。为此，我们从文献中扩展了一定的``limsup''公式，并应用了信息对称性。这种扩展需要对半曲集的新颖使用，以及对$δ_2^0 $ sets Mimimal描述的复杂性的更精确分析。
Let $K$ denote prefix-free Kolmogorov Complexity, and $K^A$ denote it relative to an oracle $A$. We show that for any $n$, $K^{\emptyset^{(n)}}$ is definable purely in terms of the unrelativized notion $K$. It was already known that 2-randomness is definable in terms of $K$ (and plain complexity $C$) as those reals which infinitely often have maximal complexity. We can use our characterization to show that $n$-randomness is definable purely in terms of $K$. To do this we extend a certain ``limsup'' formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $Δ_2^0$ sets of mimimal descriptions.
