The normalized algorithmic information distance can not be approximated

Abstract

It is known that the normalized algorithmic information distance $N$ is not computable and not semicomputable. We show that for all $\epsilon <1/2$, there exist no semicomputable functions that differ from $N$ by at most~$\epsilon$. Moreover, for any computable function $f$ such that $|{\lim }_{t}f(x,y,t)-N(x,y)|\le \epsilon$ 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 \Omega (\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 $\Omega (n/\log n)$. This strengthens the $\omega (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 .

14 pages, 2 figures