Tale of the coder, of his wife and of the dangerous AI

In the time that were to come, a venerable coder was telling of the beauty of his craft to his young wife.

« Dear wife, we coders, like wizards, build wonderful constructions out of logic that like oracles can predict the future in a nice pure way...
We give to our creature a long list of random events of the past, and such as a wonderful new born child without no prior knowledge our creature learns by itself what is a cause and what might be consequence in the future, guessing correctly the web of signal of causes and consequences by logic. Our creation are better than humankind which judgement is often clouded by ridiculous affections at predicting outcomes!

Husband, can the oracle fails?

Well it can, but this is so seldom you can discard it as something never happening, and anyway we use our creations on harmless jobs such as choosing the best ad for you. For now, it works very well. So well, it is creepy. Why?

Would you bet your life, my dearling, that most of the power of your algorithm is not from its accuracy but like for a religion in its power of self prophecy? Is it you trusting so much your automata you weight heavily for choosing its early conclusions as valid, and that maybe he has learned through the cloud of your excessive confidence that it should trust itself? Have you correctly taught your creation to doubt itself my dear?

You seem very meta-physical my dear today .... You may be blond and young, but my tingling senses tells me this question could have serious implications.

Dear husband, cannot you notice that your bright creation is proposing on your screen a targeted advertisement for a dating site for young ladies. Are you finding your 20 years old wife too old? »

The story tells that a reasonable amount of doubt in your infallibility  can save an happy marriage, and that coders thinks better of what false positive means when confronted in their life with a worst case failure that is supposed to not happen that often. 

The story also tells that we should not believe in our creations, but carefully measure they achieve their goals.

Too many knobs is not a good idea

Have you ever done the electricity board in a house and developed software?

If so, you will know the basics of not burning your house down: Keep It Simple Stupid.

Electric board are built by evenly setting the charge on segment in parallel, than chaining small sub segment in series.

The rule is balance the load on every segment, isolate them and every sub-segment.

A classical modern house will have 10 sub-segment being potentially in 0/1 states. Hence 1024 states which is quite a lot of complexity.
 
If you add equipment on the circuitry or incorrectly estimated your load compared to your input you may:
- use too much power compared to the input (resulting in power loss);
- use too much power compared to the size of your wire and overheat some cables hence having local overload.

If electricians did not knew their job it would happen, resulting in unsafe configurations. To find them a method would be to turn on and off every apparatus in the house to explore safe and unsafe configuration. Happily in 2016 it almost never happens in correctly built housing.

Something even worse could happen though: short circuits. if someone by laziness put a non protected segment directly on the main power and forget to limit its power output, you can overheat so much a wire it creates a fire.



Well, electricity boards best practice is a sane example of how to avoid disaster by tearing down a complex problem in simple practice. Still the «state» described by the list of all potential configurations is equal to 2^(number of switchs). So 10 apparatus is still a 1024 states.

Now let's talk of software. A software like mysql has 400 parameters. Some of them able to take discreet values ranging from 0 to all your memory (in size) others taking between selected values.

The number of states describing a software is way more complex than the number of states achievable by using a whole building integral electrical circuitry.

Worse : in computer isolation is like sex for the teenagers everyone talks about it, hardly anyone do it.

Hence in our software that are memory bound/CPU bound we often have parameters that antagonize one another.

In mysql so "mem" parameters affects the main engine, others the memory used to serve each requests. Some are global some are local. But memory is fixed in size. The job of sysadmins is a tad like an electricians trying to balance with the knobs knows as software configuration parameters the load on both CPU and RAM and IO  so that your software is at max speed of working.

Software don't get under powered or short circuit. But if set wrongly the parameters can make the software degrade its performance in a chaotic dramatic way.

For instance : memory access is around 4 to 100cycles in cache, 1500 to memory, a lot to hard drive, SSD and network.

Your worst nightmare is swapping: running out of memory and having to freeze/thaw data from out of the silicon of the motherboard.

So, with 400 parameters that are not isolated from one another configuration is for a human impossible.

Most wannabe consultant will say: I do not care the price of memory is so cheap we can still buy more memory, I will object that L1/L2/L3 are not extensible and they yield up to 100x improvement in speed. Others will say, as long as it works even slow it still works. I will object that slowing by 10000 thousands your requests may make your request timeout.

The simple part of scalability/availability (mysql doc)

In fact, performance problem snowballs. The more slow query/buffer are being filled, the more it will encumber your memory with relics of past queries in which the state is unknown.


Some sites like mariadb will propose you template. Some company can send you consultants. There is here another problem that I wish you to encounter : you can have success.

A misconception from developer of IT at my opinion is perfect memory is a memory that remembers everything.

My theory is a perfect IT system has a moving window of data that are kept with degraded precision over time and/or irrelevance. You wish your data to stay in a constant size of memory whatever the future is. The only data that should be kept are the one that are relevant and that is information.

Most companies I have worked with let data grow in size while they let their database grow in numbers of entries. The growing number of users can be easily handled (horizontal sharding/partitioning). The other one requires to understand that database are relational. Which often means to be careful to try to make partitions that limits the hop in requests from computers to computers, burning up to 1000 000 000 cycles.   That is coupling the exact opposite of isolation.


On top of this you probably have web services requiring operations to happen in a timely fashion. Most companies just ignore capacity planning. They prefer «scalability». It is a generic term saying that they think they know how to double the hardware (and thus operational costs) and gain a 40% gain in throughput, ignoring the epsilon latency introduced in the process. Still hardware nowadays and electricity are still way lower than workforce. A daily coder's pay is worth a server. So why care?

So modern software have a nasty mathematical property by design, the more success you have the more bound you are to double your cost for every 40% increase in your user base on your underpowered services.

Still mysql doc: it is in the HA groups you add your servers for "scalability"

I know you double initially low expanses. But still it is an exponential growth that is more than linear ... inducing a diminishing return for the acquisition of new customers. And as Microsoft, google, facebook proved it, software industry is about network effects: the more people use your software, the more value it has. It is a realm of natural monopoly and diminishing return thus of prices having to grow the more a software have success.




In this I did not even dared speak of the effect of a failure due to a timeout propagating in a web of interconnected (coupled) services. These local software failures can dramatically trigger by a snowball effect the loss of mutualized resources... like amazon in eastern zone :)



My conclusion is the following; for simple reasons of too many knobs software are hard to configure, and there is no silver bullets (distributed databases, nosql also suffer this flow). I took the example of mysql because it is a fairly commonly used piece of infrastructure in backend technology. But on top of that you may have routers, firewalls, load balancers, memcached....

In computer industry at the opposite of electrical workers we seem to ignore in our models the costs of our lack of isolation and we create the equivalent of shortcuts. 

The too many knobs effect coupled with the lack of isolation triggers leaks of behaviour making our software able to fail in worst case in dramatic ways and propagate as far as affecting large unit of works (datacenters, cloud...).

