Complexity (Melanie Mitchell)

Chaos theory. Based on "Complexity" by Melanie Mitchell. Seemingly random behavior can emerge from deterministic systems, with no external source of randomness. The behavior of some simple, deterministic systems can be impossible, even in principle, to predict in the long term, due to sensitive dependence on initial conditions. Although the detailed behavior of a chaotic system cannot be predicted, there is some "order in chaos" seen in universal properties common to large sets of chaotic systems, such as the period-doubling route to chaos and Feigenbaum’s constant. Thus even though "prediction becomes impossible" at the detailed level, there are some higher-level aspects of chaotic systems that are indeed predictable. Edward Lorenz, the father of chaos theory, described chaos as "when the present determines the future, but the approximate present does not approximately determine the future."

54 flashcards · Computer Science · by lakesare

What's the other name for white blood cells?
Lymphocytes The star players of the immune system are white blood cells, otherwise known as lymphocytes.
What happens when lymphocyte gets activated? Each lymphocyte can recognize, via receptors on its cell body, molecules corresponding to certain possible invaders (e.g., bacteria). Some one trillion of these patrolling sentries circulate in the blood at a given time, each ready to sound the alarm if it is activated—that is, if its particular receptors encounter, by chance, a matching invader.
Lymphocyte secretes large number of antibody molecules. Lymphocyte creates daughter lymphocytes that will help hunt out invaders and secrete antibodies against them. Lymphocyte creates daughter lymphocytes that will hang around and remember the particular invader that was seen, thus giving the body immunity to pathogens that have been previously encountered. When a lymphocyte is activated, it secretes large numbers of molecules—antibodies—that can identify similar invaders
Name 3 properties complex systems have in common. Market, ants, immune system, neurons
Complex collective behavior: All the systems I described above consist of large networks of individual components (ants, B cells, neurons, stock-buyers, Web-site creators), each typically following relatively simple rules with no central control or leader. Signaling and information processing: All these systems produce and use information and signals from both their internal and external environments. Adaptation: All these systems adapt—that is, change their behavior to improve their chances of…
What's meant by emergent behaviour?
Emergent behavior is behavior of a system that does not depend on its individual parts, but on their relationships to one another. Thus emergent behavior cannot be predicted by examination of a system's individual parts. Since simple rules produce complex behavior in hard-to-predict ways, the macroscopic behavior of such systems is sometimes called emergent
Name 3 branches of classical mechanics.
Classical mechanics was traditionally divided into three main branches: Statics, the study of equilibrium and its relation to forces Dynamics, the study of motion and its relation to forces Kinematics, dealing with the implications of observed motions without regard for circumstances causing them
What's the name of this fractal?
The Mandelbrot Set Definition of the Mandelbrot set is credited to Adrien Douady who named it in tribute to the mathematician Benoit Mandelbrot.Benoit B. Mandelbrot (20 November 1924 – 14 October 2010) was a Polish-born French and American mathematician and polymath with broad interests in the practical sciences, especially regarding what he labeled as "the art of roughness" of physical phenomena and "the uncontrolled element in life"
What formula does the Mandelbrot Set use?
c - is any number in the complex plane We start with Z0 = 0. We take random values of c, and check whether they Zn blows up to infinity. If it does, - c is not a part of the set. If c = 1: Z1 = 02 + 1 = 1 Z2 = 12 + 1 = 2 Z3 = 22 + 1 = 5 Z4 = 52 + 1 = 26 So we can see, that with c = 1, this equation will blow up. 1 is not a part of Mandelbrot set! Let's try c = -1: Z1 =02 - 1 = -1 Z2 = (-1)2 - 1 = 0 Z3 = 02 - 1 = -1 Z4 = (-1)2 - 1 = 0 So we can see, that with c = -1, this equation will NOT blow…
How is the image of Mandelbrot Set image constructed using this formula?
x-axis - real part of c y-axis - imaginary part of c Pixels are coloured according to how soon the sequence Z0, Z1, Z2, Z3 crosses an arbitrarily chosen threshold. Treating the real and imaginary parts of c as image coordinates on the complex plane, pixels may then be coloured according to how soon the sequence Z1, Z2, Z3 crosses an arbitrarily chosen threshold, with a special color (usually black) used for the values of c for which the sequence has not crossed the threshold after the predeterm…
Name 2 examples of the sigmoid function.
Sigmoid function is defined as a function that has a characteristic S-shape. Logistic function Hyperbolic tangent Some sigmoid functions compared. In the drawing all functions are normalized in such a way that their slope at the origin is 1.
Write down logistic function.
A typical application of the logistic equation is a common model of population growth (see also population dynamics), originally due to Pierre-François Verhulst in 1838, where the rate of reproduction is proportional to both the existing population and the amount of available resources, all else being equal.
Logistic map VS logistic function?
Logistic map is a discrete-time version of the logistic equation. Logistic map x represents the population at any given time t, and r represents the growth rate. In other words, the population level at any given time is a function of the growth rate parameter and the previous time step’s population level. If the growth rate is set too low, the population will die out and go extinct. Higher growth rates might settle toward a stable value or fluctuate across a series of population booms and busts…
What does each term mean in the logistic map? I give the equation for the logistic map to show you how simple it is. In fact, it is one of the simplest systems to capture the essence of chaos: sensitive dependence on initial conditions.
x - value between 0 and 1, denoting percentage of max population at any given time t R - growth rate The columns represent growth rates and the rows represent generations. The model always starts with a population level of 0.5 and it’s set up to represent population as a ratio between 0 (extinction) and 1 (the maximum carrying capacity of our system). This nonlinear difference equation is intended to capture two effects: reproduction where the population will increase at a rate proportional to…
How does the logistic map behave for different r-s? x - value between 0 and 1, denoting percentage of max population at any given time tR - growth rate
If the growth rate is set too low (<1), the population will die out and go extinct. Higher growth rates might settle toward a stable value or fluctuate across a series of population booms and busts. When R is approximately 3.569946, the values of x no longer settle into an oscillation; rather, they become chaotic.
What will be the behaviour of the logistic map for growth rate = 2, and x0 = 0.2?
It will converge on x = 0.5. You may have guessed it already: if R = 2 then xt eventually always gets to 0.5 and stays there. The value 0.5 is called a fixed point: how long it takes to get there depends on where you start, but once you are there, you are fixed.If you like, you can do a similar set of calculations for R = 2.5, and you will find that the system also always goes to a fixed point, but this time the fixed point is 0.6.
What's attractor for some value of r?
It's the value x converges to, no matter what x0 we start from. Attractor can be either: fixed point, oscillation, or chaotic (strange attractor). This oscillation will be reached eventually no matter what value is given for x0. This kind of regular final behavior (either fixed point or oscillation) is called an "attractor", since, loosely speaking, any initial condition will eventually be "attracted to it".
What's meant by the period of the logistic map?
When the logistic map oscillates between n values on each next iteration eventually. For values of R up to around 3.4 the logistic map will have similar behavior: after a certain number of iterations, the system will oscillate between two different values.Because it oscillates between two values, the system is said to have period equal to 2.
What happens when the R becomes ~3.569946 in a logistic map?
When R is approximately 3.569946, the values of x no longer settle into an oscillation; rather, they become chaotic. Period effectively becomes infinite.
Name 3 types of attactors.
Attractor can be either: fixed point oscillation chaotic (strange attractor) So far we have seen three different classes of final behavior (attractors): fixed-point, periodic, and chaotic. (Chaotic attractors are also sometimes called "strange attractors.") Type of attractor is one way in which dynamical systems theory characterizes the behavior of a system. Moreover, for the values of R that produce chaos, if there is any uncertainty in the initial condition x0, there exists a time beyond whic…
Name the surprising property of chaos, as Robert May stated. The fact that the simple and deterministic equation the logistic map can possess dynamical trajectories which look like some sort of random noise has disturbing practical implications. Robert May 1936-2020, mathematical biologist
Prediction à la Laplace is impossible not only in practice but also in principle, since we can never know x0 to infinitely many decimal places. For example, erratic fluctuations in the census data for an animal population need not necessarily betoken either the vagaries of an unpredictable environment or sampling errors: they may simply derive from a rigidly deterministic population growth relationship.
Explain the axes of the bifurcation diagram of the logistic map.
x-axis: values of R y-axis: attractor values for each R For example, for R = 2.9, x reaches a fixed point attractor of x = 0.655. At R = 3.0, x reaches a period-two attractor.For R somewhere between 3.4 and 3.5, the diagram shows a bifurcation to a period-four attractor, and so on, with further period doublings, until the onset of chaos at R approximately equal to 3.569946. Nicholas Metropolis, Myron Stein, and Paul Stein, working at Los Alamos National Laboratory, showed that not just the logi…
What's a unimodal function?
A function with a single highest value, which is also the only local maximum. A common definition is as follows: a function f(x) is a unimodal function if for some value m, it is monotonically increasing for x ≤ m and monotonically decreasing for x ≥ m. In that case, the maximum value of f(x) is f(m) and there are no other local maxima.
What are these abrupt period doublings called?
Bifurcations This succession of bifurcations culminating in chaos has been called the "period doubling route to chaos". Nicholas Metropolis, Myron Stein, and Paul Stein, working at Los Alamos National Laboratory, showed that not just the logistic map but any map whose graph is parabola-shaped will follow a similar period-doubling route.
Why is logistic map unimodal?
x-axis: xn y-axis: xn+1 For any r!
Name 2 universal features of chaotic systems. The term chaos, as used to describe dynamical systems with sensitive dependence on initial conditions, was first coined by physicists T. Y. Li and James Yorke. The term seems apt: the colloquial sense of the word "chaos" implies randomness and unpredictability, qualities we have seen in the chaotic version of logistic map. However, unlike colloquial chaos, there turns out to be substantial order in mathematical chaos in the form of so-called univers…
1. Any unimodal map will bifurcate. Any map whose graph is parabola-shaped (not just the logistic map) will follow a similar period-doubling route. Here, "parabola-shaped" means that plot of the map has just one hump—in mathematical terms, it is "unimodal".2. Feigenbaum's constant What this means is that as R increases, each new period doubling occurs about 4.6692016 times faster than the previous one.
What do these values mean?
Bifurcation 1, bifurcation 2, bifurcation 3: R1 - period of 21 R2 - period of 22 R3 - period of 23 Values of r when these bifurcations happen: 3.0 3.44949 3.54409
What's the second law of thermodynamics? For this reason, it is often said that entropy is an expression of the disorder, or randomness of a system, or of the lack of information about it
Entropy of an isolated system never decreases over time. Isolated systems spontaneously evolve towards thermodynamic equilibrium, the state with maximum entropy.
Describe the puzzle "Limitation of the Second Law of Thermodynamics" that James Clerk Maxwell proposed in his 1871 book "Theory of Heat".
A box is divided into 2 halves, with a demon controlling a hinged door. This demon lets only fast molecules through to one half, and slow molecules to another half. The idea is that this goes in contrast to the second law of thermodynamics. No work has been done by the demon (or close to no work, - feasible designs for such a door have been proposed), yet entropy decreased. Box that is divided into two halves by a wall with a hinged door.The door is controlled by a "demon", a very small being w…
Name 2 solutions to the Maxwell's "Limitation of the Second Law of Thermodynamics" puzzle. Has any other work been done by the demon? We assume that the work of closing and opening the door is negligible.
James Maxwell: second law (the increase of entropy over time) is not really a law at all, but rather a statistical effect that holds for large collections of molecules, like the objects we encounter in day-to-day life, but does not necessarily hold at the scale of individual molecules. James Maxwell, 1831 - 1879 Leo Szilard: proposed that it is the "intelligence" of the demon, or more precisely, the act of obtaining information through measurement, that constitutes the missing work. Szilard was…
Name 3 of the Hilbert's problems. David Hilbert posed 23 problems in 1900 at the International Congress of Mathematicians in Paris. David Hilbert, 1862–1943
Is mathematics complete? That is, can every mathematical statement be proved or disproved from a given finite set of axioms? For example, remember Euclid's axioms from high-school geometry? Remember using these axioms to prove statements such as "the angles in a triangle sum to 180 degrees”? Hilbert's question was this: Given some fixed set of axioms, is there a proof for every true statement?Is mathematics consistent? In other words, can only the true statements be proved? The notion of what i…
What happened in 1930, when Hilbert held a meeting expressing his confidence that the answer to these 3 questions is "yes"? Is mathematics complete? That is, can every mathematical statement be proved or disproved from a given finite set of axioms? For example, remember Euclid's axioms from high-school geometry? Remember using these axioms to prove statements such as "the angles in a triangle sum to 180 degrees”? Hilbert's question was this: Given some fixed set of axioms, is there a proof for…
25 year old mathematician Kurt Gödel announced his incompleteness theorem. This theorem stated that if the answer to question 2 is "yes" (i.e., mathematics is consistent), then the answer to question 1 (is mathematics complete?) has to be "no".If mathematics is consistent, then mathematics is not complete. However, his optimism turned out to be short-lived. Very short-lived. At the same meeting in 1930 at which Hilbert made his confident assertion, a twenty-five-year-old mathematician named Kur…
How can the instruction be encoded in a Turing machine?
—Current State—Current Symbol—New State—New Symbol—Motion—
What's Entscheidungsproblem?
It's German for "decision problem". Is there always a procedure that can decide whether or not a given statement is true? Turing's answer is no. Turing proposes a Halting problem to prove it. Can we decide a Turing machine that is an infinite loop detector? The answer is no, because we can feed a special program. The origin of the Entscheidungsproblem goes back to Gottfried Leibniz, who in the seventeenth century, after having constructed a successful mechanical calculating machine, dreamt of b…
What's Modern Synthesis?
The Modern Synthesis describes the fusion of Mendelian genetics with Darwinian evolution that resulted in a unified theory of evolution.
Why were Charles Darwin & Gregor Mendel proponents fighting initially? You would think that the dissemination of Mendel's results would be a big boost for Darwinism, since it provided Darwin’s theory with an experimentally tested mechanism of inheritance. But for decades, Mendel's ideas were considered to be opposed to Darwin's. Charles Darwin, England, 1809-1882. Gregor Mendel, Austria/Czech Republic, 1822–1884Born in a village in Austrian Empire (now Czech republic), served as a priest in Brn…
Darwin: evolution is continuous, organisms can differ from one another in arbitrarily minute ways Organisms can differ from one another in arbitrarily minute ways.Mendel: variation is discrete A pea plant is either tall or dwarf, but nothing in between. After many bitter arguments between the early Darwinists and Mendelians, this false opposition was cleared up by the 1920s when it was discovered that, unlike the traits of Mendel's pea plants, most traits in organisms are determined by many gen…
Mitosis VS meiosis?
Mitosis - make 2 identical copies Mitosis is the Greek word for thread, after the thread-like chromosomes that can be seen under the microscope in dye-stained cells during cell division.Meiosis - make 4 "half-copies", in preparation for sexual reproduction, where their genetic content will be made whole again by the process of fertilisation. Meiosis means a "lessening" in Greek. This refers to the outcome of meiosis, where the genetic information in each new cell is halved. Notice how we design…
Every cell in your body contains almost exactly the same complete DNA sequence, which is made up of a string of chemicals called nucleotides. Nucleotides contain chemicals called bases, which come in four varieties, called (for short) A, C, G, and T. Due to chemical affinities, A always pairs with T, and C always pairs with G.
What's effective complexity?
To calculate the effective complexity, first one figures out the best description of the regularities of the entity; the effective complexity is defined as the amount of information contained in that description, or equivalently, the algorithmic information content of the set of regularities.
What's logical depth?
In order to get closer to our intuitions about complexity, in the early 1980s the mathematician Charles Bennett proposed the notion of logical depth. The logical depth of an object is a measure of how difficult that object is to construct. In Bennett’s words, “Logically deep objects ... contain internal evidence of having been the result of a long computation or slow-to-simulate dynamical process, and could not plausibly have originated otherwise.” Or as Seth Lloyd says, “It is an appealing ide…
Who came up with the word fractal?
Benoit Mandelbrot. In 1975 Mandelbrot solidified hundreds of years of thought and mathematical development in coining the word "fractal" and illustrated his mathematical definition with striking computer-constructed visualizations. These images, such as of his canonical Mandelbrot set, captured the popular imagination; many of them were based on recursion, leading to the popular meaning of the term "fractal".
What's the difference between Turing machine, and Universal Turing machine (UTM)?
Universal Turing machine is a simple Turing machine, but one that has the code of another turing machine encoded as symbols on its tabe. Universal Turing machine U
How many possible rules can the elementary cellular automata have? The term rule refers to the entire list of configurations and update states, not to the individual lines in the list. Wolfram termed these "elementary cellular automata". He figured that if he couldn’t understand what was going on in these seemingly ultra-simple systems, there was no chance of understanding more complex (e.g., two-dimensional or multistate) cellular automata.
22^3 = 28 = 256 Since there are only eight possible configurations of states for a three-cell neighborhood and only two possible ways to fill in the update state (on or off) for each of these eight configurations, there are only 256 (28) possible rules for elementary cellular automata.
What's the logic behind the numbering system for elementary cellular automata used by Stephen Wolfram? Stephen Wolfram, London, 1959
Rule 30
What classes did Stephen Wolfram observe his cellular automata fall into? In Wolfram's exhaustive survey of all 256 elementary cellular automata, he viewed the behavior over time of each one starting from many different initial configurations.
Class 1: Almost all initial configurations settle down to the same uniform final pattern. Rule 8 is an example of this class; for all initial configurations, all cells in the lattice quickly switch to the off state and stay that way. Class 2: Almost all initial configurations settle down to either a uniform final pattern or a cycling between a few final patterns. Here, the specific final pattern or patterns depends on the initial configuration. Class 3: Most initial configurations produce rando…
What's the relationship between cellular automaton and Universal Turing machines?
Rule 110 is indeed universal. Wolfram speculated that, because of this complexity of patterns and interactions, all class 4 rules are capable of universal computation. However, in general it is hard to prove that a particular cellular automaton, Turing machine, or any other device is universal. Turing's proof that there exists a universal Turing machine was a triumph, as was von Neumann’s proof that his self-replicating automaton was also a universal computer. Since then several researchers hav…
Antigen vs antibody?
Antibody - molecules secreted by lymphocytes to neutralize pathogens. Antigen - molecule on the outside of the pathogen. Antigens are "targeted" by antibodies. Each antibody is specifically produced by the immune system to match an antigen after cells in the immune system come into contact with it; this allows a precise identification or matching of the antigen and the initiation of a tailored response. Types of lymphocytes
What's a scale-free network?
The ratio of very connected nodes to the number of nodes in the rest of the network remains constant as the network changes in size. A distribution like this is called self-similar, because it has the same shape at any scale you plot it. In more technical terms, it is "invariant under rescaling". This is what is meant by the term scale-free. Put simply, the nodes of a scale-free network aren't randomly or evenly connected.Scale-free networks include many "very connected" nodes, hubs of connecti…
What's preferential attachment?
A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who are already wealthy receive more than those who are not. The Matthew effect of accumulated advantage, Matthew principle, or Matthew effect for short, is sometimes summarized by the adage "the rich get richer and the poor get poorer". The concept is appli…
What's basal metabolic rate?
Basal Metabolic Rate is the number of calories required to keep your body functioning at rest. An organism’s metabolic rate can be defined as the rate at which its cells convert nutrients to energy, which is used for all the cell’s functions and for building new cells. The organism gives off heat at this same rate as a by-product. An organism’s metabolic rate can thus be inferred by measuring this heat production.
What are the formulas for volume of the sphere VS surface area of the sphere?
In living organisms, - why metabolism doesn't increase in proportion to the body mass?
If a hamster has volume V (and therefore mass) 8 times bigger than the volume of a mouse, - hamster surface area A would be just 4 times bigger. That would make a very hot hamster! Generating eight times the heat with only four times the surface area to radiate it would result in one very hot hamster. Similarly, the hippo would generate 125,000 times the heat of the mouse but that heat would radiate over a surface area of only 2,500 times the mouse’s. Ouch! That hippo is seriously burning. Natu…
What's Kleiber's law?
It's the idea that metabolic rate is proportional to bodymass3/4. Reasoning that organisms must not get too hot, - in 1883, Max Rubner hypothesized, that the rate of metabolism should be proportional to the area of the organism - that is, to bodymass2/3.However, in 1930, Max Kleiber performed careful measurements, and his data showed metabolic rate is proportional to bodymass3/4. The mass of living systems has a huge range: from bacteria, which weigh less than one one-trillionth of a gram, to w…
What is the fractal dimension of the koch curve? The Koch snowflake can be constructed by starting with an equilateral triangle, then recursively altering each line segment as follows:- divide the line segment into 3 segments of equal length.- draw an equilateral triangle that has the middle segment from step 1 as its base and points outward.- remove the line segment that is the base of the triangle from step 2.
In analogy with the traditional definition of dimension, we defined the fractal dimension of the Koch curve this way: 3dimension = 4, which yields dimension log43 = 1.26. We saw that in the Koch curve, at each level the line segments were one-third the length of the previous level, and the structure at each level was made up of four copies of the structure at the previous level. More generally, if each level is scaled by a factor of x from the previous level and is made up of N copies of the pr…
How is power-law distribution a fractal?
Because it's self-similar in different scales. The take-home message is that fractal structure is one way to generate a power-law distribution; and if you happen to see that some quantity (such as metabolic rate) follows a power-law distribution, then you can hypothesize that there is something about the underlying system that is self-similar or "fractal-like".
Evolutionary biologist Dan McShea has given me a useful way to think about these various issues. He classifies evolutionists into three categories: adaptationists, who believe that natural selection is primary; historicists, who give credit to historical accident for many evolutionary changes; and structuralists, such as Kauffman, who focus on how organized structure comes about even in the absence of natural selection. Evolutionary theory will be unified only when these three groups are able t…