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