chaos.md

   1 # Chaos
   2
   3 In [mathematics](math.md) chaos is a phenomenon that makes it extremely difficult to predict, even approximately, the outcome of some process even if we completely know how the process works and what state it starts in. In more technical terms chaos is a property of a [nonlinear](nonlinear.md) [deterministic](determinism.md) [system](system.md) in which even a very small change in input creates a great change in the output, i.e. the system is very sensitive to [initial conditions](initial_condition.md). Chaos is a topic studied by the field called **chaos theory** and is important in all [science](science.md). In [computer science](compsci.md) it is important for example for the generation of [pseudorandom](pseudorandom.md) numbers or in [cryptography](cryptography.md). Every programmer should be familiar with the existence of chaotic behavior because in mathematics (programming) it emerges very often, it may pose a problem but, of course, it may be taken advantage of as well.
   4
   5 Perhaps the most important point is that a chaotic system is difficult to predict NOT because of [randomness](randomness.md), lack of information about it or even its incomprehensible complexity (many chaotic systems are defined extremely simply), but because of its inherent structure that greatly amplifies any slight nudge to the system and gives any such nudge a great significance. This may be caused by things such as [feedback loops](feedback_loop.md) and [domino effects](domino_effect.md). Generally we describe this behavior as so called **[butterfly effect](butterfly_effect.md)** -- we liken this to the fact that a butterfly flapping its wings somewhere in a forest can trigger a sequence of events that may lead to causing a tornado in a distant city a few days later.
   6
   7 Examples of chaotic systems are the double pendulum, weather (which is why it is so difficult to predict it), dice roll, [rule 30](rule_30.md) cellular automaton, [logistic map](logistic_map.md), [Baker's map](bakers_map.md), gravitational interaction of [N bodies](n_body.md) or [Lorenz differential equations](lorenz_system.md). [Langton's ant](langtons_ant.md) sometimes behaves chaotically. Another example may be e.g. a billiard table with multiple balls: if we hit one of the balls with enough strength, it'll shoot and bounce off of walls and other balls, setting them into motion and so on until all balls come to stop in a specific position. If we hit the ball with exactly the same strength but from an angle differing just by 1 degree, the final position would probably end up being completely different. Despite the system being deterministic (governed by exact and predictable laws of motion, neglecting things like quantum physics) a slight difference in input causes a great different in output.
   8
   9 A simple example of a chaotic equation is also the function *sin(1/x)* for *x* near 0 where it oscillates so quickly that just a tiny shift along the *x* axis drastically changes the result. See how unpredictable results a variant of the function can give:
  10
  11 | *x*   | *1000 * sin(10^9 / x)* |
  12 |-------|------------------------|
  13 | 4.001 | 455,...                |
  14 | 4.002 | 818,...                |
  15 | 4.003 | -511,...               |
  16 | 4.004 | -974,...               |
  17 | 4.005 | -335,...               |
  18
  19 **Logistic map** is often given as the typical example of a chaotic system. It is the series defined as *x[n + 1] = r * x[n] * (1 - x[n])*, which for some constant *r* (interpreted as speed of population increase) says how a population evolves from some starting value *x[0]*; for low *x[n]* the population will be increasing proportionally by the rate of *r* but once it reaches a higher value, it will start decreasing (as if by starvation), resulting in oscillation. Now if we only start to be interested in changing the value *r* and then seeing at what value the population stabilizes (for a big *n*), we make some interesting discoveries. This is best seen by plotting the stable values (let's say *x[1000]*) depending on *r*. For *r* approximately between 3.57 and 4 we start to see a chaotic behavior, with results greatly depending on the initial population value (*x[0]*). This demonstrates chaotic behavior.
  20
  21 The following is a [fixed point](fixed_point.md) [C](c.md) implementation of the above:
  22
  23 ```
  24 #include <stdio.h>
  25
  26 #define FP_UNIT 256
  27 #define DOWNSCALE_X 4
  28 #define DOWNSCALE_Y 25
  29 #define LINE_LENGTH (FP_UNIT / DOWNSCALE_X)
  30 #define GENERATIONS 1000
  31
  32 char stablePoints[LINE_LENGTH + 1];
  33
  34 int main(void)
  35 {
  36   stablePoints[LINE_LENGTH] = 0; // string terminator
  37
  38   for (int i = 0; i <= FP_UNIT * 4; i += DOWNSCALE_Y) // for different rs
  39   {
  40     for (int j = 0; j < LINE_LENGTH; ++j)
  41       stablePoints[j] = ' ';
  42
  43     for (int j = 0; j < FP_UNIT; ++j) // for different starting population sizes
  44     {
  45       int population = j;
  46
  47       for (int k = 0; k < GENERATIONS; ++k)
  48         population = (i * population * (FP_UNIT - population)) / (FP_UNIT * FP_UNIT);
  49
  50       population /= DOWNSCALE_X;
  51
  52       if (population >= 0 && population < LINE_LENGTH)
  53         stablePoints[population] = '*';
  54     }
  55
  56     printf("%.3f| %s\n",i / ((float) FP_UNIT),stablePoints);
  57   }
  58
  59   return 0;
  60 }
  61 ```
  62
  63 It outputs the following:
  64
  65 ```
  66 0.000| *
  67 0.098| *
  68 0.195| *
  69 0.293| *
  70 0.391| *
  71 0.488| *
  72 0.586| *
  73 0.684| *
  74 0.781| *
  75 0.879| *
  76 0.977| *
  77 1.074| *****
  78 1.172| **     ***
  79 1.270| **          **
  80 1.367| *               **
  81 1.465| *                   *
  82 1.562| *                     **
  83 1.660| *                        *
  84 1.758| *                          *
  85 1.855| *                            *
  86 1.953| *                              *
  87 2.051| *                               *
  88 2.148| *                                 *
  89 2.246| *                                  *
  90 2.344| *                                   *
  91 2.441| *                                    *
  92 2.539| *                                     *
  93 2.637| *                                      *
  94 2.734| *                                       *
  95 2.832| *                                        *
  96 2.930| *                                        **
  97 3.027| *                                     *********
  98 3.125| *                                  *       *     *
  99 3.223| *                               *           *      *
 100 3.320| *                             *                     **
 101 3.418| *                           **               *       **
 102 3.516| *                      ** * *   **           *      *****
 103 3.613| *                   **** *** *  * ** * *      *   ********
 104 3.711| *                **               **      ** *****  *     **
 105 3.809| *           *      **  * *        *   * *         *  *  *** *
 106 3.906| *     *        *     ***      *       *      *     *   * ***  *
 107 ```
 108
 109 Vertical axis is the *r* parameter, i.e. the population growth speed. Horizontal axis shows stable population size after 1000 generations, starting with different initial population sizes. We can see that up until about *r = 3* the stable population size always stabilizes at around the same size, which gradually increases with *r*. However then the line splits and after around *r = 3.56* the stable population sizes are quite spread out and unpredictable, greatly depending on the initial population size. Pure CHAOS!