The sum $2^{KA(x)-KP(x)}$ over all prefixes $x$ of some binary sequence can be infinite

Abstract

We consider two quantities that measure complexity of binary strings: $KA(x)$ is defined as the minus logarithm of continuous a priori probability on the binary tree, and $KP(x)$ denotes prefix complexity of a binary string $x$. In this paper we answer a question posed by Joseph Miller and prove that there exists an infinite binary sequence $\omega$ such that the sum of $2^{KA(x)-KP(x)}$ over all prefixes $x$ of $\omega$ is infinite. Such a sequence can be chosen among characteristic sequences of computably enumerable sets.