Re:Kolmogorov Complexity - A Primer
by MathProgramming on Sunday April 22, 2012 @11:48PM
(#3877120)
In the context of Turing machines, the output is really a _binary_ string, not a string of arbitrary characters. So in a sense, those two programs are the same thing. But of course, the Kolmogorov complexity of any number n is bounded by log(n) + c.
print "000"+bin(0x748b48bd413d)[2:]
print '00011101001000101101001000101111010100000100111101'
print bin(128141569638717)[2:]
In general, any string of 1s and 0s will be compressible using this method in python once the binary number is greater than 212 (you break even at 211). However, again, I only claim this to be an upperbound ;). (also assuming that invoking built-ins isn't cheating).