Mikhail V. Vyugin

C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.H.~Zurek

have defined information distance between two strings $x$, $y$

as

$$

d(x,y)=\max\{ K(x|y), K(y|x) \}

$$

where $K(x|y)$ is the conditional Kolmogorov complexity.

It is easy to see that for any string $x$ and any integer $n$

there is a string $y$ ...
more >>>

Mikhail V. Vyugin, Vladimir Vyugin

A new notion of predictive complexity and corresponding amount of

information are considered.

Predictive complexity is a generalization of Kolmogorov complexity

which bounds the ability of any algorithm to predict elements of

a sequence of outcomes. We consider predictive complexity for a wide class

of bounded loss functions which ...
more >>>