the complexity barrier

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