Thomas Sepulchre comments on K-complexity is silly; use cross-entropy instead

[Thomas Sepulchre]

I think that, if you use the base 2, the alt-complexity might be ill-defined

Assume that, for your function $f$, there is some program $p$, such that it computes $f$, and you can add any string after $p$ without changing the fact that it computes $f$. For example, you could think that $p$ finishes with some stopping sequence, such that anything after will be ignored

Then, assuming $N$ is the length of $p$, there are at least one program of length $N$, 2 programs of length $N+1$, and, in general $2^k$ programs of length $N+k$ computing f. Thus, the sum diverges

Unless I made a mistake, this hints that the choice of base is not neutral, and any choice below 2 (including 2) makes the definition ill-posed

[So8res]

You’re over-counting programs. I didn’t spell out definitions of “programming language” and “length”, but an important disideratum is that there has to only be finitely much “length” to go around, in the sense that ${\sum }_{p\in P}rexp\left(length\right(p\left)\right)$ must converge.

Under your proposal, the total amount of “length” is ${\sum }_{n=1}^{\infty }{2}^n\cdot 2^{-n}={\sum }_{n=1}^{\infty }1=\infty$, so this is not an admissible notion of length.

(Note: this argument has nothing to do with the choice of base 2, and it applies equally well for all bases.)

Two common ways of repairing your notion of length are:

1. Using a prefix-free code for programs, such that if $p$ is a program then it is not the prefix of any other program.

2. Thinking of programs as infinite bitstrings (which you might intuitively factor into a finite prefix describing a probabilistic program, and an infinite suffix serving as the random seed).

In the former case, when $001$ is a valid code for a program $p$, then any extension to that code (like $0010$ or $0011$) is not valid, and so a total of $2^{-3}$ length is allocated to $p$ and no other length is allocated to any program that starts with $001$, and it’s not too hard to see that a total of 1 length is allocated overall.

In the latter case, we don’t count $001$ as separate from $\mathrm{0010...}$ and $\mathrm{0011...}$; we only count the infinite programs, and observe that a total of $2^{-3}$ length is allocated to the collection of all programs that start with $001$, and that $1$ length is allocated overall.

You ran into trouble because you were trying to count both the prefixes like $001$ and all their continuations, which is overcounting :-).

[Thomas Sepulchre]

Thanks!