Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help with Kolmogorov Complexity proof

  1. Apr 29, 2015 #1
    Hey, has anyone here done Kolmogorov complexity? I hadn't, and I was just reading the Wikipedia page to start learning it. The core concept makes sense: The Kolmogorov complexity for a a string s, K(s) is equivalent to the length of a program that generates that string (It can be any math object, not just strings.) So a string that's long but with a simple pattern behind it will have a short program and small K, where a random string will have larger K.

    Then I got to this proof, which claims to show the incomputability of K. Its a proof by contradiction, here given in pseudo Python, and available on the Wikipedia page in pseudo Pascal.
    Code (Python):

    function GenerateComplexString():
         for i in range(infinity):
             for each string s of length exactly i:
                if KolmogorovComplexity(s) >= 8000000000
                    return s
    This code enumerates through the set of all strings as s, until it finds the first one with K(s) > than some high number (in this case 8000000000) and outputs it. Since this program is shorter than 8000000000, its a contradiction, and they used it to say that K(s), (here written as KolmogorovComplexity(s)) must not be computable.

    The problem is, using a similar dirty trick, I can construct a KolmogorovComplexity function that clearly is computable. The idea behind it is to generate and run all possible programs and return the first one that produces the string. It looks like this:
    Code (Python):

    function Execute(code, s):
        string output = run(code)
        if output = s:
          addToPotentialAnswers(len(code), code)

    function KolmogorovComplexity(s):
         for i in range(infinity):
             LaunchOnNewVirtualProcessor(Execute, (ConvertToBinary(i), s))
    The LaunchOnNewVirtualProcessor runs Execute on a "virtual processor", and exploits the fact that any Turing machine can simulate any other number of Turing machines, so if the given code doesn't halt, it slows it down but the whole process keeps going. (Its not assumed all every number representing a program generates a number or halts) So long as the strings are finite, as they are in their function, and the programs that output strings halt (which is totally reasonable), than this works, and everything becomes incredibly confusing.

    So what am I getting wrong, there's got to be something, because their proof seems totally sound, the more I go over it in my mind.

    edit: Changed my code, can't assume that the process which ends first has the shortest code.
    Last edited: Apr 29, 2015
  2. jcsd
  3. Apr 29, 2015 #2
    Okay, I think I might see it now. My program generates a list of potential answers, but you can never quite say when the its done, when the potential answer is the best answer. So though my program will generate at some point the answer, you can never quite say when that is. That must be it.

    Edit: Yeah, that's totally it. I see it now. Mods can delete if they want. My error was in thinking there was some sufficiently huge amount of time within which a program with the right answer would halt, but not true. The best program might be some small thing that simulates the entire universe to find the best answer. A really interesting illustration of how deep the Halting problem is.
    Last edited: Apr 29, 2015
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook