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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
10
References
0
Citations
NaN
KQI