Hybris is our problem. It is not there are bad developers out there that is the real problem. It is much more we believe in our capacity to handle a lot of complexity. But some level of complexity are not in the reach of our brain.

The software industry is ultimately human bound in its capacity to handle a given amount of complexity/information in its brain. 

Search engines, please add temperature to your settings

The web is big. It is a network which value is to be connected. And we need an index to access it, else information are lost. It is called search engine. And I think they function to well.

Okay some engines are plain unusable. I am talking about the good ones.

What is a document's meaning?

It is at first approximation a vector in a non orthogonal multi dimensional base constituted by the invariant form of words with their occurrences.

This vector points to a direction. For describing this direction we use "key words".

You can visualize it as a transformation of a whole text into "the smallest canonical non reducible key words" that are idempotent to a bigger text. Like a mapping to the space of sets of words to a sub space of set of words. Key words forming a new base to express the meaning of thousands of words in a synthetic way. 

A documents contents can be easily expressed in a base of key words that are "strong meaning full words". You can thus reduce language and ideas without to much loss of meaning.

These vectors can be measured and you can make normalization, cross products, scalar product.

A scalar product is a projection of a vector on a vector and it results in telling you how much time vector A is compared to vector B. Hence, you can after normalization sort easily and compare text that are similar to the key world ideal texts. You can also "compress with loss" a text in a smaller base  made of key words. This what being a base is. A reduction to the smaller set of dimensions that are orthogonal. A reduction of the degrees of liberty. Geometrically, it makes sense.

Given the fact we have very fine tools in Euclidean geometry, with 2500 year old knowledge it is a very convenient way to represents text.

There are some caveats of course.

At the opposite of school geometry, the base is not complete... language are not all constructed the same ... there are more than one form, ambiguities ... This is what NLP deals with. And it is freaking harder than doing geometry. But I am focusing on geometry right now. I consider NLP as an accidental problem not an essential one on this topic.

The meaning of a word can change according to the context meaning that "diagonalisation" requires to sometimes degenerate a dimension (word meaning) in more than one according to the other words.

Words have a little uncertainty in their meaning. And a small step for an algorithm is not a step for a staircase.

So... how do you actually make the magic of compressing a 10k word document into 1 or more keywords?

The way it is done is by taking human beings that are very good at tagging text and let them define the keywords for corpuses of text. And learn. I guess machine learning automate this process. You can by using enough tagger "diminish the bias" of the human taggers with statistical treatment used in everyday experimental activities. It works.

You can  make a statistical analysis to then determine according to the input what is the separate probabilities for one or n orthogonal dimensions (made of a linear combination of words or a single one from the input text) to appear when a given keyword is given. Xhi² is a great tool for this. You measure positive, negative contributions and you also for each dimension considered check it is not random. For instance "the", "that", "a", "an" tends to not be correlated to any keywords so you can filter them out as not being part of any basis of any keywords. You diminish the degrees of liberty without loosing meaning.

You deduce from this or other methodologies from a learning corpus ways to guess keywords from frequential analysis. (text to keyword)

Of course, you can use meta data to change the occurence (tittle can be considered more heavy than words in the chapters/section/paragraph)

Then, you can just do cosinus similarities from the sets of "ideal documents" triggered by the keywords matching score using distances. Distances following the imperative properties of being defined normed and positive. So you can actually choose other norms than L2 (classical euclidean norm).

It gives you a relation of order thus a ranking.

Until now, I am fine with this.

I guess machine learning comes into handy for over industrializing this.

However one thing bugs me. As much as the difference between precise and exact.

Feedback loops... with amplification.

S = - k . ln(O)

What makes information is having the less numerous  more relevant choices being shown to you over the whole corpus of information. The "first page" accuracy.

Basically search engine relevance tends to minimize absolutely the informational entropy. Which seems a good goal.

If a kid ask for a recipe of a cake and fall on porn this is not cool.

However, because of using the "network/social/link/domain" context, we introduce a feedback loop based on how much "other people" rate the keywords validity. And without being a wizard, I guess mathematicians already guessed that collecting data on the "personnal" context of a user help increase the relevance based on what you expect and what your social context tends to find relevant.  And it is cool too.

If I need to do text processing, it might point me to the "state of the art" if my neighborhood are professional. In a professional context it standardizes the education. Leading you to stuff like stackoverflow where discussion happens and letting you avoid a lot of pit traps. To be honest I don't know if search engines go as far as using sociogram as an input. But, that would increase the relevance of keywords in a given social context. 

And, for instance if I ask a keyword for something ambiguous on which I am biased, it is better for increasing my liking of the results to show me what I like initially.

Just like when you go on youtube ask for "joe dassin" and when you are a metalhead (like me) youtube will show you on the next suggestions a lot of joe dassin and metal. Not rap, or traditional music, or whatever. Just metal. (it is much more like a moving average with a weight  decreasing over time to be honest, but still this is accidental not essential).

It is indeed what I like and I am often pleased with it, and I do indeed make some nice discoveries.

It also reinforce my biases with time. I go on youtube sometimes to be surprised, to discover stuff.

And I feel cornered into a caricature of my own self.

And I fear that most of us of get  reinforced in our own biases. But these are just feelings and theories and vague intuition. Nothing tangible.

I guess with time and enough data about people's query over time we could measure if my hypothesis are real or not. We could measure the evolution of the musical choices and diversity of "patterns" in playlist according to the age of persons over time. (melodies, arrangements, artists, ....) and we could influence people's culture.


Clustering of opinions reinforced by social networks.

This one is simple. Some people don't want to change. Some people don't want to hear the earth is flat, other it is patatoidal, and some spheric.

Me, I love Sir Terry Pratchett's Disc world and Erasthothènes and watch NASA pictures of the earth. So I am okay with all the possible shapes of the earth. Even the ring shaped earth from Niven's SF.

However it is not everybody's case, and  some people with biases prefer to concentrate in clusters of reading/writing that are mutually enforcing belief....  like some conspiracy theorists.

For instance we all fear propaganda from terrorism on the internet. But how does it happens you never randomly fell on one of these sites, and oppositely how can this person never get in touch with your culture? You know they exist, but you never had the occasion to speak with them and magic of humanity happening sometimes help them turn into better persons. You could also fell for their idea to be honest. So should we be scared?  Are some people irreversibly bad?

I am a great fan of Periclès. He used to say "polemic is life".

The world of progress (as opposed to immobility) comes from ideas not words.

Words are imperfect media for ideas, because ideas are grey, intangible, a moving target ...

And for this moving target to progress, it requires dialog/exchanges that are not always comfortable. Yes basically I say polemists (called trolls nowadays) are a necessary evil of all progressive regime. Do we need progress? Tell me : is the world in a trajectory you like? Is global warming cool? Are wars cool? Is terrorism cool? Is the increase of pollution, poverty cool?
Well, I don't benefit any of these, so my own personal contextual selfish answer is no. I want society to progress. Can I do it alone? No. So I have to able to be in touch with other people and dialog.

