3

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?

Dan Brumleve
  • 17,796

2 Answers2

2

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

Noah Schweber
  • 245,398
  • 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 01 '17 at 03:26
  • @DanBrumleve That would be clearer, but I don't think perfectly so; I would still explicitly say what you mean. – Noah Schweber Jun 01 '17 at 03: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 01 '17 at 03: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 01 '17 at 04: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 01 '17 at 04:38
  • I have another intended use for this terminology, relating to complexity classes. Suppose there is a particular program such that there is a proof that it runs in polynomial time and there is a proof that it solves SUBSET-SUM (note this is stronger than the statement that there is a proof that $P=NP$). Then, because the programs that give a wrong answer for SUBSET-SUM for any input are computably enumerable, there is a short program for which a proof exists that it always halts in polynomial time and solves SUBSET-SUM except for a finite number of inputs where it gives the wrong answer... – Dan Brumleve Jun 01 '17 at 04:54
  • and I think it would better to refer to "the Kolmogorov complexity of SUBSET-SUM" rather than make up an upper bound for it like a million bits and claim I can write a program to decide it shorter than that in any reasonable language. And similarly for this it would be useful to talk about the time-bounded version of KC as well. You and I talked about a related idea a couple years ago in the comments here: https://math.stackexchange.com/a/1593122/1284 – Dan Brumleve Jun 01 '17 at 05:05
1

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

consumer
  • 125