solipsist comments on Does Kolmogorov complexity imply a bound on self-improving AI? - Less Wrong

4 Post author: contravariant 14 February 2016 08:38AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (14)

You are viewing a single comment's thread.

Comment author: solipsist 18 February 2016 03:06:42PM *  0 points [-]

What what sorts of output strings are you missing?

Calculating Kolmogorov complexities is hard because because it is hard differentiate between programs that run a long time and halt and programs that run a long time and never halt.

If God gave you a 1.01 MB text file and told you "This program computes BB(1000000)", then you could easily write a program to find the Kolmogorov complexity of any string less then 1 MB.

kolmogorov_map = defaultdict(lambda x : infinity)
for all strings *p* less than 1000000:
    run *p* for at most BB(1000000) steps
    save output to *o*
    if (*p* halted and kolmogorov_map[*o*] > len(p):
        kolmogorov_map[*o*] = len(p) # found smaller program
    else:
        # *p* does not ever ever halt and has no output

Replace BB(1000000) with a smaller number, say A(Graham's number, Graham's number), and this calculator works for all programs which halt in less than A(Graham's number, Graham's number) steps. That includes pretty much every program I care about! For instance, it includes every program which could run under known physics in the age of the universe.