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

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?

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).

• What about "the Kolmogorov complexity of the function itself" as opposed to the Kolmogorov complexity of the thing's prefixes, initial segments, bits, etc.? – Dan Brumleve Jun 1 '17 at 3:26
• @DanBrumleve That would be clearer, but I don't think perfectly so; I would still explicitly say what you mean. – Noah Schweber Jun 1 '17 at 3:52
• I guess so, I wonder if there is some other standard term, or if there is some reason that my definition isn't natural. – Dan Brumleve Jun 1 '17 at 3:55
• @DanBrumleve I think it might not be as natural as it seems, at least for a lot of the usual things we use KC for. The question of whether one computable real has lower KC (in your sense) than another is not stable under change-of-universal-machine, so it's not clear what property this actually reflects. Now of course that's true for finite strings too; but there, we're usually asking asymptotic questions, or looking at longer and longer prefixes of a fixed real, and so the constant error gets swept away. So I think it's hard to see what this KC is capturing here. Do you have an application? – Noah Schweber Jun 1 '17 at 4:31
• Right, suppose we have two infinite sequences of binary strings, and that for any desired compression factor $c$ there is an offset such that the KC of the element of the first sequence at that offset is $c$ less than the KC of the corresponding element of the second sequence. That's stable under change-of-universal-machine. Likewise using my definition and sequences of computable reals. – Dan Brumleve Jun 1 '17 at 4:38

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).