Terminology for the Kolmogorov complexity of computable functions, sets, reals?

204 Views Asked by At

The Kolmogorov complexity of a binary string can be defined in terms of a prefix-free binary encoding of Turing machines that operate on a binary tape. Then if $x$ is a binary string, $K(x)$ is the length of the shortest encoding of any Turing machine that halts with $x$ on the tape when given an initially empty tape.

It's possible to use the same setup to describe the shortest Turing machine encoding corresponding to a computable function. We need one extra parameter it seems: a binary prefix-free encoding of the natural numbers. Given that, it's possible to define the length of the shortest Turing machine encoding corresponding to any particular computable function $\mathbb{N} \rightarrow \{0,1\}^*$ (or by decoding with the same function, $\mathbb{N} \rightarrow \mathbb{N}$). Or with the convention that membership is equivalent to an empty output tape, we can talk about the length of the shortest Turing machine encoding corresponding to a computable set of natural numbers (or the bits of a computable real). It doesn't really matter what natural number encoding we choose, as long as it is computable, since the result is still defined up to an additive constant.

Can I just call this the Kolmogorov complexity of a function, or of a set, or of a real, and be understood?

2

There are 2 best solutions below

7
On

This isn't really my field, but the following is my impression:

I believe that the phrase "Kolmogorov complexity of $f$" for $f$ a function/set/real, computable or not, would frequently be understood as referring to the function taking $n$ to the Kolmogorov complexity of the length-$n$ prefix of $f$; or even, that function up to an additive constant (so in particular, ruining the distinction between computable $f$s). Papers using the term "Kolmogorov complexity of a real" or similar seem to be referring to this almost uniformly, see e.g. http://www.sciencedirect.com/science/article/pii/S0304397501001025. Of course, that paper never says "the Kolmogorov complexity of $\alpha$ is," but the title - "The Kolmogorov complexity of a real number" - does use that language.

To further muddy the waters, there is a notion of Kolmogorov complexity of a real in the setting of BSS machines, introduced by this paper.

Given all this, I think using the phrase without explanation might create confusion (although it does make perfect sense). I would say explicitly what you mean by the Kolmogorov complexity of a computable function/set/real; given how the term seems to be used elsewhere, I might also call it something else (the phrase "index complexity" seems nicely self-explanatory to me).

0
On

Apparently it is possible to use the same set up as in regular definition of Kolmogorov complexity of a finite binary string for the definition of Kolmogorov complexity of a function.

The Kolmogorov complexity of an integer valued function f is the length of the shortest program to the turing machine that computes f. For more detail, you can look at the Shannon Information and Kolmogorov Complexity (section 2.2.3).