Re: Similarity of Structure

From: Matt Mahoney (matmahoney@yahoo.com)
Date: Wed Mar 19 2008 - 13:47:19 MDT


--- Lee Corbin <lcorbin@rawbw.com> wrote:

> Matt writes
>
>
> > [Lee had written]
> >
> >> Suppose that by some *obvious* [1] isomorphism,
> >> today Lee is one bit string
> >> 11011011001110010110111111001010110100000011...
> >> and tomorrow I am
> >> 11011011001110010110011111001010110100000010...
> >> where two 0's happen to be changed to 1's. By all measures
> >> of similarity, those two strings are still very similar. (It would be
> >> easy to mention some particular measures used by mathematicians,
> >> but the ones I'm completely familiar with without having to go look
> >> them up aren't very applicable here.)
> >
> > Perhaps I am missing the point of this discussion, but the standard way to
> > measure the difference between two strings x and y is K(x|y) + K(y|x)
> where
> > K(x|y) is the length of the shortest program that inputs y and outputs x.
>
> Thanks Matt! Hopefully if I had gone and tried to look up that
> stuff, I would have encountered that vastly more compact and
> simpler notion of similarity between strings.
>
> What do you think of pushing that idea for 2D patterns on a Life Board?
> (Easy, I would suppose.) What about for two grains of salt? Think that
> it can consistently and advisably be stated also in terms of Komolgorov
> complexity? What about large 3D or 4D objects in general?

You just need to code these things as strings (or code their relevant
features) and apply the same rule.

-- Matt Mahoney, matmahoney@yahoo.com



This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:02 MDT