论文标题
不能近似归一化算法信息距离
The normalized algorithmic information distance can not be approximated
论文作者
论文摘要
众所周知，归一化算法信息距离$ n $是不可计算的，也不可半计算。我们表明，对于所有$ε<1/2 $，没有与$ n $不同的半计算函数最多〜$ε$。此外，对于任何可计算功能$ f $ \leε$，对于所有$ n $，存在$ x，y $ a length $ n $的y $，以便$ \ sum_t | f（x，y，t+1）-f（x，x，y，y，t）| \geΩ（\ log n）$。这是最佳选择的最佳因素。我们还表明，$ n $的限制近似值的最大振荡数为$ω（n/\ log n）$。这加强了$ω（1）$从[K。 Ambos-Spies，W。Merkle和S.A. Terwijn，2019年，归一化信息距离和振荡层次结构]，请参见Arxiv：1708.03583。
It is known that the normalized algorithmic information distance $N$ is not computable and not semicomputable. We show that for all $ε< 1/2$, there exist no semicomputable functions that differ from $N$ by at most~$ε$. Moreover, for any computable function $f$ such that $|\lim_t f(x,y,t) - N(x,y)| \le ε$ and for all $n$, there exist strings $x,y$ of length $n$ such that $\sum_t |f(x,y,t+1) - f(x,y,t)| \ge Ω(\log n)$. This is optimal up to constant factors. We also show that the maximal number of oscillations of a limit approximation of $N$ is $Ω(n/\log n)$. This strengthens the $ω(1)$ lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, Normalized information distance and the oscillation hierarchy], see arXiv:1708.03583 .
