Effective dimension is the liminf prefix-complexity rate

Let an effective $s$-gale $d$ succeed on $X$, and fix a rational $t>s$. For $n\ge 1$ enumerate $E_n=\{\sigma \in 2^n:d(\sigma )>1\}$, possible because $d$ is lower semicomputable. Iterating the gale identity gives ${\sum }_{\mathrm{\mid }\sigma \mathrm{\mid }=n}d(\sigma )=2^{sn}d(\mathrm{\varnothing })$, so $\mathrm{\mid }{E}_n\mathrm{\mid }<2^{sn}d(\mathrm{\varnothing })$. Choose an integer $c$ such that $\mathrm{\mid }{E}_n\mathrm{\mid }<2^{\lceil tn\rceil +c}$ for every $n$. Such a fixed $c$ exists since $t>s$ and $d(\mathrm{\varnothing })$ is finite (Effective Hausdorff dimension).

For the reverse inequality write $a={\mathrm{lim\hspace{0.17em}inf}}_{n}K(X\upharpoonright n)\mathrm{/}n$, which is finite since a self-delimiting code for $n$ followed by $n$ bits gives $K(X\upharpoonright n)\le n+O(\log n)$. Independently choose rationals $q,t$ with $a<q<t$. Let $U$ be the fixed optimal prefix-free machine. For each halted program $p$ with output $\sigma$, put mass $2^{-\mathrm{\mid }p\mathrm{\mid }}$ uniformly on the cylinder $[\sigma ]$: its value on a cylinder $[\tau ]$ is $2^{-\mathrm{\mid }p\mathrm{\mid }}$ if $\tau ⪯\sigma$, $2^{-\mathrm{\mid }p\mathrm{\mid }-\mathrm{\mid }\tau \mathrm{\mid }+\mathrm{\mid }\sigma \mathrm{\mid }}$ if $\sigma \prec \tau$, and $0$ if $\tau$ and $\sigma$ are incompatible. Denote the sum of these values over all halted $p$ by $\mu ([\tau ])$. Kraft's inequality (Kraft inequality and effective prefix-code allocation) gives $\mu ([\mathrm{\varnothing }])\le 1$; each summand is nonnegative and obeys ${\mu }_p([\tau ])={\mu }_p([\tau 0])+{\mu }_p([\tau 1])$, so the sum has the same identity.

Give $n$ a computable self-delimiting code of length $O(\log n)$, followed by a fixed-length $\lceil tn\rceil +c$-bit index into the enumeration of $E_n$. These codes form a prefix-free machine: the first code identifies $n$, and all following indices then have the same length. Its output on an index is the corresponding enumerated string when that index appears. Thus, by optimality of $K$ (Invariance theorem for prefix complexity), each $\sigma \in E_n$ has $K(\sigma )\le tn+O(\log n)$. Success of $d$ makes $d(X\upharpoonright n)>1$ at infinitely many, hence unboundedly many, lengths $n$. It follows that ${\mathrm{lim\hspace{0.17em}inf}}_{n}K(X\upharpoonright n)\mathrm{/}n\le t$. Since rational $t>s$ was arbitrary, the liminf is at most $s$, and therefore at most $\dim (X)$.

Set $d_t(\tau )=2^{t\mathrm{\mid }\tau \mathrm{\mid }}\mu ([\tau ])$. Because $t$ is rational and the halted computations can be enumerated, $d_t$ is lower semicomputable; the preceding identity makes it an effective $t$-gale (Effective Hausdorff dimension). At any $\sigma$ with a shortest program $p$, its contribution alone gives $d_t(\sigma )\ge 2^{t\mathrm{\mid }\sigma \mathrm{\mid }-K(\sigma )}$ (Prefix-free machines and prefix complexity). There are infinitely many lengths $n$ with $K(X\upharpoonright n)<qn$ by the definition of the liminf. On them $d_t(X\upharpoonright n)>2^{(t-q)n}$, which tends to infinity. Thus $d_t$ succeeds and $\dim (X)\le t$. Letting rational $t$ decrease to $a$ completes the equality.