http://johncarlosbaez.wordpress.com/2011/10/28/the-complexity-barrier/
...here’s a more interesting question: how complex can we prove
something to be?
The answer is one of the most astounding facts I know. It’s called
Chaitin’s incompleteness theorem. It says, very roughly:
There’s a number L such that we can’t prove the Kolmogorov
complexity of any specific string of bits is bigger than L.
Make sure you understand this. For any number, we can prove there
are infinitely many bit strings with Kolmogorov complexity bigger
than that. But we can’t point to any particular bit string and
prove its Kolmogorov complexity is bigger than L!
Over on Google+, Allen Knutson wrote:
That’s an incredibly disturbing theorem, like driving to the edge
of the universe and finding a wall.
I call L the complexity barrier. So one question is, how big is L?
It’s hard, or perhaps even impossible, to find the smallest L that
does the job. But we can certainly find numbers L that work. And
they’re surprisingly small!
My friend Bruce estimates that the complexity barrier is a few
kilobytes.
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
