From: rpwl@lightlink.com
Date: Sat Oct 08 2005 - 19:35:30 MDT
Ben Goertzel wrote:
> Hi,
>
> I remember there was some discussion on this list a while back regarding
> complex-systems concepts like "emergence" and their utility (or otherwise)
> for understanding AI and the world in general.
>
> Well, I stupidly left the lights on in my car yesterday (while it was parked
> for a few hours) and wound up sitting for 90 minutes waiting for AAA to come
> give me a jumpstart. In the meantime I sketched out (literally) on the back
> of an envelope what seems to be an elegant definition of "emergence" in
> terms of basic computational concepts.
>
> The p.s. to this email presents this definition. It's math-y so
> non-math-happy readers should just ignore it!
>
> The main point is to show that the notion of emergence can be formulated in
> a precise and elegant way. I have made efforts in this direction in some of
> my prior writings but I think this one is a little nicer.
>
> The basic intuitive notion pursued is that emergence occurs when one has a
> situation so that:
>
> · f is a pattern in the combination of x and y
> · There is no g similar to f so that g is a pattern in x or g is a pattern
> in y
>
> I just introduce what seems to be the minimal math formalism (or close to
> it) needed to make the above two sentences precise.
>
> The next step would be to try to do some real math modeling and see if the
> intuitive examples of emergence observed in complex systems can be easily
> cast into this kind of formal perspective
>
> -- Ben G
>
> ******
>
> P.S.
>
> OK, here goes...
>
> Suppose we have a set E of entities with an operation + defined on it. (For
> instance, E might be the set of subsets of some other set of elementary
> entities; or it might be the set of multisets formed from some other set of
> elementary entities.)
>
> The + operator may be assumed commutative and associative. Examples of
> suitable + operators would be operations of set or multiset union.
>
> Consider also a set F of function mapping E into E. Elements of E may be
> mapped into elements of F via considering them as “constant functions.”
> Define an operation * on F as function composition. Of course, * is neither
> commutative nor associative.
>
> The operation + may be extended from E onto F in an obvious way, so that we
> may now think about {+,*} as algebraic operations on F.
Wait! You can extend + from E into F only if there is a unique x in E that
is associated with each f in F. To do this you need to map elements of F
into elements of E ... and the mapping has to be injective if you want to
extend + as you suggest.
But in the previous paragraph you talked about mapping in the opposite
direction, from E to F, and that would not, in general, buy you an
injective mapping.
I think you must have meant something a lot more specific (a restricted
notion of what is supposed to be in F). Could you clarify what you mean by
"constant functions" and what F is (surely it cannot be the set of ALL
possible functions from E to E?), and how this allows you to extend + to F?
Many thanks.
Richard Loosemore
> Distributivity may be assumed with regard to function application, i.e.
>
> (f+g)(x) = f(x) + g(x)
>
> Within F, we may assume there is a zero element (the constant function
> mapping everything to zero) so that
>
> x+0=0+x=x
>
> 0*f = 0
>
> and a 1 element (the identity function) so that
>
> 1*f = f*1 = f
>
> Finally, let us assume there is a valuation measure H on E, meaning that for
> any x in E, H(x) is defined as some nonnegative real number. Also assume a
> two-component valuation measure H(x,y) so that H(x,0) = H(x).
>
> Intuitively, H(x) is to be thought of as the complexity of producing x, and
> H(x,y) is to be thought of as the complexity of producing x given y as
> input. This interpretation makes it plausible to assume that
>
> H(f*g) <= H(f) + H(g,f)
>
> We may now define the notion of pattern as follows:
>
> f is a pattern in x iff:
> f(0) = x and H(f) < H(x)
>
> That is, f is a pattern in x if f produces x and yet f is simpler than x.
>
> As a consequence, it follows that
>
> f*g is a pattern in x if:
> (f*g)(0) = x and H(f)+H(g,f) < H(x)
>
> (note that this is if, not iff).
>
> We may define a distance measure between elements of F as follows:
>
> D(f,g) = (H(f,g) + H(g,f))/2
>
> If H(f,g) is interpreted as the complexity of producing f from g as an
> input, then this is a metric (a mathematically valid measure of distance)
> since
>
> H(f,g) <= H(f,w) + H(w,g)
>
> from which it follows that D also obeys the triangle inequality. We may
> produce a similarity measure from this by normalizing D to [0,1] via
>
> D1(f,g) = D(f,g) / [1+D(f,g)]
>
> and then setting
>
> sim(f,g) = 1 – D1(f,g)
>
> Now, what about emergence? Emergence occurs when we have a pattern in a
> combination of two things, that does not occur in either of the two things
> individually. That is, it occurs when one has a situation so that:
>
> · f is a pattern in x + y
> · There is no g similar to f so that g is a pattern in x or g is a pattern
> in y
>
> Thus we see that a natural notion of emergence arises from simple notions of
> computation.
>
> This account can be made probabilistic if we introduce a “reference
> dynamical system” and define H(f,g) as the probability of f being produced
> within time T by the dynamical system beginning from initial condition g.
> For instance, if the reference dynamical system for computing H(f,g)
> consists of a system that creates random computer programs taking g as
> input, choosing each program with probability proportional to 2-(program
> length) , then this probabilistic-dynamic perspective recovers an
> approximation of what one gets from defining H(f,g) as relative Kolmogorov
> complexity.
>
> -- Ben
>
>
>
---------------------------------------------
This message was sent using Endymion MailMan.
http://www.endymion.com/products/mailman/
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:52 MDT