This is a very good point and very important to understand. K-complexity is measured in terms of how many bits you need to specify a Turing machine (under some encoding) that computes the function. There are therefore only four functions whose K-complexity is 2.
An important ancillary result is Chaitin's theorem, which is that beyond a certain threshold (a few hundred bits) it is not possible to know the K-complexity of a function because if you did then you could solve the halting problem. See [1] for a simple proof.
> There’s just one drawback to Kolmogorov complexity: It’s incomputable, meaning that there is no program that can calculate the complexity of every possible string. We know this because if there were such a program, we’d end up with a contradiction.
> To see this, imagine we have a program that can compute Kolmogorov complexity for any string. Let’s call the program K. Now, let’s search for the smallest string of numbers — call it S — whose Kolmogorov complexity is double the length of K. To be concrete, we could imagine that K has 1 million characters, so we’re looking for a string S whose Kolmogorov complexity is 2 million (meaning that the shortest program that outputs S has 2 million characters).
> With program K in our toolbox, calculating S is easy (though not necessarily quick): We can write a new program that we’ll call P. The program P essentially says, “Go through all strings in order, using program K to compute their Kolmogorov complexity, until you find the first one whose Kolmogorov complexity is 2 million.” We’ll need to use program K when building P, so altogether P will have slightly more than 1 million characters. But this program outputs S, and we defined S as a string whose shortest program has 2 million characters. There’s the contradiction.