Making people see what they want above all at my own personal opinion (I share with myself) goes against the acceptation of diversity of points of views and dialog.

Search algorithm will get all the more precise that the feedback loop will  reinforce the contextual meaning of them.

But exact is not precise. pi = 3.14159 is precise. pi = 4 [+- 2] is exact in Euclidean geometry. pi = 4 is both exact and precise in Taxicab geometry.   

A potential solution to this unproven problem ?

In multi agent simulation based on physical statistics they used to model people's rationality in accordance to Fermi Dirac or Maxwell Boltzman distribution of energy. As if "economical agent" were rational but for modeling the uncertainty/irrationality of human behaviour they would add a factor temperature. Something saying : well there is a clear advantage for agent X to behave this way, BUT you never know. This temperature factor could vary more or less. A parameter you could set in accordance to real world observations. Basically you'd replace a fully deterministic algorithm by one tainted with some randomization. The "amount" of randomization being related to its physical equivalence of temperature.

In some model magnetic model could be used to model the influence of the neighborhood. Sometimes positively (better use the same software as industry is demanding) sometimes negatively (I don't want to wear the same shirt as my neighbor).  

What I loved was a simulation on the behaviour of the fish market in Marseilles.

They had a simulation that basically validate an experimental strategy used by buyer that was to be loyal to ONE buyer (because you get discounts for instance), but sometimes explore the competition in case the remaining competition either increase its competivity or your buyer decrease.

Trust you are right, but check.

These simulation were not the true world. Sometimes they were matching experimental evidences though. And making the market converge to less instability in prices, less fish thrown away.

However some stuffs were perturbing. In a simulation without temperature the agents can evolve in non interacting clusters or in constant noise.  Both cases would lead to an unstable market with a global loss of utility/income for everyone. Lose - lose situations.

Another stuff was perturbing if you made the "influence" parameter recomputed every turn according to the distance and effectiveness of the influence, the more a cluster was polarized and strong, the more it would make itself harder, and could become irreversible and the compensation in temperature to fix this states would go higher. Making the problem non reversible.

Slowly ghettoing people in their own behaviour.

When I look at my social networks, they all seem clusterized this way .. in a sort of progression of radicalization of opinions.



I do feel a disturbance in the increased use of algorithm that works to well to show me what I want.

Actually my little brain could be wrong. Who am I to question the smartest engineers in the world when I a kind of small imperfect person on the Internet?

Maybe you are perfect. I am not. I am human, I do err, I do make mistakes, and I like to believe in my capacity of correcting myslef. For this, I need to be exposed to "noise".

Please dear search engines, give me back my capacity to lower my biases and give me a setting for loosing the "precision" on your result. I want a stupid button ranging from "I don't want to see noise 'cause I am focused on technical problem solving it the one best way" to "I am in the mood for exploring the world and question myself and see totally crazy surprising stuffs".

I would gladly accept to be "polarized" in the one best way of thinking if first I believed in a non ambiguous proven immutable truth, and also if it did not resulted in increasing the violence of the exchanges. Something about this could trigger instability and violent moves at my opinion.

And I dare say it could be measured. By applying measures of the entropy on searches over time. But economically I fear there are indirect incentives for polarizing people's opinion when you are both judge of what is relevant and benefit from directing people in comfortable clusters that generates revenues. Why do not we want to see it? Because, we all enjoy to live a peaceful life without conflicts. Sometimes like a frog in water slowly heating and so numbed by comfort we forget to jump out of the water when temperature gets critical. 

 
But, I am not like every frogs I also want to see what I do not want so that I can apply my own critical judgement to my own self and improve.

I could use more than one search engine you think like on a fish market. But actually we know one engine has the biggest overall relevance that also influences the direction of the other ones. So maybe the "temperature" factor is fubar for this case and we may rely on the big elephant in the room to wake up.

I just wonder if by avoiding small conflicts now for comfort we are not building up a bigger more violent one later.

Using python to visualize randomness

Heard of randomness?

What is random: something that given a serie of chronological events (happening after one another) whatever long the time serie is, we cannot predict the future.

Two kinds of events are random; purely random events (stochastics) or mathematically deterministic equations that are so sensitive to initial conditions that they are very hard to predict.

PRNG is the second kind of beast.

Takens series are an intuitive way of trying to see if something is random in a space phase. Here because our brain is limited I took only 3 dimensions. Anyway maplotlib sux at doing projections from n dimensions to 3 in a way that is easy to see.

You take segment of time series and you make linear visualization of the serie in function of its former self. And for the fun I added an alpha (the more you are in the past, the fader the color is), and I added as quivers the variation of variations
Script here : https://gist.github.com/jul/0f16782ed01f18c2c72a

Here are the results :

First order Takens for GE opening prices are swirling in the negative sense

Nice vortexes :)

2000 Random int between 0,32. The fadest, the oldest data.

Another point of view of on randint

Takens series were once used in an article to make an analysis of the randomness of TCP/IP and the impact of PRNG lack of randomness.

This article is a good introduction to how to use this tool on sampling randomness : http://lcamtuf.coredump.cx/oldtcp/tcpseq.html

I also got confirmation some regulations office are using Takens series to see if people are cheating online :)


Complex systems are both resistant to perturbations and unpredictable. A lot of phenomenons are like these: simple in their understanding but made of a lot of elements interacting: weather, the movements of the stars, your heart .... our IT infrastructures.

Takens series can be tweaked in more than one ways :)

Addendum: I used the periodic boundary conditions as a former physicist, because it does not essentially alter the result, and it makes code more readable even if incorrect for 4 points.
Why using 5 offsets? Every time I make a derivation I consume one degree of freedom.
so 3 dimensions + 2 derivations = 5 offsets. As a result it means by playing funnily I can devise as much space phases I have elements in the time series per dimensions minus the order of derivative I want to display.

PS : I forgot to seed the PRNG so that we can "see" the same things. Random data being random, without  seeding then results will differ normally according to the seed.

Perfect unusable code: or how to modelize code and distributivity

So let's speak of what and un/deterministic code really are.

I am gonna prove that you can achieve nearly chaotic series of states with deterministic code \o/

Definitions:

Deterministic: code is deterministic if the same input always yield the same output

Chaotic: a time serie of value is considered chaotic if knowing of sample of t-n samples cannot make you able to predict the t+1 term. 

Turing Machine: a computer that does not worth more than a cassette player.

Complex system: a set of simple deterministic object connected together that can result in non deterministic behavior.

lambda function: stateless functions without internal states.

FSM (finite state machine): a stuff necessary in electronic because time is relativistic (Einstein).

Mapping: a mathematical operation/computer stuff that describes a projection of input discrete dimension A to output discrete dimension B. 

Now let's play real life turing machine.

