Kolmogorov complexity of an algorithm?

188 Views Asked by At

I've read that Kolmogorov comlexity is about calculating the least number of bits needed to describe a string or other mathematical objects.

Does 'other mathematical objects' include algorithms too?

I guess the answer is yes. But the thing that concerns me is how an algorithm defined in this context? Because many algorithms do the exact same thing but do it differently. So they are not the same algorithms, also you can add a comment to an algorithm or change it in a way that the even though its text has changed the computations that happen are exactly the same. And they should be considered the same. so how is an algorithm defined in this context (if it is studied in the first place)?

1

There are 1 best solutions below

9
On BEST ANSWER

Algorithms are to be understood as Turing Machines, in the majority of contexts. But you are right: from a Turing Machine, one can always modify the transition table so that the Turing Machine we obtain is different, yet it essentially does the same thing. In this context, we say that the two Turing Machines have the same language: on any input, if one accepts the input then so does the other one and the output is the same.

But this doesn't change the definition: given an algorithm (a Turing Machine) $N$, the Kolmogorov complexity of $N$ is the smallest size of pairs $(M,w)$ where $M$ is a Turing machine and $w$ is a word in the alphabet of $M$ so that on input $w$, $M$ outputs $N$ on its tape.