Non-Computability of Algorithmic Information Distance

Since the middle of the 20th century, many researchers have been trying to work with Kolmogorov Complexity. As a result, Normalized Information Distance has been described. It is an object strongly related to prefix Kolmogorov Complexity. In the last few years, there have been published several works on non-computability of it. In this thesis, we are improving the lower bound of the number of oscillations of any limit approximation of the function related to normalized information distance (with hardcoded length in the condition of prefix Kolmogorov Complexity). We are getting $\Omega(n)$ bound for it. This result improves the result of $\Omega(n/\log n)$ that was proven in recent work. The result of $\Omega(n)$ is proven with the help of Game Theory method: we describe such a game on semimeasures that finding a winning strategy is equivalent to proving the bound. This result can be used as proof that there should be problems with approximating normalized information distance.