New answers tagged kolmogorov-complexity
2
Consider the word $w_n$ that is the output of $M'$ given input $n$.
Note that description of $w_n$ is the description of $M'$, whose length is some constant $c$, plus the description of $n$, whose length is $O(\log n)$ since we can express $n$ in the binary representation. So $K(w_n)\le c + O(\log n)$. If $n$ is large enough, we get
$$K(w_n)\lt n = |w_n|.$$...
2
The underlying problem with the example you quote is that it's informal and completely imprecise. As you say, why don't we include the size of the "simple algorithm"? Why are we allowed to assume that it is known what "$e$" is?
Formally, Kolmogorov complexity is defined with respect to a particular encoding of Turing machines. If you fix an encoding, then ...
Top 50 recent answers are included
