Kolmogorov复杂性，与方程斗争

Question

我正在努力了解kolmogorov复杂性。我一直在努力挣扎，这是一段时间的一段时间，并将欣赏任何投入。

显示存在常量 $ c $ ，使得对于每个 $ n \ in \ mathbb {n} - \ {0 \}，$$ {k（（01）^ 2} ^ n）\ leq \ lceil \ log_2（n + 1）\ rceil + c=lceil \ log_2（\ log_2（\ frac {| {（01）^ 2} ^ n |} {2}））\ rceil + c $

通过实验，我得出结论， $ | {（01）^ 2} ^ n |= 2 \ cdot2 ^ n \ incliS \ log_2（| {（01）^ 2} ^ n |）= n + 1 $ 。为什么简单地将其替换在上面的等式中是错误的：

$ {k（（01）^ 2} ^ n）\ leq \ lceil \ log_2（n + 1）\ rceil + c=lceil \ log_2（\ log_2（| {（01）^ 2} ^ n |））\ rceil + c $

为什么字符串的长度在问题陈述中除以2？

Answer 1

该语句相当于 \ begin {senugen} n + 1=log_2 \ left（\ frac {|（01）^ {2 ^ n} |} 2 \右）＆\ incliedby |（01）^ {2 ^ n} |= 2 ^ {n + 2}。\结束{align} 如果 $（01）^ {2 ^ n} $ 表示 $ \ underbrace {（01）（01）（01）\ Cdots（01）} _ {2 ^ n \，\文本{次$ 然后该语句不正确，如 $ |（01）^ {2 ^ n} |= 2 ^ {n + 1} $ 已正确获得。