[CST-2] Kolmogorov complexity - cost of sorting

[Timothy Hospedales]

Sounds sensible. But how do you actually use the lack of information
it the sorted sequence to compress it to zero size? It doesnt seem
like you can because you still have to know what particular numbers
the sorted numbers were in order to put them back into their original
unordered form. Which you cant do from zero size by the counting
argument.

Tim


> It contains less information as it has fewer degrees of freedom?
> 
> i.e. it's confined to be monotonically increasing/decreasing  across it's
> length.
> 
> log_2{n!} is the information content of a random sequence of length n
> (it has n! possible orderings, so can communicate log_s{n!} bits of
> information), the sorted version has 1 possible ordering, so conveys 0
> bits)
> 
> 
> -- 
> David Singleton    _________________      St John's College, Cambridge
>  C5 3rd Crt        +44(0)7980 641608   http://www.davidsingleton.co.uk/
> !!my @cam.ac.uk address stops mid-June - use davidsingleton@cantab.net!!
> 
> 
> 
> _______________________________________________
> CST-2 mailing list
> CST-2@srcf.ucam.org
> http://www.srcf.ucam.org/mailman/listinfo/cst-2