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

  • $\begingroup$ What about "the Kolmogorov complexity of the function itself" as opposed to the Kolmogorov complexity of the thing's prefixes, initial segments, bits, etc.? $\endgroup$ – Dan Brumleve Jun 1 '17 at 3:26
  • $\begingroup$ @DanBrumleve That would be clearer, but I don't think perfectly so; I would still explicitly say what you mean. $\endgroup$ – Noah Schweber Jun 1 '17 at 3:52
  • $\begingroup$ I guess so, I wonder if there is some other standard term, or if there is some reason that my definition isn't natural. $\endgroup$ – Dan Brumleve Jun 1 '17 at 3:55
  • $\begingroup$ @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? $\endgroup$ – Noah Schweber Jun 1 '17 at 4:31
  • $\begingroup$ 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. $\endgroup$ – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.