The normalized algorithmic information distance can not be approximated

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 .

No reviews yet.

No comments yet.