The normalized algorithmic information distance can not be approximated

DOI10.1007/978-3-030-50026-9_9MaRDI QIDQ6334908arXivFDO

Authors B. Bauwens, Ilya Blinnikov

Publication date 16 February 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-50026-9_9

Mathematics Subject Classification ID

Theory of computing (68Qxx)

arXiv classification

cs.CCcs.ITmath.IT

Abstract: It is known that the normalized algorithmic information distance $N$ is not computable and not semicomputable. We show that for all $epsilon<1/2$, there exist no semicomputable functions that differ from $N$ by at most~$epsilon$. Moreover, for any computable function $f$ such that $|li{m}_{t}f(x,y,t)-N(x,y)|leepsilon$ and for all $n$, there exist strings $x,y$ of length $n$ such that $su{m}_t|f(x,y,t+1)-f(x,y,t)|geOmega(logn)$. This is optimal up to constant factors. We also show that the maximal number of oscillations of a limit approximation of $N$ is $Omega(n/logn)$. This strengthens the $omega(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 .

This page was built for publication: The normalized algorithmic information distance can not be approximated

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6334908)