The normalized algorithmic information distance can not be approximated

It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all \(\varepsilon < 1/2\), there exist no semicomputable functions that differ from \(\mathrm {N}\) by at most \(\varepsilon \). Moreover, for any computable function f such that \(|\lim _t f(x,y,t) - \mathrm {N}(x,y)| \le \varepsilon \) and for all n, there exist strings x, y of length n such that \(\sum _t \left| f(x,y,t+1) - f(x,y,t)\right| \ge \varOmega (\log n)\). This is optimal up to constant factors.