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_t f(x, y, i) - N(x,y)| ≤ ε and for all n, there exist strings x,y of length n such that Σ_t|f(x, y,t + 1) - f(x, y,t)| ≥ Ω(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/ logn). This strengthens the ω(1) lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, Normalized information distance and the oscillation hierarchy].