Is the Kolmogorov Complexity of 11…1 with even length L less than for the string 1010…10 of the same length?

54 Views Asked by At

We define the Kolmogorov Complexity to be independent of any

particular programming language for bit string x as the length of the shortest

string <M,w> where TM M on input w halts with x on its tape

and <M,w> is some specified fixed encoding of the pair {M,w}.

1

There are 1 best solutions below

4
On

Yes, generally $C(111...1) \leq C(1010...10)$. You can see why it couldn't be more noting that you can apropriatly change a program $M$ or a input $w$ for $10...10$ making substitutions of zeros for ones (intuition: repeat "01" k times-> repeat "11" k times). This don't change the size of neither $M$ nor $w$. And eventually it will be less, for in general programs for the first are simpler then programs for the second.