The normalized algorithmic information distance can not be approximated

Bruno Bauwens, Ilya Blinnikov

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 function…