13.16Kolmogorov complexity and the dimensions of individual strings

The basic idea is to introduce a new termination symbol to mark the end of a string. A terminated binary string is σ with σ 2<ω. Let T be the collection of terminated binary strings.

Definition 13.16.1 (Lutz [254]). For s 0, an s-termgale is a function d : 2<ω T → R 0 such that d(λ) 1 and for all σ 2<ω,

d(σ) 2−s(d(σ0) + d(σ1) + d(σ )).

For s = 1, the s-termgale condition is akin to the usual supermartingale condition, but as noted by Lutz, if each of 0, 1, is equally likely, independently of previous bits, then the conditional expected capital after

definition of s-termgales is based on the assumption that the termination symbol should actually be regarded as having vanishingly small probability. In other words, the 1-termgale payo condition is the same as the corresponding supermartingale condition, except that the 1-termgale must divert some of its capital to the possibility of occurring, and this diversion is without compensation, but can occur at most once, and we can make the impact of this diversion of capital small.

Lutz [254] provided the following example. Let d(λ) = 1. Given d(σ), let

d(σ0) = 32 d(σ) and d(σ1) = d(σ ) = 14 d(σ). Then d is a 1-termgale and if σ is a string with n0 many 0’s and n1 many 1’s, then

2<ω T , then d is an s-termgale, and each s-termgale can be obtained in this way from a 0-termgale.

We need the following technical lemma.

Lemma 13.16.3 (Lutz [254]). Let d be an s-termgale and τ 2<ω. Then

σ 2<ω 2−s|σ|d(τ σ ) 2sd(τ ).

Proof. First suppose that s = 0. It is straightforward to show by induction that for all m,

Thus σ 2 m d(τ σ ) d(τ ) for all m, and hence σ 2<ω d(τ σ ) d(τ ).

664 13. Algorithmic Dimension

For the general case, let d (σ) = 2−s|σ|d(σ) for all σ 2<ω T . Then d is a 0-termgale, and hence

We are now ready to define (optimal) termgales.

s , and σ 2<ω T .

(ii) A termgale is Σ01, or constructive, if d0 is a Σ01 function.

In the same way that we connected continuous semimeasures with mar-

tingales, we can define the termgale induced by a c.e. discrete semimeasure

m via d[m]s(τ ) = 2s|σ| τ σ m(σ). (See Section 3.9 for more on discrete semimeasures.)

Theorem 13.16.5 (Lutz [254]). If m is a maximal c.e. discrete semimeasure then d[m] is an optimal Σ01 termgale. Thus there is an optimal Σ01 termgale.

Proof. It is easy to check that d[m] is a termgale. Let d = {ds : s 0} be a termgale. Let m(σ) = d0(σ ). By Lemma 13.16.3, m is a c.e. discrete semimeasure. Since m is multiplicatively optimal, for some c we have m(σ) cm(σ) for all σ 2<ω. Hence

d[m]s(σ ) = 2s|σ |m(σ) 2s|σ |cm(σ) = cds(σ ).

Definition 13.16.6 (Lutz [254]). If d is a termgale, n > 0, and σ 2<ω, then the dimension of σ relative to d at significance level n is

dimnd (σ) = inf{s 0 : ds(σ ) > n}.

We can characterize this dimension in terms of an optimal termgale.

d be a Σ01 termgale. Then for each n > 0 there is a c > 0 such that, for all

σ 2<ω,

Theorem 13.16.7 is the key to Lutz’ definition of the dimension of a string, since it says that if we base our definition on a particular optimal

on the dimension of a given string, particularly for longer strings. Therefore we fix an optimal Σ01 termgale d and make the following definition.

Definition 13.16.8 (Lutz [254]). dim(σ) = dim1d (σ) for every σ 2<ω.

In this context, we lose some of the finer points of Hausdor dimension. For example, it is no longer true that the e ective dimension is bounded above by 1. But we do have the following analog.

Theorem 13.16.9 (Lutz [254]). There is a b > 0 such that dim(σ) b for all σ 2<ω.

Proof. For each σ and s, let ds(σ) = 2(s−2)|σ| and ds(σ ) = 2(s−2)|σ|+1. Then it is easy to check that d = {ds : s 0} is a termgale, and d2(σ ) = 2 for all σ. Thus, by Theorem 13.16.7, there is a c such that dim(σ) 2 +

c| | 2 + c, so we can take b = 2 + c.

1+ σ

Finally, we have an analog of the Kolmogorov complexity characterization of e ective Hausdor dimension.

Theorem 13.16.10 (Lutz [254]). K(σ) = |σ| dim(σ) ± O(1).

Proof. Let m be a maximal c.e. semimeasure, as given in Theorem 3.9.2, and let d[m] be the termgale induced by m. For all σ 2<ω and s > 0, we have

d[m]s(σ ) > 1 iff 2s|σ |m(σ) > 1 iff s > − log m(σ) , 1 + |σ|

so (1 + |σ|) dim1d[m](σ) = − log m(σ).

Thus, by Theorem 13.16.7, (1 + |σ|) dim(σ) = − log m(σ) ± O(1), so by Theorem 13.16.9, |σ| dim(σ) = − log m(σ) ± O(1). But by the Coding Theorem 3.9.4, K(σ) = − log m(σ)±O(1), so |σ| dim(σ) = K(σ)±O(1).

Corollary 13.16.11 (Lutz [254]). For A 2ω, we have dim(A) = lim infn dim(A n) and Dim(A) = lim supn dim(A n).

In [254], Lutz also proved several other facts about the dimensions of finite strings. Space considerations preclude us from including this material.