• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

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