Let a program p on input a output b. We are looking for a shorter program p' having the same property (p'(a)=b). In addition, we want p' to be simple conditional to p (this means that the conditional Kolmogorov complexity K(p'|p) is negligible). In the present paper, we prove that ... more >>>

Predictive complexity is a generalization of Kolmogorov complexity which gives a lower bound to ability of any algorithm to predict elements of a sequence of outcomes. A variety of types of loss functions makes it interesting to study relations between corresponding predictive complexities. Non-linear inequalities between predictive complexity of non-logarithmic ... more >>>

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 are ... more >>>

A string $p$ is called a program to compute $y$ given $x$ if $U(p,x)=y$, where $U$ denotes universal programming language. Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$ is defined as minimum length of a program to compute $y$ given $x$. Let $K(x)$ denote $K(x|\text{empty string})$ (Kolmogorov complexity of $x$) ... more >>>

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$ such that ... more >>>