Complexity theory with simple examples
Ask the question “WHERE?”. Where is the center for controlling the movement of galaxies or cyclone behavior? Where is the force that unites atoms into complex compounds, those, in turn, into chains of proteins, and gives rise to such stable and complex phenomena as biological life, reason, society.
Under the umbrella of complexity theory, various models are combined that describe how, without central control, from the interaction of simple initial elements that obey simple rules, higher-order phenomena are formed that have difficultly predictable behavior and unforeseen, but stable, properties.
The article does not offer ready-made answers about the meaning of life, it can be seen through crude, rigorous analogies, but it has the daring goal of expanding the horizons of the reader, based on his imagination and some mathematical facts.
To get started, let's figure out how complex unpredictable behavior can arise based on a simple deterministic rule. Meet the “Logistic Map”:
x n + 1 = Rx n (1 - x n )
I hasten to preempt the possible thought “Well, that's boring! Now there will be formulas ... " Try to understand, it will be very interesting.
Logistic Map - describes an iterative process in which the next value of a function is analytically determined by its value in the previous step. We plot this function for various values of the “R” coefficient, taking the initial value X 0 = 0.1
1) R = 2. The graph degenerates into a line:
2) R = 3.1. Comes to an oscillation state between 2 values:
3) R = 3.47. Oscillation frequency 4:
4) R = 3.55. Oscillation frequency 8:
5) And now R = 3.999:
There are no regularities in this graph. At R = 3.999, we observe chaos. Under the chaos understand the extreme sensitivity of the final result in relation to the initial data. Let's change the initial value X 0 = 0.1000000001 (unit in 10 digits) and plot the graph in red on top of the previous result.
This picture can serve as an illustration of the so-called "Butterfly effect". As a result of a slight change in the initial value at 10 decimal places already at 30 iterations, we get a completely different graph. This property is so remarkable that it is used in pseudo random number generators.
We will get completely different graphs, plotting them for some irrational number calculated with different (extremely insignificant) accuracy. Do not take my word for it, take (1 / sqrt (2)) and go for it!
Thus, we learned that complex random behavior that seems random can occur in systems based on simple deterministic rules. Moreover, this behavior cannot be predicted in the long term because of the strong sensitivity of the behavior to the initial conditions (or the inaccuracy of physical measurements).
Let's look at another interesting example - cellular automata, and in particular, John Conway’s “Life” game .
The rules of the game specify only the behavior of a single cell among the nearest neighbors. However, we have that in the game environment of the cell without any initial prescription there are stable phenomena of a higher order. The life of individual cells, which are strictly attached to their positions, gives rise to stable disturbances in the environment, called patterns. Perturbations can be static, in a state of oscillation, or exhibit more complex behavior. For example, to move and collide, collapsing or creating new formations with bizarre properties.
A few pictures from Wikipedia to maintain interest:
Such properties or phenomena that were not explicitly set initially, but arising as a result of the processes of interaction of the initial components, are called emergent (literally, arising). These properties are created and maintained by processes within the environment. As soon as the processes disappear, the properties also disappear, as life disappears if you disassemble the body into its components, and then mechanically try to put it together.
Emergent properties are an integral feature of complex systems.
Dive deeper and turn to the work of Stephen Wolfram , published in the book "New Kind of Science".
Tungsten conducted experiments with the simplest version of the game, life, in which the medium is a long closed tape with a width of one cell. He was driven by the idea that if it is impossible to understand what is happening in this very simple cellular automaton, then there are nothing more to think about more complex systems.
The rules are simple. A cell can be alive or dead, depending on its previous state and the state of its two neighbors. Total, the subsequent state of the cell is determined by three parameters.
And now bear with us - practice in combinatorics ...
Of the possible states of 3 cells, only 8 possible combinations can be made.
Each combination can translate a cell into one of 2 possible states (on and off). A small final number of possible rules is obtained: 256 (2 8 ).
On each rule, Wolfram conducted a series of experiments with different initial data and as a result identified 4 classes of rules:
1) Almost all initial configurations are set to the same final pattern
2) Almost all initial configurations are set to the same final pattern or circulate between several final patterns
3) Most of the initial configurations create random-looking behavior and also generate triangles or other regular patterns
4) The last class combines order and randomness, generating localized structures that, being simple in themselves, move and interact with each other in a very complex way.
A picture for maintaining attention:
Class 4 is the most interesting. An example of a class rule 4 is the “rule 110” illustrated above.
There is something unexpected in him. Wolfram's student Matthew Cook proved that ... (drum roll ...) this rule is Turing complete. In other words, it is the simplest currently known computational model.
Wolfram suggested that some similar simple rule could underlie all the laws of nature. According to him, the world is a complex system generated by this simple rule on some universal cellular automaton from the big bang to the moment when you read these lines.
This statement rests on sacred debate about whether the universe is computable or computation - it is only a mental model that allows us to describe with some accuracy the trace of "something happening somehow."
The article describes only a few basic models of complexity theory. These formalisms allow us to explain how complex phenomena at the level of the whole system can arise from the behavior of the simplest basic elements.
I did not touch on models of evolution, adaptation, social self-organization based on game theory and network theory. If the article finds a response - perhaps I will write another one where I will try to highlight these aspects.
Some companiesthey are adopting self-organization as a way of existence of a social organization. That is, refusing central control, they give the individual complete freedom to choose what to do: join a ready-made project team or, starting his project, engage in the search and inspiration of like-minded people. You can find an analogy with the immune system that attacks viruses - interesting tasks find their artists. While the specialist’s vector of activity coincides with the company’s vector, everything goes on, otherwise the social system will reject the foreign body :)
Also, some models of complexity theory are the basis of flexible development methodologies , where, unlike waterfall, the system is not specified in advance, but flexibly adapts to external requirements.
Complexity A guided tour
New Kind of Science
Complexity Theory for Software Developers
Video: Stanford Lectures. Emergence and Complexity
Video: NKS Presentation by Stephen Wolfram
Video: The Universe as a Cellular Automation
Corporate Culture at Valve
Under the umbrella of complexity theory, various models are combined that describe how, without central control, from the interaction of simple initial elements that obey simple rules, higher-order phenomena are formed that have difficultly predictable behavior and unforeseen, but stable, properties.
The article does not offer ready-made answers about the meaning of life, it can be seen through crude, rigorous analogies, but it has the daring goal of expanding the horizons of the reader, based on his imagination and some mathematical facts.
Predictable unpredictability
To get started, let's figure out how complex unpredictable behavior can arise based on a simple deterministic rule. Meet the “Logistic Map”:
x n + 1 = Rx n (1 - x n )
I hasten to preempt the possible thought “Well, that's boring! Now there will be formulas ... " Try to understand, it will be very interesting.
Logistic Map - describes an iterative process in which the next value of a function is analytically determined by its value in the previous step. We plot this function for various values of the “R” coefficient, taking the initial value X 0 = 0.1
1) R = 2. The graph degenerates into a line:
2) R = 3.1. Comes to an oscillation state between 2 values:
3) R = 3.47. Oscillation frequency 4:
4) R = 3.55. Oscillation frequency 8:
5) And now R = 3.999:
There are no regularities in this graph. At R = 3.999, we observe chaos. Under the chaos understand the extreme sensitivity of the final result in relation to the initial data. Let's change the initial value X 0 = 0.1000000001 (unit in 10 digits) and plot the graph in red on top of the previous result.
This picture can serve as an illustration of the so-called "Butterfly effect". As a result of a slight change in the initial value at 10 decimal places already at 30 iterations, we get a completely different graph. This property is so remarkable that it is used in pseudo random number generators.
We will get completely different graphs, plotting them for some irrational number calculated with different (extremely insignificant) accuracy. Do not take my word for it, take (1 / sqrt (2)) and go for it!
Thus, we learned that complex random behavior that seems random can occur in systems based on simple deterministic rules. Moreover, this behavior cannot be predicted in the long term because of the strong sensitivity of the behavior to the initial conditions (or the inaccuracy of physical measurements).
Game "Life"
Let's look at another interesting example - cellular automata, and in particular, John Conway’s “Life” game .
The rules of the game specify only the behavior of a single cell among the nearest neighbors. However, we have that in the game environment of the cell without any initial prescription there are stable phenomena of a higher order. The life of individual cells, which are strictly attached to their positions, gives rise to stable disturbances in the environment, called patterns. Perturbations can be static, in a state of oscillation, or exhibit more complex behavior. For example, to move and collide, collapsing or creating new formations with bizarre properties.
A few pictures from Wikipedia to maintain interest:
 |  |  |
