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 𝜀<1/2, there exist no semicomputable functions that differ from N by at most 𝜀. Moreover, for any computable function f such that |lim𝑡𝑓(𝑥,𝑦,𝑡)−N(𝑥,𝑦)|≤𝜀 and for all n, there exist strings x, y of length n such that
∑_𝑡 |𝑓(𝑥,𝑦,𝑡+1)−𝑓(𝑥,𝑦,𝑡)| ≥ 𝛺(log 𝑛)
This is optimal up to constant factors.
We also show that the maximal number of oscillations of a limit approximation of N is 𝛺(𝑛/log𝑛). This strengthens the 𝜔(1) lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, Normalized information distance and the oscillation hierarchy].