19
$\begingroup$

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 $K_1$ and $K_2$ are kolmogorov complexity functions (defined via different languages or models), then there exists a constant $c$ such that for every string $x$, $|K_1(x) - K_2(x)| < c$. I believe this is because for every Kolmogorov complexity function $K$ and for every $x$ it holds that $K(x) \le |x| +c$, for some constant $c$.

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

  1. number of states: Define $K_1(x)$ to be the minimal number $q$ such that a TM with $q$ states outputs $x$ on the empty string.
  2. Length of Program: Define $K_2(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 $\langle M \rangle$. $K_2(x) = \min |\langle M \rangle|$ where the minimum is over all $M$'s that output $x$ on empty input.

Are $K_1$ and $K_2$ 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 $K_2$ increase with $x$, which seems not to be super-linear (or at least linear with constant $C>1$ such that $K_2 < 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 $K_1(x) \le |x|+1$. However the encoding of the same machine is much larger, and the trivial bound I get is $K_2(x) \le |x|\log |x|$.

$\endgroup$
  • $\begingroup$ There are more than $2^{n^2}$ machines with $n$ states, and their average size is at least $n^2$, therefore it is unlikely that these only differ by a additive constant. $\endgroup$ – Kaveh Mar 9 '12 at 3:17
  • 1
    $\begingroup$ There is a well known bound that $K_2(x) \leq c + 2|x|$ for some fixed $c$ not depending on $x$. This is because we can encode $x$ into a prefix-free language by just doubling each bit of $x$ and then ending with $01$. This takes $2|x| + 2$ bits to represent $x$. Thus, because $K_2$ is defined in terms of a universal prefix-free machine, $K_2(x) \leq 2|x| + 2 + c'$ for some fixed $c$. This can be improved some by using a more intelligent way to encode $x$ into a prefix free language. $\endgroup$ – Carl Mummert Mar 9 '12 at 3:48
  • $\begingroup$ I can't see how. It seems that either $x$ is given as part of the encoding (as raw data), or you must construct $x$ by your state-machine. The first option seems to be cheating and I don't see how it can be comparable to the second option (which implies $K_1$) $\endgroup$ – Ran G. Mar 13 '12 at 6:35
  • $\begingroup$ @Ran G.: The key point is the invariance theorem described at en.wikipedia.org/wiki/Invariance_theorem . If I can describe any effective system that has a growth rate of $2|x|$ then a universal Turing machine (as you describe for $K_2$) will meet this within an additive constant. The universal machine is the one that takes $\langle M\rangle$ are input and returns the output of $M$ if $M$ halts. $\endgroup$ – Carl Mummert Mar 15 '12 at 1:17
6
$\begingroup$

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 $K_1(x)≤K_2(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 $K_\mathtt{C}(x)≤K_\mathtt{Python}(x)+c_\mathtt{py2c}$ 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 $c_\mathtt{py2c}$ 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 $K_1(x)=q$ is flawed

The problem with your definition of $K_1$ 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 $K_1$ and $K_2$ are probably not equivalent, but that's mainly $K_1$'s fault. I think that we can prove that for all $a>0$ there is a $c_a$ such that $K_1(x)≤a|x|+c_a$. Of course any $a<1$ is enough to disprove the fact that $K_1$ is not a valid function, since it would mean that we can encode more all $2^n$ possible strings of length $n$ into $an+c_a$ 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 $b^{2b}$ ways to find transitions for each state and that's better than the usual $2^b$ ways you can fill $b$ bits. Then you can store in each block $\log_2 b$ bits of information. (not $2\log_2 b$ because you have to go in and out the block one way or another)

So yeah... With blocks of size $2^{1/a}$ you could probably prove $K_1(x)≤a|x|+c_a$. 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 $K_2$

The naive descriptive language corresponds roughly to $K_2(x)=q\cdot 2 \cdot (\log_2 q + 2)$ (i.e. $\log_2q$ 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 $K_2$ you could use the same technique I used in the previous part to save a few bits, but I seem to be stuck at $K_2(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|)$.)

$\endgroup$
  • $\begingroup$ do you claim that $K_1$ is not a kolmogorov-complexity function? This is very surprising to me, since $K_1$ is actually the definition used in some intoduction to computability course I've once taken (not that it says anything about its correctness). $\endgroup$ – Ran G. Mar 15 '12 at 3:42
  • $\begingroup$ Well the fact that $K_1(x)≤\frac12|x|+c$ is quite disturbing. Consider this: there are $2^n$ possible words of $n$ bits and you could encode them using a $\frac12n+c$ bits? That would imply $2^n=O(2^{\frac12n})$ (you encoding has to be injective) $\endgroup$ – jmad Mar 15 '12 at 8:20
  • $\begingroup$ What if the python program has characters reserved by C? $\endgroup$ – PyRulez Dec 10 '18 at 2:48

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.