Fundamental Compressionist Philosophy.

[Brendan Macmillan]

> > Perhaps a good image is to take the terrain of your caving story, and cut
> > it up into cross-sections of a square foot each (as a practical
> > approximation of a mathematical "point"), and then jumble them all up, so
> > that there is "no relationship between the heights of adjacent points".
> > Now, to find the heighest point now require exhaustive search, as knowing
> > the height of one point tells us nothing about the height of an adjacent
> > point.  We truly are lost.

> Perhaps we can start a collection of these kinds of problems. Here is a
> possible example: we know that the decimal expansion of pi is not random
> because it can be generated by a relatively simple formula. But to most
> people, the sequence of digits looks completely random. If someone were
> given a section of the sequence, (particularly if it were a section
> relatively far from the beginning) and asked to find a simple formula that
> would generate the section, my guess is that most people, including
> professional mathematicians, would find it impossibly difficult.
> 
> Would this be a possible example?
Yes - although, there is a possible confusion of levels here.  On the one
hand is the sequence itself, and its (apparent) disorder.  This looks similar
to the search space I gave as an example, of being all jumbled up (of course,
your example is loaded, because there actually is an order to it).

On the other hand, is the search conducted by the possible mathematicians,
which has another search space altogether, which you have not explicitly
mentioned.

Perhaps this space also has a nice hidden "order" to it, and all we need do is
find it.  That is, perhaps we can cleverly discover a heuisitic, that reveals
the shape of the search space, so that it becomes easy to search.
Or perhaps not - why should it be conveniently ordered for us?  Your example
seems loaded to me, in that it only *seems* random.  Why should this be true
of search spaces?  But even if there is a very clever pattern to the search
space, that God put there for us (or perhaps hid there for himself)...

...there is the killer point - even if there is a nice pattern to this
search space, perhaps it is just as difficult to discern as the one in the
original problem (of the sequence of digits forming pi), and this search
space is only application to that particular problem...

...of course, if we did find a general pattern, universal to all search spaces,
then *we* would be gods... every problem would crumble trivially before us...
speaking as a programmer, dealing with incredibly simple and contained
problems in comparison with this one: I don't think it's gonna happen ;-)


> So if you move around amongst a jumble of points at different heights and
> accidentally stumble on a relatively high one, you may decide that that is
> "good enough". There does not seem to be much other option.
Yes.  And in an infinitely large search space, sparsely populated with
"relatively high ones", this search will take a loong time.

On the other hand, if we study the search space for long enough, we may find
a nice pattern to it, that enables us to search it efficiently.  For example,
a way of presenting the space that reveals a hilliness.  The fact that we can
do this at all bodes well for us.



Incidentally, anyone reading all these posts about searching might wonder what
it has to do with compression.  Well, I think that compression has actually
solved the problem of recognizing good ideas when you have them - automatically.
This is a sensational leap forward in creating a thinking machine.  However,
it turns out that the previous step, of "having good ideas" is not so easy -
this is the search problem, and the reason why this discussion is relevant.

Caitin has published on this in the context of mathematics - he suggests that
the search space of mathematical thereoms is random, and what we have is stuff
that we just happened to discover.  (Please correct me if I've got this wrong
in some way).

The most interesting point, as I keep iterating, are that 
 (1). we human being seem to be pretty good at it - especially when bouncing
ideas off each other, and trully absorbing each other's perspectives; and
 (2). we are actually not so good as we think, as we don't even see much of
the search space.  It's hard to see things for which we have conceived no
concepts.

Thus, there are lots of sensational ideas just lying all over the place, that
few people are looking for, and by working together - bouncing ideas - we can
be the first to discover them, and really make a difference.


Cheers,
Brendan
-- 
e:  bren at csse.monash.edu.au                         v:  +61 (3)  9905 1502
Email is checked daily                              Phone is rarely attended