# [r-t] Complexity of extents

Richard Smith richard at ex-parrot.com
Wed Jun 19 02:02:29 UTC 2013

```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

```