There are many ways to define the Kolmogorov-Complexity, and usually, all these

Question

There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if K1 and K2 are kolmogorov complexity functions (defined via different languages or models), then there exists a constant c such that for every string x, |K1(x)?K2(x)|<c. I believe this is because for every Kolmogorov complexity function K and for every x it holds that K(x)?|x|+c, for some constant c.

I'm interested in the following definitions for K, based on Turing-machines

number of states: Define K1(x) to be the minimal number q such that a TM with q states outputs x on the empty string.
Length of Program: Define K2(x) to be the shortest "program" that outputs x. Namely, fix a way to encode TMs into binary strings; for a machine M denote its (binary) encoding as ?M?. K2(x)=min|?M?| where the minimum is over all M's that output x on empty input.

Are K1 and K2 equivalent? What is the relation between them, and which one grasps better the concept of Kolmogorov complexity, if they are not equivalent.

What especially bugs me is the rate K2 increase with x, which seems not to be super-linear (or at least linear with constant C>1 such that K2<C|x|, rather than |x|+c). Consider the most simple TM that outputs x - the one that just encodes x as part of its states and transitions function. it is immediate to see that K1(x)?|x|+1. However the encoding of the same machine is much larger, and the trivial bound I get is K2(x)?|x|log|x|.

Explanation / Answer

I apologize in advance for that I give way too many details, but I'm about to contradict people.
About K(x)?K?(x)+c

The fact that K1(x)?K2(x)+c usually comes from an interpreter of the description language #2 into the description language #1 and not from a translation from programs of #2 into programs of #1.

For example KC(x)?KPython(x)+cpy2c and you get this inequality as simply as this:

void py_run(char * s) {
// code of your Python interpreter
}

int main(void) {
py_run("Put here your Python program of size Kpython(x)");
}

Then your constant cpy2c will be something like 528+490240688 where 528 is the number of bits for this code and 490240688 bits is the size the official Python interpreter written in C. Of course you only need to interpret what is possible in your description language for Python so you can do better than 69 MB :-)

What is important is that you can write your Python program linearly in your C code. For example, a language where you need to put "BANANA" between every character is not a very good description program and the property is then false. (But if the description language authorizes you to write data in a separate file or in a block, this problem disappear)
Why your K1(x)=q is flawed

The problem with your definition of K1 is that you may need more than q bits to describe a Turing machine with q states because you need to encode transitions.

So no K1 and K2 are probably not equivalent, but that's mainly K1's fault. I think that we can prove that for all a>0 there is a ca such that K1(x)?a|x|+ca. Of course any a<1 is enough to disprove the fact that K1 is not a valid function, since it would mean that we can encode more all 2n possible strings of length n into an+ca bits.

But the size is an incredibly tight bound when building Turing machines. The idea is that in a block of b states there are b2b ways to find transitions for each state and that's better than the usual 2b ways you can fill b bits. Then you can store in each block log2b bits of information. (not 2log2b because you have to go in and out the block one way or another)

So yeah... With blocks of size 21/a you could probably prove K1(x)?a|x|+ca. But I already written way too much about why the number of states is not a valid Kolmogorov complexity function. If you want me to elaborate, I will.
Now about K2

The naive descriptive language corresponds roughly to K2(x)=q?2?(log2q+2) (i.e. log2q for each next state and details about write and termination).

As you seem to be, I'm convinced that a better/cheater way would be to authorize to encode "data" into Turing machine, maybe by adding a binary tag in the description language that says whether if a state is a data state (that just writes a bit and go to the next state) or if it does something else. That way you could store one bit of your x in one bit of your descriptive language.

However if you keep the same K2 you could use the same technique I used in the previous part to save a few bits, but I seem to be stuck at K2(x)?a|x|log|x|+c (for any a>0) .. maybe less than log|x|, even, but obtaining O(|x|) seems hard. (And I expect it should be |x|, not even O(|x|).)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.