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

Abstract: We consider two quantities that measure complexity of binary strings:

m a t h i t K A (x)

is defined as the minus logarithm of continuous a priori probability on the binary tree, and

m a t h i t K P (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

o m e g a

such that the sum of

2^{m a t h i t K A (x) - m a t h i t K P (x)}

over all prefixes

x

of

o m e g a

is infinite. Such a sequence can be chosen among characteristic sequences of computably enumerable sets.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite