Well, I guess it basically goes to show how hard it is to determine the actual kolmogorov complexity (even once specifying a particular encoding of a Turing Mac

Well, I guess it basically goes to show how hard it is to determine the actual kolmogorov complexity (even once specifying a particular encoding of a Turing Machine) of a string, but the following is a new upper bound on the complexity (in Python) of the second string. 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).