2020/02/16 by Bauwens, Bruno, Blinnikov, Ilya
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2002.06683
It is known that the normalized algorithmic information distance N 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 |limt f(x,y,t) - 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/log n). This strengthens the ω(1) lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, Normalized information distance and the oscillation hierarchy], see arXiv:1708.03583 .