The sum 2 KM(x) K(x) over all prefixes x of some binary sequence can be infinite

2014 
We consider two quantities that measure complexity of binary strings: KM(x) is defined as the minus logarithm of continuous a priori probability on the binary tree, and K(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 w such that the sum of 2 KM(x) K(x) over all prefixes x of w is infinite. Such a sequence can be chosen among characteristic sequences of computably enumerable sets.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    10
    References
    0
    Citations
    NaN
    KQI
    []