From: Ben Goertzel (ben@goertzel.org)
Date: Sat Oct 08 2005 - 09:25:17 MDT
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.
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 archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:52 MDT