Imagine I give you an old K7 player with a band of 30 minutes and every minutes I tell the result of n x 3.
If you go at minutes 3 the K7 will tell 9.
If you go at minutes 5 you will hear 15. 

This is the most stupid computer you can have. 
My tape is a program. The index (minutes) is the input, and the output is the what is said. 

So let's do a python Basically we did a mapping from the index on the tape in minutes to integers that yields index(in minutes) x 3. 



So what do we learn with this?

That I can turn code into turing machines, that I can use as a code with a 1:1 relationship, I have a ... mapping \o/

What does compile does?
It evaluates for all the input possible that is an integer belongs to [0:255] all the output possible of boolean function. It is a projection of [2^8] input => 2 output
I projected a discrete space of input to a discrete space of output.

Let's see why it is great

My code is fully deterministic and is threadsafe because my code is stateless.

It is an index of all the 256 solutions for f(x) for every possible values.

if I encode a function that tells if a number can be divided by X another one by Y to have the function that tells if a number can be divided by (X * Y) I just have to apply then & (bitwise and operator) to the int representing the code.

An int is a very cool for a storage of function.
With div2 / div 3 I can by applying all the «common bitwise operator» create a lot of interesting functions:

div2xor3 : a code that indicates number that can be divided by 2 or 3 but not 6
not div2: every even/odd number
div2or3: multiple of 2, 3 and 6
div2and3: multiple of 6 only
....

I can combine the 16 bliter operations to directly obtain functions.

In functional programming you do partial function that you apply in a pipe of execution, here you can directly combine the code at «implementation level»


My evaluation is always taking the same number of cycles, I don't have to worry about worst case, and my code will never suffer from indetermination (neither in execution time nor results). My code is ultimately threadsafe as long as my code storage and my inputs are immutables. 


My function are commutative thus I can distribute them.

div2(div3(val)) == div3(div2(val)) (== div6(val))

=> combining function is a simple and of the code

Why we don't use that in real life

First there is a big problem of size.

To store all the results for all the possible inputs, I have to allocate the cross product of size of input * size of output.

A simple multiplication table by 3 for all the 32 bits integers would be 32 bit * 32 bits = an array of 4billions worlds of 32 bits. 16Gbytes!

Not very efficient.

But if we work on a torus of discrete value, it can work :)

Imagine my FPU is slow and I need cos(x) with an error margin sufficient to only work in 1/256 of radians? I can store my results as an array of precomputed cosinus value expressed in fraction of 256%256 :)

A cache with memoization is also using the same principle.
You replace computing code that is long by a lookup in a table.

It might be a little more evoluted than reading a bit in an integer, but it is globally the same principle.

So actually, that is one of the biggest use of the turing machine: efficient caching of pre computed values.

Another default, is that the mapping make you lose information on what the developer meant.

If you just have the integer representing your code, more than one function can yield the same code. The mapping from the space of the possible function to the space of the solutions is a surjection.

Thus if you have a bug in this code, you cannot revert back to the algorithm and fix it.

if I consider I have not a number of n bit as an input but n input of 1 bit constituting my state input vector,  and the output is my internal state, than I am modeling a node of a parallel computer. This «code» can be wired (few clocks costs) as a muxer that is deterministic in its execution time and dazzling fast.

What is the use of this anyway?

Well, it models deterministic code.

I can generate random code and see how they interact.

The Conway's Game of life is a setup of turing machine interconnected to each other in a massively parallel fashion.

So my next step is to prove I can generate pure random numbers with totally deterministic code.

And I can tell you I can prove the condition for my modified game of life to yield chaotic like results is that the level of similarity for every code on every automaton is low (entropy of patterns is high) AND 50% of the bits are 0/1 in code (maximizing the entropy of the code in ratio of bits).

 

Heavyside function: a systemic mathematical root of social inequity

Abstract 

Just a random theory for fun, nothing really serious.

Assumption