Such properties or phenomena that were not explicitly set initially, but arising as a result of the processes of interaction of the initial components, are called emergent (literally, arising). These properties are created and maintained by processes within the environment. As soon as the processes disappear, the properties also disappear, as life disappears if you disassemble the body into its components, and then mechanically try to put it together.
Emergent properties are an integral feature of complex systems.
Stephen Wolfram Cellular Automata and the "Rule 110"
Dive deeper and turn to the work of Stephen Wolfram , published in the book "New Kind of Science".
Tungsten conducted experiments with the simplest version of the game, life, in which the medium is a long closed tape with a width of one cell. He was driven by the idea that if it is impossible to understand what is happening in this very simple cellular automaton, then there are nothing more to think about more complex systems.
The rules are simple. A cell can be alive or dead, depending on its previous state and the state of its two neighbors. Total, the subsequent state of the cell is determined by three parameters.
And now bear with us - practice in combinatorics ...
Of the possible states of 3 cells, only 8 possible combinations can be made.
Each combination can translate a cell into one of 2 possible states (on and off). A small final number of possible rules is obtained: 256 (2 8 ).
On each rule, Wolfram conducted a series of experiments with different initial data and as a result identified 4 classes of rules:
1) Almost all initial configurations are set to the same final pattern
2) Almost all initial configurations are set to the same final pattern or circulate between several final patterns
3) Most of the initial configurations create random-looking behavior and also generate triangles or other regular patterns
4) The last class combines order and randomness, generating localized structures that, being simple in themselves, move and interact with each other in a very complex way.
A picture for maintaining attention:
Class 4 is the most interesting. An example of a class rule 4 is the “rule 110” illustrated above.
There is something unexpected in him. Wolfram's student Matthew Cook proved that ... (drum roll ...) this rule is Turing complete. In other words, it is the simplest currently known computational model.
Wolfram suggested that some similar simple rule could underlie all the laws of nature. According to him, the world is a complex system generated by this simple rule on some universal cellular automaton from the big bang to the moment when you read these lines.
This statement rests on sacred debate about whether the universe is computable or computation - it is only a mental model that allows us to describe with some accuracy the trace of "something happening somehow."
Conclusion
The article describes only a few basic models of complexity theory. These formalisms allow us to explain how complex phenomena at the level of the whole system can arise from the behavior of the simplest basic elements.
I did not touch on models of evolution, adaptation, social self-organization based on game theory and network theory. If the article finds a response - perhaps I will write another one where I will try to highlight these aspects.
Some companiesthey are adopting self-organization as a way of existence of a social organization. That is, refusing central control, they give the individual complete freedom to choose what to do: join a ready-made project team or, starting his project, engage in the search and inspiration of like-minded people. You can find an analogy with the immune system that attacks viruses - interesting tasks find their artists. While the specialist’s vector of activity coincides with the company’s vector, everything goes on, otherwise the social system will reject the foreign body :)
Also, some models of complexity theory are the basis of flexible development methodologies , where, unlike waterfall, the system is not specified in advance, but flexibly adapts to external requirements.
Recommended Sources
Complexity A guided tour
New Kind of Science
Complexity Theory for Software Developers
Video: Stanford Lectures. Emergence and Complexity
Video: NKS Presentation by Stephen Wolfram
Video: The Universe as a Cellular Automation
Corporate Culture at Valve