Tuesday, February 25, 2003, 10:12:07 AM, Ben Goertzel wrote:
BG> I view complexity as part of a web of concepts that also, centrally, BG> includes "pattern" BG> Roughly, an entity is complex if there are a whole lot of patterns in it BG> (statically or dynamically) BG> On the other hand, what is a pattern? A pattern in X is a program P that BG> produces X, but has significantly less "basic complexity" than X. BG> What is this "basic complexity"? One approach is to define it as program BG> length: that's algorithmic information theory, in essence... BG> This mathematical approach is part of the conceptual foundations of BG> Novamente. It highlights the very real subjectivity of the notion of BG> "complexity." Note that I defined complexity in terms of pattern and then BG> defined pattern in terms of "basic complexity" ;-) You can define "basic BG> complexity" as "complexity relative to a certain observer" or "the minimum BG> length program that computes P assuming a given knowledge base K as BG> background knowledge." Then you have defined complexity in a way that is BG> specifically relative to an observer or a set of knowledge. As I'm sure you're aware, but others may not be, some interesting things have been proved about K and P. The main result is in a sense analogous to G�del's proof, but far further-reaching. That is that you cannot prove you have found the smallest program that computes P unless your axioms (knowledge base, K) is of complexity P itself (for sufficiently large P). See e.g.: http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ieee74.html and other works by Chaitin at http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ At some point I suspect that his proofs will be used to prove P!=NP but that may be a ways off. -- Cliff ------- To unsubscribe, change your address, or temporarily deactivate your subscription, please go to http://v2.listbox.com/member/[EMAIL PROTECTED]
