COMP6044   Just another ECS Blogs weblog

Keywords: complexity theory, complex adaptive system theory, general system theory, nonlinear dynamics, self organising, adaptive, chaos, emergent.

For the past couple of weeks I have been trying to get my head around the idea of theories of complexity as applied to systems. What is it ? How is it measured ? how does it – or does it in fact – relate to web science ?

John Cleveland in his book “Complex Adaptive Systems Theory An Introduction to the Basic Theory and Concepts” (published in 1994 revised in 2005), states that complex adaptive systems theory seeks to understand how order emerges in complex, non-linear systems such as galaxies, ecologies, markets, social systems and neural networks.

For an explanation more useful to a layman I was advised to read ‘Complexity – A guided tour’, by Professor Melanie Mitchell (Professor of Computer Science at Portland State University). In 349 pages Melanie Mitchell has tried to give a clear description and explanation of the concepts and methods which may be considered to comprise the field of Complexity Science without the use of  complex mathematics.

One problem is that as a recognised discipline, Complexity Science appears to barely 30 years old, though work on some of its aspects go back to the 1930s. Mitchell suggests its beginning as an organized discipline could be dated to the founding of the Santa Fe Institute and its first conference on the economy as an evolving complex system in 1987.

Another problem appears to be that the sciences of complexity should be seen as not singular. In the last chapter of her book Mitchell comments that ‘most (researchers in the field), believe that there is not yet a science of complexity at least not in the usual sense of the word science – complex systems often seem to be a fragmented subject rather than a unified whole.’

Armed with these caveats I started ploughing my way through an interesting and enlightening book. The book is divided into five parts: background theory, life and evolution of computers, computation writ large, network thinking and conclusions – the past and future of the sciences of complexity. By the end of the book I knew more about such things as Hilberts problem, Goedels theorem, Turing machines & uncomputability, the Universal Turing machine and the Halting problem amongst others.

Below is summary of points I found interesting and have spurred further reading.

• Seemingly random behavour can emerge from deterministic systems, with no external source of the randomness.
• The behaviour of some simple, deterministic systems can be impossible to predict, even in principle, in the long term due to sensitive dependence on initial conditions.
• There is some order in chaos, seen in universal properties common to large sets of chaotic systems e.g. period doubling route to chaos and Feigenbaums constant.
• Complex systems are centrally concerned with the communication and processing of information in various forms.
• The following should be considered with regard evolution: Second law of thermodynamics, Darwinian evolution, organisation and adaption, Modern Synthesis (Mendel V’s Darwin), supportive, discrepancies, evolution by jerks, historical contingency.
• When attempting to define and measure complexity of systems Physicist Seth Lloyd 2001 asked how hard is it to decribe ? how hard is it to create ? what is it’s degree of organisation ?
• Complexity has been defined by:
• Size
• Entropy
• Algorithmic information content
• Logical depth
• Thermodynamic depth
• Statistical
• Fractal dimension
• Degree of hierarchy

• Self reproducing machines are claimed as viable e.g. Von Neumans self reproducing automaton, “a machine can reproduce itself”
• Evolutionary computing – genetic algorithms(GA), work done by John Holland, algorithm used to mean what Turing meant by definite procedure, recipre of a GA …. Interaction of different genes.
• Computation writ large and computing with particles – Cellular automata, life and the universe compared to detecting information processing structures in the behaviour of dynamical systems, applied to cellular automata evloved by use of Genetic Algorithms.

The points which seemed to be most relevant to web science and merit further investigation are:

• Genetic algoritms
• Small world networks and scale free networks
• Scale free distribution Vs normal distribution
• Network resilience

The future of complexity – mathematician Steven Strogatz “I think we may be missing the conceptual equivalent of calculus, a way of seeing the consequences of myriad interactions that define a complex system. It could be that this ultra-calculus, if it were handed to us, would be forever beyond human comprehension…”.