[r-t] Complexity of extents

[Richard Smith]

Richard Smith wrote:

> Alexander Holroyd wrote:
>
>> This is an interesting and ptoentially tricky area.
>> 
>> In some sense the "true" measure is Kolmogorov Complexity, but that is a a 
>> non-computable function.
>
> It's worse than non-computable.  It doesn't a defined 
> value at all (other than, perhaps, for the case of an 
> empty string).  Almost any result you might want to use 
> involves one or more unknown but finite constant.  The 
> result is that you can only sensibly talk about the 
> complexities of things as they tend to the limit of being 
> infinitely long (where you can ignore all the unknown 
> finite constants).  But that makes no sense for an extent.

This is worse than it sounds.

Kolmogorov defined the complexity of a string to be the 
minimum length of a computer program that generates the 
string (plus the length of the data used as input to the 
program, plus a hard-to-quantify factor denoting the 
complexity of the language that the program is written in).

We could encode every extent as a sequence of n! place 
notations, of which there are F(n) on n bells, where 
F(0)=F(1)=1 is the Fibonacci sequence.  The complexity of 
such an encoding is n!.lg(F(n)) + C, where lg is the 
logarithm to base 2, and C is the complexity of a program 
that interprets place notation.

An alternative encoding is to say that an extent is a 
sequence of k parts, each with n!/k place notations.  The 
complexity of that encoding is n!/k.lg(F(n)) + lg(k) + C', 
where C' is the complexity of a program that interprets 
place notation and repetition.  The difference C'-C >= 0 is 
the cost of adding support for repetition to the program 
that interprets place notation.

In the case of minimus, n = 4, k <= 4 and F(n) = 5.  Thus 
for a four-part extent (like Erin), which is where 
repetition has the biggest saving, the saving is only ~40 
bits.  If the cost of adding repetition, C'-C, is greater 
than that, then it's a false economy, and, so far as the 
Kolmogorov complexity is concerned, the repetition is 
irrelevant.

Because we cannot quantify C' and C, we don't know whether 
the repetition is relevant.  In the limit of extents on 
large numbers of bells, it clearly is (because C and C' are 
finite constants, not dependent on n).  But in the sort of 
cases we're most likely interested in, we don't know.

We cannot even know whether there is any difference in the 
Kolmogorov complexities of extents on a specific number 
bells, or whether they are all equally complex.

RAS