The normalized algorithmic information distance can not be approximated

P. 130–141.

Bauwens B. F., Blinnikov I.

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].

Keywords: Kolmogorov complexity, computability theory, Algorithmic information distance, oscillation hierarchy

Publication based on the results of: Mathematical methods in computational complexity theory and algorithm game theory (2020)

In book

Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings

Vol. 12159. , Springer, 2020.