0

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}.

Arthur Lubocce
  • 1

1 Answers1

0

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.

Lost definition
  • 972
  • I understand your argument.

    But can you provide a formal mathematical proof based on the definition of Kolmogorov Complexity/

    That is what I am seeking.

     – Arthur Lubocce Apr 17 '21 at 18:14
  • Yes, I also have some block to construct this formal proof. I don't think it is simple. I think you would have to stipulate what encoding you are working. Then you would have to generate in this encoding all the Turing Machines M combined with inputs w by length order till you find a M and a w for the string 11...1 and 10...10. I guess also you would have to show some way to dismiss all the non-terminating TMs you found in this process by some argument. And this is not easy, in general it is non-computable. But I think that for such simple strings you could find some way. – Lost definition May 02 '21 at 14:48
  • Actually I think this is the general problem to work with Kolmogorov complexity. It is difficult to stipulate the value for concrete strings. But it has a good approximation. In general, the value for $C(x)$ is not computable. But for some simple string $x$, it can be computable, and I think your example could be among them, but actually i am not sure. My answer is just intuition based. Maybe you could edit your question to be more explicit about this, and you could say where did you get your complexity definition. – Lost definition May 02 '21 at 15:17
  • I am using the minimal description definition of Complexity as in Definition 6.2 of Spitzer assuming some fixed encoding for the pair M,w, <M,w>. – Arthur Lubocce May 04 '21 at 19:20