News for hackers. Stuff that matters.
Re:Kolmogorov Complexity - A Primer by archgoon on Sunday April 22, 2012 @11:35PM (#3877095)
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).

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.
Re:Kolmogorov Complexity - A Primer by mmphosis on Monday April 23, 2012 @02:37AM (#3877596)
print "000"+bin(0x748b48bd413d)[2:]
Re:Kolmogorov Complexity - A Primer by archgoon on Monday April 23, 2012 @01:53PM (#3880057)
ah... good catch :)