1. I hate analytics, so it will be a formal reasoning;
2. We consider that social inequity is the inequity in front of the differential between tax being paid, and tax being received as n nth order;
3. We consider that the social agents interact has entities formed in a network and that they tend to be over represented the more «utility/wealth» they have (I still don't know of any hobo making it to the parliament);
4. We consider that part of this interaction are with a special entity called «state» that have feedback loops on the agent:
1. some for taking (VAT, IRS ...);
2. some for giving back (education, health...)
3. all these agents are interconnected and may have delay in propagation of the feedbacks;
5. We consider that there is an agent called parliament that can interact with the «state» in such a way it can changes the network and functioning of the agent;
6. We consider that each the utility function for a given agent to set his choices are based on a rationnality that is based on 
1. sum of dis/imitation of a neighbourhood, 
2. global rationnality (the mathematical choice that maximize my utility);
3. and temperature (random factor where you put moral and stuff);
4. temporal rationnality (based on a short term memory);
5. partial access to the information related to utility/state vector of the agent;

By the systemic nature of tax reversation our societies are bound to tend towards extremely inequal society

So basically we have a complex system. A set of simple systems interconnected together. It belongs to a young branch of mathematics called «complex system».

These systems are quite unnice, it is very hard to analyse them mathematically even though some statiscal physics can help. Simulation can help. But reasoning is better.

So what my beef is all about?

The BAD Guy

This is the problem !

This function is a non linear function. If I introduce it in any equation, I cannot use any mathematical means to predict tendancies. Averages, trends, estimations cannot work per nature with these functions. So it means, mostly all predictive models based on «linear algebrae» such as matrix, average, derivate, estimation don't work.

And, I pretend I can solve it.

Juste let's acknowledge that laws have effects.
Let's acknowledge that law is often formulated with stuff such has : IF Income > xk$; THEN pay x% taxes;  ELSE pay y% taxes.

So we have clearly my bad guy hidden every where.

Now, let's be fun and imagine the utility (money) flowing from each of these cellular automata based on the hypothesis there are evenly distributed wealth at the origin and that interaction are randomly distrinuted.
At some turn out of n taxes are paid,
At n turns income can be randomly given based on the discrete state of the automata;
At some turns the automata rules are changed by a subset of the people with more utility.

So the question, is how will it evolve?

Well it is like visualizing a huge body with cells and  heart pumping. Which is nice.


I can predict that if there are heavyside functions used by the «state», then it will evolve more often, and with bigger amplitude towards unfair system than system with linear functions and no binary criterions...

The problem lies in the fact there are «acausal» stuffs in this system. Or retroaction delayed loop. And they tends to amplificate violently.

Acausality means that an effect can have an effect on the cause (but always later in time). Taxing too much people will impact next years potential income. The state wealth is like a gigantic bath tub but globally it requires sum(income) == sum(outcome) and the income are solely taxes (I cheat, I know, I am closing the «state» system whereas it is an open system).

You will notice that the time constant for a feedback loop varies. The Revenue taxes will need one year to retro propagate, while VAT feedbacks almost immediatly. Thus there are asymmetries both in time constant, and amplitudes of the feedbacks.

So know, We hit the run button of the simulation.

We follow agent 1 that is randomely chosen to need money from the state (food stamp? parental break? Sickness?...).Utility increase.

Another agent may lose money coincidentally at the same moment (parking ticket, donation, ...). Utility decrease.

Now, we could imagine it is already the turn for paying your annual income tax.

And, there is this heavyside function tearing appart 2, 1 and the rest into a cluster...

Time in this asynchronuous system, is the accident of the accident.  Every time a transaction is made amongst agents, time increases (discretly).

Randomly things will happens; with the same odd for everyone, unless their utility is null. When utility is null, you can't play outgoing interaction.

Now, 3rd turn, we are already playing the election, 1, 2 are either above or below the utility of the crowd, so their odds of playing the election games are disctinct.

At 0 utility you cannot play the game of election.

I make the following assumption: probability of being elected is represented by a non linear but growing function of the utility (wealth) that is 0 for 0. Given the right utility (if you have money, but no time, you don't have «available wealth» for an outgoing interaction). Rules name : "pas de bras, pas de chocolat".

So in the decision of presenting myself I have to set my decision based:
on my current mathematical interest;
odds of winning;
and my «imitation factors».

Statistically, it is small, and should be considered as the same kind of noise as random photons exciting the oxygen in the sky...

But, let's add a little realistic bias to the agents:
they have a small term memory;
they have all the more chance to predict future that they have education.
In fact, this is too much a strong hypothesis. Let's just say something regulated by the state create an assymmetry of information. I won't treat the case of multiverse rationnality per agent, but it should be treated. You can modelize them as sets of relationship to information some being random (religious interpretation or a star being behind the sun), some being relevant (bribery) plus a set of rules to edict a future outcome based on «values». These have of course a feedback loop from the taxes. These surset of individuals are moral persons, thus almost regular agents (polymorphism), like religion/schools/companies. For each of the surset an indivual is in, the agent has an access to rules and information based on a ratio  of «fit with my own interest according to my memory». And this agent can't be at the parliament, but they can increase the odds of winning for people belonging to their surset.

For the sake of realism, we will consider the lower this fitness variable is, the more an alteration of the information is, so we corrupt randomly either a relationship or a rule.

But, it is way to hard to code, so let's try the simple model that does not change much: a global major education (jacobinism) for the network of agent, and that education is mostly a question of where you live, inclusive or of how much money you have (through both your patrimponial, and indirect income).

The agent still have a short term memory and partial access to the information based on flags describing its cluster.

Well at turn free I have 2 possibles outcome: 2 clusters of 1 and 1 cluster of n - 2, and 1 cluster of 2 plus the other ones.

Not much.

But everytime an event happens with the simple fact there this gaps, it repropagates.

And since we said nothing about the height of this gap, it can make the difference between Charydbe and  Scilla.

Imagine that you go in jail? You cannot earn money, you can't play the game of election.

Imagine thanks to the tax system you have a wonderful contract from the DARPA. You are a cluster of one, but your utility for trying to change the system because of potential bad suprises raises. Who wants to pay taxes when you can rationnaly avoid it with less investment in utility?

Plus the more education you have, the more you share you rationnality with other agents the more you see the retroaction loops and can predict the future (given your rationnalilty favours your agent) and you acknowledge teh utility of sticking together. Karl Max's Capital at my opinion was more useful for the powerful to understand the need to act as a class because they benefit the most of it. I sometimes wonder how much Karl Marx helped the emergence of the capitalism he was strongly denouncing.

And remember, my situation impacts the neighbours on the network (wife, family ...).

Then the more you see the retroaction feedback loop join interest with yours, the more likely you are to adopt interacting with the agent... fast, and spreads the more in amplitude. It is strongly contaminating the more it benefits you.

Every agents have their time of reactions, based on the channel of informations.

Ex: some people knows the Fed's new rate before they are even announced on the market. [find the link with order at 14:00 in NY while announce at 14:00 Chicago]

So ... why does Heavyside make a difference?

This wheel of fortune non linear effects happens also in a system without gaps.

The difference is that if you happen to put a continuous function, the result will results in smoothing the non linear effect after n turn. New comers will come and live with the favored according to a progressive effect.

Their will still be local optimum with linear functions that will make small valleys of clusters. But the depth of the will be smaller. 

The heavyside function will of course clusterize MORE the population with more impacts. Putting a binary flag state for every single steps introducing discrete domains with distinct rationnalities, you try to know best the channel that favours you best while risking less. Some will have interest in changing the laws to favour the conservatism of the situation based on their interests, others will have a rationnality of changing the «winning domains». Just random stuff you could modelize. Without knowing anything you already know that the good rationality will have to favour cluster effects. Because the symmetry in the cause will have an impact in the effect. And it will be all the more efficient that it feedbacks positively. All winning rationalities in an Heavyside based complex system WILL favours strong discriminations that favours the clusters created by the intial Heavyside function. Here is the Capital's central thesis: there is a clear mathematical incentive for the more powerful to regroup together and since they are favoured in their probability of having a positive action on the system for them, to favour clustering for their better good. They should favours laws that works all the society if is (arbitrarily) fractionned by bigger gap.

I don't say every agents in the same conditions share the same rationalities. Warren Buffet or Bill Gates asking to pay more taxes seems to contradict me.

It is just an effect of number. Of imitation, spreading of information, of majority of behaviour, and of cumulative re enforcing effects.

The existence of the bias in the representation/power, favour the systemically the strong clustering of conflicting rationalities artificially. And it is at my opinion very hard to say whether education makes wealth or the opposite.
So saying the favoured clusters in terms of wealth OR education will have a tendency to be over represented in parliament is clearly the right way to say it.

Saying the more represented will favour their interest is kind of a trivial fact.

Rich people without education (no information, just lucky guys (won loto) won't care.

Poor people without education won't care.

Rich (favored by the clustering) and relatively poor people but acknowledging the bias (un favored by the clustering) with education will care to change the system.

Now, if we introduce the fact there is a clash when the tension is too big (we can measure an antagonist rationality between two clusters that is more than a certain amplitude) then it is becoming unstable.

Every agent will tend to try to choose the information node/rule set that will best its interests according to its rationnality.   

But, thanks to the cluster and the nature of the heavyside function and all this binary flags introduced by the heavyside functions, people will punctionate their income through differents paths that requires differents sets of informations.

Thus we have diverging rationnalities. And given enough education, their must be a conflict. If you see you have no chance of filling a gap, you don't try to filll the gap, you just change the gap.  People will mechanically fight other belonging to arbitrary domains.

The funniest conclusion is that in my model, the 99% should be called the 1%, and the 1% should be called the .01%

1% vs .01% is the fight between (have favouring clusters and access to information) vs (don't belong to the more interesting clusters but have access to enough information to see it, or is favoured but has an opposed rationnality).

The simple fact of criticizing the 1% is already a proof you belong to the 1%.

The 99% movement, the occupy wall street stuff is not about trying to solve the inequity problem, it is about asking for a new order because it is a rationnal choice for people that just want to be in the .01% and don't have access to it, yet.

Political disclaimer: I belong to the movement «we should all be the 100% and living happily ever after». The 100% in short.

So now, one big question. Is it intrinsically bad to have a system that is more unstable than it should be overwhise? Is the discrete clustering bad?

Let's rephrase, do you prefer the funkyness of war, or the boringness of happyness and peace? Well it depends of course if you have to die at war or earn money from it.

A system that induces systematically arbitrary clusters of population that amplifies have less chance to be stable than a system without clustering.

In natural language; a society were rules are applied without any discrimination on the nature of the citizen is less likely to tend towards unstability and strong auto amplifying discriminations.  These discriminations are purely mathematical amplified artefacts. Should we let artefacts rule our lives?

It is is kind of better when in a society people share the same rationality, and there is less paranoïa when the information is more symmetric.

Our systems are thus chaotic by nature, and more stochastically behaviouring than they should, just because of a stupid function that introduces an arbitrary amplification on discrimination. It should be fixed. The laws should be rewritten to get rid of the all the possible formulation like: IF BLah THEN this ELSE that.

I am agreeing strongly on the importance of sanctioning wrong behaviours or protecting the youngest (which are strong heavyside function), I don't agree with the multiplication of unnecessary non linear clauses (IF SEX | EARN more than x$.... THEN ....) in our social systems. They cluster us, and they make the effect of the law unpredictable thus arbitrary. And as a human, I prefer control.

How could I prove I am right/wrong?

Well, if I were serious I would bring proof. So I would have to make a simulation, give data, and make a model. Than I would claim to the world that I am an unrecognized genius, but I don't care. I am just waiting for my wife to come back, and it is my way of relieving the stress.


However, I gave a try at multi agent simulation. https://github.com/jul/KISSMyAgent
It could be used to modelise this. And, I am pretty sure by running a lot of simulation we will find the properties of our whole known systems (democratic, republicans, communists, monarchists) will be prone to this effect.

But I hated the programmation of this stuff. So I don't recommend it.

I went on an implementation based on distributed agent: https://github.com/jul/dsat

I began to use it in conjunction with graphite/carbon to store results. But, it is faster to run the simulations in my head than on the computer, so I prefer to go directly to the results. ;)

So there it was, a recreational theory that probably is useless, but it was in my brain. So I unloaded it. 

Just for fun, I just described a purely asynchronuous distributed system.
It means, that with too much non linear interactions, any real distributed systems (the cloud, big clusters of distributed applications) also have this unstability properties. 

Just think about it: I am saying that the cloud will be unstable one day by nature, I am saying the day it will break it will break in a massive violent snowball effects the more non linear rules are introduced (non linear: swithching traffic from interface, rejecting jobs on timeout, according more resources to tasks that are already greedy on CPU instead of fixing the algo...). And since the effect is non linear we have no assessment possible of when and how. I have a strong suspicion the breakout will be violent and undetectable. One day, you will wake up with an irreversible situation that will affect you without any possibility to foretell it.  Thus, no insurance can cover this phenomenon. No science... yet. We don't have mature analytical, theoretical and empirical tools to studies these. 

I would be you, I would not rely on systems that are chaotic and built by engineers that don't seem to see any problem with that. You just are having a system that is stable as long as a given piece of network equipment in China doesn't flap its small BGP wings too much but oddly resists to people trying to destroy its backbone with nukes....

I just hope it does not happen before I am retired. ;) On the other hand, I am just a single guy without any credibility, and I seem to be a little to dramatic. So, let's say it is just another stupid theory with no interest.

DevOps are doomed to fail: you never scale NP problems

We live in a wonderful world: all new technologies have proven that old wisdom about avoiding NP problems was stupid.

The Travelling salesman problem? (which is not NP, I know)
Well, can't google map give you wonderful optimized routes?

And K-SAT?
What is K-sat by the way?

SAT problem is the first problem to be known as NP. (wp, youhou)

What does NP mean in computer science nowadays, that can translate in word devops/business can understand?

It cannot scale by nature. 

Most devs reason as if we can always add CPU, bandwidth, memory to a computer.

The truth is the world is bounded. At least by one thing called money.

So here is what I am gonna do:
- first try to help you understand the relation ship between KSAT and dependency resolution;
- then we are gonna try to see roughly what are the underlying hidden problems;
- I am gonna tell you how we cheated so far;
- then we will show that the nature of the problem is predictably in contradiction with accepted actual business practices.

Solving the problem of knowing which package and in which order to install them given their dependency is NP complete. 

The more correct way to explain this homeomorphism is here.

So: K-SAT is about the generic problem of solving boolean equation with k-parameters where some parameters maybe in fact an expression of other parameters (solution of an another equation) (that are the cycles I will talk about later).

After all, boolean are the heart of a computer, it should be easy.

Seems easy as long as the equation is a tree. And aren't all our languages based on the parsing of an AST? Don't they work? So we could write a language for it.


Well, no. Computer manipulate data. A register does not tell you what the data is. Is it one variable of my equation, its name, its value, its relation with other adresses...?

The hard stuff in computer science is to make sense of data: to make it become information by handling the context.

Installing a package on a computer is in fact building a huge graph (40k nodes on debian) and when a package is to be installed you begin by asking the first equation
Ready_to_install = Union(dependencies == satisfied)
if false then we go to the dependency solving stage

For each dependency listed in the dependency (to the nth order)
build a list of package not installed that should be required.

Plan installation of this package with the actual solutions chosen (there may be more than one way to solve your dependency, so the equation as not one but potentially N solutions).

So ... you have to evaluate them ... recursively (because parameters are solution of other equations)... then stack them ... sometimes the solution is not good, so you backtrack to another solution, modify the stack ... and sol long.

And it's over?

Bof, not really.

What if package A is installed and package B requires A+1 and A & A+1 are mutually exclusive?  (small cycle ex: centos6.4 git requiers git-perl and git-perl requires git)
What if package B requires A, C , D. C requires E, E requires F and G, G requires B? This is a circular dependency or a cyclic graph.
In which order to install the package so that after every step all software still works? (I don't have the right to wipe software installed to solve a version dependency).

Where is the hic?

Variable subtitution can make the boolean equation impossible.

ex: A & B = True given A what is the value of B? easy True

The given equation is the desired state of the system package A and B should be installed.

A is True because package A is installed.

What if B = ~A ?

The equation is not solvable. Trivial case that normally don't happen.

What if B expressed requires C, D and D requires N and N is exclusive of A?
(Example A == apache, N == nginx and the software B requires nginx on 0.0.0.0:80).

Testing for cycle is easy given K determinated vertex. Finding how to check all the possibilities given all the N set of I partial solutions is quite more complex.

This is known as the DLL Hell!

That is called software requirements (see ITIL that makes a lot of fuss on this).

We already are facing small problems, but nothing that really matters. We have not talked about how we cheat, and why some are heading for a disaster.

Why do computer engineers avoid NP problems by the way?

The universe is bounded.

The data structure needed to solve the resolution dependency is a graph.

The edge are the packages (variables).
The vertex are the logical expression of software requirements (A.version > B.version)

So  before talking of algorithm just one basic:
in worst case, when you add a node to a graph with n nodes you add at least n-1 vertex.

Thus the number of total relations has grown more than linearly.

You still have to store the information ... in memory (for the work to be done fast).

Then, you have to detect the cyclic references. The first order are easy.

But not always. There are ambiguity in the vertices. A requiers B.version>1.1
and C requires B.version < 2.2 may conflict if B is only available in version 1.0 and 3.0. ... so ... there is much more than what the eyes can see :)

And cycle can be bigger than the usual classical 2 exclusive packages.

But that is not all.

The algorithmic normal way to solve the equation is to create the graph. And do the systemic evaluation of the cases.

The time of computing grows in worst case explosively.

But we are not in worst case: with my «blabla» OS it takes me 3s with 4k package to install and 3s with 41k packages installed

Well, we cheat.

One part of the cheat is not going for the exact solution but given known property of real world packages KSAT solvers are optimized.

We cheat even more by relying on human beings.

Maintainers in most distributions are doing an excellent job at testing, and fixing the bugs the OS users report and make very minimal dependency.
We are in a special case where the vertex are not very dense.

The algorithm seems to scale. But ... it can't... since we are changing the domain of validity of the KSAT solver we use. Optimization that relies on : sparse connections//few requirements per software.

DevOps problematic is not ONE computer. It is a set of computers with different Operating Systems. And in house developers that ignore what packaging is all about.

So you don't have one set of equations to solve your dependencies, you have n sets. And now, the requirements may link to other sets of equations :
exemple My python program on server X requires nginx on the front end Y.  

OOps, I don't have a graph of 40k nodes anymore, but 800k nodes now.
Do you want to compute the number of potential vertex with me? No. It is huge.

My sets of depencies has grown a lot. My input data in my algo have grown exponentially, so will my CPU time needed to solve the new problem.

if your apt-get install apache is 3 seconds on your ubuntu, your chef deployment will take you 3 minutes.

And, in real life, there are still people installing software from the sources without using a package manager (if that was not complex enough).

So your data are possibly not even accurate.

To sum up:
We are tending to :
- multiply the number of edges more than linearly;
- increase the number of vertices more than linearly
and feed that to an algorithm that takes exponentially more time given more input in the worst case and we tend to move towards the worst case.

The time and complexity is increasing very much.

Why old wisdom matters!

“I tend to think the drawbacks of dynamic linking outweigh the advantages for many (most?) applications.” — John Carmack

The fashion for android and OSX is to prefer statically build application.  It diminishes the vertex in the graph a lot.  It diminishes the software requirements.... on the front.

But smartphones and tablets are CPU/IO/battery bound very much, so we deport more and more computing in a distributed system called the cloud.

And let's zoom on the cloud system requirements.

Since we exploded the resources available on one computer we are replacing in cache memory available to more than one threads to distributed in memory cache (memcached, mongo, redis...). We are adding software requirements. We are straffing/caching/backuping data everywhere at all levels.

Since we can't serve the application on one server anymore we create cross dependencies to higher the SLA

Ex: adding a dependency on HAproxy for web applications.

For the SLA.

So your standalone computer needs no 99.9% SLA when it is shut down.

But now, since we don't know when you are gonna use it, where you are, we have to increase the backend's SLA.  

By the way, SLA adds up.

My CDN is 99.9%
My heroku is 99.9%
Our's ISP is 99.9%
so my SLA is know ...between 99.9% and 99.3% yep, you forgot to add the necessary links between your CDN and heroku, and your customers ...

You need a 99.9% SLA. It is cool, it is your upper bound.

But you build a growing uncertainty for the worst case.

Or you could expect more SLA from your provider.

What is the SLA beast?

Service Level Agreement. The availability of a service over a given time on average.

99% SLA over one year ~= 3.65 days down.

Would you use still google/fb/twitter/whatever if it was down 4 day per year?

If you have a business 1% off on a critical service (like mail) you have 1% gross income less.

So ... our modern distributed technologies are aiming at 99.999%

Mathematically SLA is thus a decreasing function

And they are de facto based on increased requirements. They rely on an algorithm that is NP complete.

Mathematically resolution dependency is an exponentially time consuming function. And you are feeding more than linearly growing input.

So ....

Mathematically they are bound to intersect.

Just for memory: chef recommends 30 min per run // the equivalent of apt-get install on your computer that takes 3 to 45seconds.

These are

Availability per day per     month         per year
99.999%         00:00:00.4 00:00:26 00:05:15
99.99%         00:00:08 00:04:22 00:52:35
99.9%         00:01:26 00:43:49 08:45:56
99%         00:14:23 07:18:17 87:39:29

So, well... imagine a distributed deployment did happened bad, what do you think of the SLA?
And, do you trust people who says they never made any mistakes?

I don't say the days are near where this NP complete aspect of software deployment will bite us.
I say these days exist.
I say the non linear nature of the problem makes it impossible to predict when.
I say the phenomenon will be very abrupt due to nature of the phenomenon.
I say we are pushing towards choices that will create the problem.
I say business analysts, companies, CTO will not see it coming.

And that is my last point:

Our scientific education makes us blind to non linear problems

The first words of your scientific teachers that you have forgotten before teaching you science/math was: «most problems are not linear, but we only study these one because there are the only one for which we can make easily accurate predictions»

If you have a linear system you can predict, plan ... and make money. Without well, you are playing the lottery.


What are non linear stuff ?
- weather (weather forecast after 24 hours is still a scam even though our computers can crush even more data since 40 years);- actuariat/finance: selling products based on the probability connected problem will happen ; 
- resource consumption (coal, oil, fish, cows);
- biodiversity;
- cryptography (you search for symmetrical operations with non symmetrical CPU cost)
- floating point behaviour (a operator b != b operator a is not always true)
- economy;
- coupled moving systems in classical physics (randomness can be obtained easily with predictable system if you couple them correctly);
- quantum mechanics (it bounds the max frequency of the CPU);
- the movements of the planets (you can send me your exact solutions for where the moon will be relatively to the sun in one year (length) relatively to a referential made of 3 distant stars).
- internet bandwidth when bought to a tiers one;
- real life, sociology, politics, group dynamics .... 

You see a common point there?

We still have not solved these problems, and we do not learn how to solve them in our regular curriculum.

I don't say there is no solutions.
I say there is no solution. Yet. We will never find the solutions if we don't get aware of the problem.
Non linear problems are not a computer problem. They are an intellectual problem that requires proper thinking.
It requires education.

We are pretending to live under the empire of necessity, but there is no necessity to accept this reign.

We try to build a new world with the wrong tools because we are making the false assumption we can handle the problem we face with the methods we learned at school. We rely on the «giant's shoulder» to make the good tools. But, since we are not well educated, we invest money on the wrong tools for our problem. Tools often made by the right guys for often no actual problem.


Firstly, we should slow down our adoption of async/distributed systems;
Secondly, we should lower the SLA to reasonnable levels. If 2% of a service interruption in one of your production can kill you, your business is not reliable;
Lastly, we should understand how the more our systems is efficient the more fragile it is becoming.
It maybe the time to trade efficiency for durability. It maybe the time to slow down and enjoy all the progress we made.

Having fun and making fun with game of life.

Summary of the previous episode

In the previous episode we made a simple game of life called GoF because I am dyslexic and Game Of Life became Game Of liFe. The purpose of the exercise was to demonstrate that an abstraction ought not to be complicated but ought to dissociate the intuitive way to use the code and its implementation. Now, our new mission, is even funnier: it is to show how a simple toy program can teach us serious things.

Introducing the game of life console 

I have made a small tutorial here : http://gof.readthedocs.org/en/latest/quickstart.html

My game of life implementation is deliberately faulty in its implementation, is a little bit of a troll, but it is has an amazing power to illustrate some key concepts of developing (I prefer factorizing):

• it is an introduction to non linear algebra a field in which computer analysis is a must;
• it is a massively parallel model hence a way of thinking problems in order to defeat concurrency problems;
• it is a very simple way to begin manipulating python;
• there are some smart tricks based on abstractions; 
• it is an introduction to discrete cellular automata / multi agent simulations.

The troll in the code

I am not an Object Oriented developer. I am an old old developer coming from the old time, we use to say : «show me your code, and I shall be mystified, show me your data, and I know how your code really works». Since OOP and encapsulation has been massively adopted, data and code are mixed up in the same files. As a result, it has become impossible to tell code from data.

My code is old fashioned : data on one side (the matrix), and functions on the other side (evolve, bleach, dirty). But, is not.

If you type :

matrix.play = evolve
matrix.reset = bleach
matrix.random_fill = dirty

grid.reset(15,20)
grid.random_fill(10)
grid.play(200,3)

Then, now all the tutorial can be rewritten in a plain OOP fashion. So, the troll in my code is about stating that coding is not about using a paradigm, it is about making code that works, and that OOP and imperative programming can be equivalent.

Since I miss the separation of data and code, I do advocate separating data and behaviour in distinct files and that is why I love python dynamic typing but you could also use inheritance to achieve the same result. One illustration of this principle is archery that use traits (mixins) to give behaviours to inert objects (Mutable Mappings in this case).

I deliberately left a mistake in my code to illustrate my point: my Game Of Life's implementation cannot be used for a generic 2D cellular automaton networks because I left a method for counting living neighbors that is specific to Conway's game of life. I intend to use it make a point later if I have the time to develop on cellular automata, and on the proper separation of methods in an object.

Readying the path for some analysis

Imagine you want to make an histogram of the number of cells that are ALIVE after 0, 50, 100, 200 iterations. For the sake of fun, I use gof.weird_array.SparseArray. Hence you just have to count the number of items in the set to count the living cells this way:

import matplotlib.pyplot as plt
from gof.matrix import matrix 
from archery.bow import Daikyu
from archery.barrack import bowyer
from gof.gof import dirty, bleach, evolve
from gof.weird_array import SparseArray
from json import dump
result= Daikyu({})

for _try in range(100):
    ### {0}^{0} is more friendly thant the boring set()
    grid = matrix(20, 16, SparseArray({0}^{0}))
    dirty(grid, 10)
    result+= bowyer(Daikyu, {0: {len(grid.matrix._set): 1 }})
    evolve(grid, 50, 'unseeable')
    result+= bowyer(Daikyu, {50: {len(grid.matrix._set): 1 }})
    evolve(grid, 50, 'unseeable')
    result+= bowyer(Daikyu, {100: {len(grid.matrix._set): 1 }})
    evolve(grid, 100, 'unseeable')
    result+= bowyer(Daikyu, {200: {len(grid.matrix._set): 1 }}) 

fig = plt.figure()
for i, label in enumerate([0, 50, 100, 200]):    
    ax = fig.add_subplot( len(result), 1, i+1)
    if not i:
        ax.set_title("Number of living cells for 100 random configurations")
    p = None
    x,y=[],[]
    for k,v in sorted(result[label].iteritems()):
        x+= [k]
        y+= [v]
    ax.plot(x, y, label="%d iterations" % label)
    ax.legend()

plt.savefig("histo.png")

And Tada o/

What is so special about these plots ?

1. there is no nice distribution of the number of the accessible configurations after initial  time  (gaussian or any other distributions);
2. the configurations that were pretty homogeneous in terms of 0/1 are now more spread (the entropy of each initial patterns decreases, but the result are less homogeneous in terms of 0/1 ratio than the initial patterns)  ;
3. the number of configurations increases, and then decreases : we have a transition! 

At iteration 200, patterns should be converging to their  attraction basin. With a network of simple systems interacting with each other, you have a complex system. These rules being non linear, they cannot be addressed with linear tools (matrices, Fourier...). It is thus quite hard to predict their behaviors.

If you have the audacity to speak French ;) you can read this : http://www.lps.ens.fr/~weisbuch/cha2/02.html

Now you have a lot of challenge to solve :

• is there a domain in which the system is chaotic (given a distance of 1 for two distinct patterns, how does final distance evolve?);
• Are there more chaotic rules than Conway's?
• If we change the actual neighborhood for a random neighborhood how does the system change? 
• how many stable attractors exists, what are they size? 
• how many precursors exists for a basin, how these are distributed?
• if we consider the grid as a vector of 1/0, then it is a number. Can we construct a chaotic enough cellular automata that would make a good cryptographic hashing function (hint : rule30) ?

What about GPU?

Another cellular automata that is fun is the lattice gas automaton. And it is suited for GPU : Data-Parallelism and GPUs for Lattice Gas Fluid Simulations Since the same causes produces the same effects, most of the cellular automata networks will be easily implemented on GPU.

 

And what about Finance? 

I have found G. Weisbuch works inspiring :  hits and flops dynamics by G. Weisbuch. Financial phenomenon are pretty much based on a lot of agent with their own rationalities, some global beliefs and a neighbourhood. It seems very tempting to use a cellular automata to model financial phenomenon (which seems non linear).

Plus cellular automata are pretty easy to code, easy to parallelize with CUDA. So maybe we can do fun things. At least I tried with a very ugly first code in python of a multi agent simulation with a fanciful utility : http://wiki.github.com/jul/KISSMyAgen

And now?

Well, I hope you enjoyed, that's all.

PS Special thanks  to Alejandro Weinstein, Bmispelon for the corrections...