My last two blogs were about the Conway’s Game of Life [1][2]. Actually this game belongs to a broader set of models, that are called Cellular Automata. All of them follow the same idea of applying simple rules according to the current state of the cell and its neighbours.  A simple modification as changing any of the 4 rules of the game of live or taking into account second order (Figure 1) neighbours will produce very distinct patterns in the game.

However, the Game of Life is a quite sophisticated cellular automaton compared with the simplest version of them. The Game of Life is actually a 2-dimensional and, yes, there are 3-dimensional version of it. But I am looking for more simplicity and there are 1-dimensional automata (Figure 2). Again, we have “live” and “death” individuals and a few rules to decide the next state.

The way we are going to define rules in this scenario is slightly different. We are just going to use two neighbours and the current state of the cell itself to stablish the state in the next iteration. We can represent this with 3 values indicating the actual state of the neighbours and the current cell: left neighbour – current cell – right neighbour. We are going to use symbol 0 for death and symbol 1 for alive. For example, 111 means that both neighbours and the current cell are alive. When 111 happens, we have to decide whether the next state would be 0 or 1 (Figure 3.).

There exactly 8 possible combinations of 0s and 1s with three values. If we define 111,110,101,100,011,010,001,000 as a universal order for this kind of cellular automaton, then we just have to define 8 values that indicate the next state of the center cell. For example, in the Figure 3. the values would be 00011110. Yes, that is a binary number that could be represented in decimal system as 30. So the rule of Figure 3. is Rule 00011110 or Rule 30. Just remember we accept the universal order of 111,110,101,100,011,010,001,000.

Take a few seconds to re read the previous two paragraph. It may seem very complicated but it isn’t. You just have to remember that the state of each cell in the next iteration is going to be the result of the two nearest neighbours and the cell itself. Just to be sure, Figure 4. gives and example. First row is the current iteration and second row the next iteration. Use the Figure 3. to check everything is fine. You can practice calculating the next “next generation”. When you are on the leftest cell you can use as the left neighbour the rightest cell (like a ring).

Ok, so what? Let’s say you continue doing this with a bigger 1-dimensional array (instead of just 10 cells per iteration, use 1000 or more). At the end you are going to have something like the Figure 5. You may see a pattern but actually there is no way of complete generalization, welcome to chaos! It is true, there are parts that have order and even cycles (I like to think the live on Earth as one of that ordered universal instants) but in general is unpredictable. Actually Wolfram proposed a computer random generator (more properly say  pseudorandom number generator) with it.

Going back to Figure 3., all we need is 8 1s and 0s  to define a rule. There are exactly 256 different rules (actually just 128 because the other 128 are a negative mirror of the first 128, black would be white and white black). Not all of them produces this kind of crazy patterns (another good example is Rule 90 in Figure 6.).

Some of them produce no patterns at all. Think about Rule 0 (Rule 00000000), everything is going to die in one iteration. Others produces some kind of cycles or more order structures like Rule 184 (Figure 7.) used to model traffic flow in a single line of a road.

Well, you may say. This very artificial, simplistic and unrealistic. Take a look the Figure 8 and compare it to Rule 30 in Figure 5.

You may said it is a coincidence and it just looks like. Maybe, but the probabilities of Rule 30 appear in nature is very high so the coincidence is the rule appearing and not the whole pattern out of the blue. Just think how the growth of a shell is done.  The conclusions are the same of my previous post:

1. Initial setting is very important
2. Complexity can emerge from simplicity
3. Chaos is not randomness
Thanks Wikipedia to for the pictures.

15 days I wrote the blog “yet another blog about the “Conway’s Game of Life” . My purpose was convincing you that very simple individual rules could produce group patterns. This patterns emerge from the individuals interacting with their environment and nothing else.

I promised I was letting the best for today. So here it is. You probable were wondering how complex this group patterns could get with the right positioning. Actually what I showed in the previous blog were just the most basic and well known examples.  There are much more complex things. Take a look at the next youtube video, but start it at minute 1:10, since you don’t need explanations about the game of life anymore.

That is very cool but there is more. Some very simple patterns can produce very unstable sequences (chaotic) structures. You can go here and click on run. It takes 5206 to converge (Here is a list of other long-lived patterns that you may want to try). Of course you can also randomize the canvas and wait. It could easily happen that you stare at your screen for a few days, weeks. What to say? The universe is still here in a constant accumulation of simple interaction of small particles.  Even in a simple game like this would be almost (just giving a benefit of doubt) impossible to predict the final stage, and we are starting just five individuals.

You may say, simply run the game and then you have your prediction. First, is that really a prediction? Second, there is a practical problem if you want to apply that to, say, the universe. You need another one to simulate it (and a faster one so you can use the prediction). There is another solution. Simplify the individuals. Instead of simulating a whole human being, just grab the main characteristic of his behaviour and you may learn something of the factors you picked it up. This is the theoretical background of my thesis and I will be talking about this in many different ways.

But let’s go back to the “Conway’s Game of Life” to stress two important things:

1. Actually the “Conway’s Game of Life” is a more complicated version of something even more simple that produce complex patterns. It is just another example of a Cellular Automata. Don’t worry, my next blog is going to be about it. For now, I am just going to add that the “Conway’s Game of Life” is a 2 dimensional games. The simplest cellular automata has just 1 dimension, and still produces chaos
2. The “Conway’s Game of Life” has the same computational power as a universal Turing machine.  I don’t know if I will be talking about the Turing machine at some but, for now, just consider that this game is “as powerful as any computer with unlimited memory and no time constraints: it is Turing complete”[1].

Three important conclusions so far:

1. The initial conditions (patterns) determine dramatically the ending result.
2. Chaos could come me from very simple conditions. That is to say, you don’t need complicated models to get interesting environments. You are going to find head aching problems even in the restrictive and conditioned environment of math.
3. The predictability inside chaos is still possible. You just need another universe :D. Here, I am very satisfied and assert that chaos is different randomness. You cannot predict the latest. The question, still open in the science, is “does randomness exist at all?”

Next entry: Cellular Automata

Around 1970,  John Horton Conway created a fascinating game called “Life” [1].  The reason for the name is going to be quite obvious as I quote the rules of the game. Before that just imagine a large white checkboard (the world where ‘Life’ happens) and a plentiful supply of counters (the creatures that plays ‘Life’). Counters could be simple ‘poker chips’. See Figure 1. to be clear.

So, how to play? In fact you (or the computer) just have to follow three rules. “Conways genetic laws are delightfully simple. First note that each cell of the checkerboard (assumed to be an infinite plane) has eight neighboring cells, four adjacent orthogonally, four adjacent diagonally. The rules are:

1. Survivals. Every counter with two or three neighboring counters survives for the next generation.
2. Deaths. Each counter with four or more neighbors dies (is removed) from overpopulation. Every counter with one neighbor or none dies from isolation.
3. Births. Each empty cell adjacent to exactly three neighbors–no more, no fewer–is a birth cell. A counter is placed on it at the next move.” [1]
So the game is fairly simple and seems boring. But take a look at Table 1. Those are 10 different examples of possible words. As you can see, several group behaviours are produced with the same three Conway’s rules. The only thing that has change in each world is the initial configuration of the game. Thing of each column as small society. The first column would be examples of societies that never change (‘classic’). The second column would be cyclic societies (I would say mesoamerica is a good example or the oscillation between republicans and democrats). The third column, well, that is for sure a nomadic group.

Table 1. The table presents three kinds of examples. First column is about still lives, the world is not going to change and it doesn’t matter how many times you apply the rules. The second column is about oscillators, this worlds produces cycles of  2 or 3 periods following the same rule. The third one is about spaceships, the individuals “move”  through the grid indefinitely. (Source: Wikipedia [2])

Still lifes
Block
Beehive
Loaf
Boat
Oscillators
Beacon (period 2)
Pulsar (period 3)
Spaceships
Glider
Lightweight spaceship (LWSS)
Remember, this doesn’t have a top down construction. This is build from each individual rules. It doesn’t matter that it seems a very coordinated and dictatorial group behaviour. Each cell has its own behaviour and there is no centred government. Don’t trust me? try it in a piece of paper, it is going to be just as little less boring than a Sudoku.
There is more, but this blog is already large and I feel like keeping the best part for the next post. But before going, enjoy the little example in the Figure 2. What could it be? Two little societies in a battle?

[1] Gardner, Martin (1970-10). Mathematical Games – The fantastic combinations of John Conway’ new solitaire game “life”223. pp. 120–123. ISBN 0-89454-001-7. Archived fromthe original on 2009-06-03. Retrieved 2011-06-26.

Ok. Digital Humanities. Everybody is talking about it, so am I right now. But this talking talking is not Digital Humanities (DH). The discussion about DH is not DH. The definition of DH is not DH. This post is not DH. Yep, it doesn’t matter it is on the tweeter, facebook or blogs. The problem is that everybody is giving an opinion, and opinion over opinions, and then I don’t really know what is people talking about.

So, what is this DH about? Does it makes sense? It seems is something related with humanities and digital. Humanities includes a lot of other areas and the term digital is already corrupted. Originally the term “digital” is related with discrete values in contrast with “analog” (continues values).  A discrete system is for example the binary. Other discrete system is the alphabet, which is used to write novels, which are studied by the area of literature that belongs to humanities. Therefore wasn’t the literature already digital?

I guess they mean something else with digital here. It seems to be more related with either Internet or computing. In the first case, Internet, I agree that there are new forms of expressions (Orsai or Balada/Track) that deserve being studied separately because they include new elements to the “traditional” literature. Before the Internet, those elements didn’t exist. Other examples are studying the behaviour of people in social networks or analysing the work of graphic designers. I agree that they are new forms of expressions that need theories that have to be developed. But not all out there is new. Most of the change that we are seeing nowadays is because of there is much more information that could be studied. From independent movies or books to interactions between individuals.

This take me to the second case, computing. Specially processing lots of information. Here, the possibilities are huge. Not just to study the new forms of expressions but also the old ones. For example, processing a whole collection of the Spanish golden age period. However, things here are also not necessarily that new. For example, computational linguistics has been there for a while. Note the use of more specific name. It requires a big deal of linguistics, statistics and computer sciences. And yep, it is claimed to be part of DH.

There are clearly two big areas here. And, each one, contains also big areas.  A criticism of digital graphic design should be way different of that girl who is dealing with understanding Orsai. What about computer linguistics and artificial societies (simulation of social interaction)? Is digital humanities all of this? Seems a bit too much. I think it would make more sense to start (1) listing all the new forms of expression and (2) study which new tools are being applied to the already existing areas of humanities. DH is just an umbrella for all this but I cannot think in a curriculum for all of that…

Anyway, this is just me increasing the bubble of Digital Humanities… talking talking…

The last week I was in the Latinamerican Conference in Informatics. Three to five were running at the same time. It was an overwhelming schedule that serve more as a restaurant menu. Papers from history of computer science to  biological computing. However, the best part of the event was listening to John E. Hopcroft  in his tutorial “Mathematics for the Information Era” and his conference “New directions in computer science”.

Both of them were related with the constantly increasing and, since long time ago already, intractable amount of information available to us. We generate an amount of information equivalent to a couple of hundreds newspapers per day per person. Of course that include junk and data generated by computers themselves. Still, information should be useful to us, unless we are just trying to create the biggest museum of the world (called Internet) receiving visits just to take pictures.

But there is nothing new in what I just said. What is new is the summary that Hopcroft manage to put together. He gave sort of the set of the “new” mathematical tools that we had to attack the problem of Big Information. Here is the list that I can extract from my notebook and a very brief explanation (forgive if I am not precise as him or if I misunderstood any of the concepts):

High dimensionality: things in many dimensions doesn’t behave as things in 1,2, 3 or even 4 dimensions. There is a new set of theories that are being developing in this area increasing our understanding of how complex problems (with many dimensions, such as texts) may work. Some of the next topics are related with high dimensionality. This is more like a new whole area of study.

Volumes: in many dimensions volumes does not behave as we expect. For example, as dimensions tent to infinite, the volume of the sphere (or hypersphere) goes to zero. For the Gaussian surface things are even more unexpected. It looks like a ring. For that reason, its consequences are totally nuts. Let say you have two Gaussians  that generated points in a high dimensional space. Then you can deduce which of the Gaussian generate each point (with extremely good accuracy).

Dimension reduction: if you have some vectors in a (very) high dimensional space, you can decrease the numbers of dimensions and still distinguish between them (very different when you reduce from 3 dimension to 2 dimiensions).

SVM: One of the breakthrough in machine learning (and Artificial Intelligence, unfortunately he didn’t have more time to continue on this topic). This could be seen opposed as the previous one. This is, the possibility of increase the number of dimensions of the vectors so it is to classify (learn) quicker the solutions of problems. For example, try to draw a straight line that separates the “x” from “+”.

x + x x  ++++  x x + x

Now, the mathematical magic come and increase the dimensions. Now, try again!

+         ++++         +

x     x x              x x     x

Of course, it is not as simply at that, there is a lot hidden in the mathematical magic part. It is important to notice that computers are better learning single lines than curves.

Sparse Vectors: in nature, if you have a huge vector representing, say a genome, most of the values (gens) are 0. Even more, the sparse solution is unique. This is why geneticists are able to crack out ADN. This also reminds me that in nature, interactions of 3 factors (or more) are rare. This is great for statistics in which we look for low interactions or no interactions (independent variables).

Probability and statistics: no need to explain what is this. But most of the big advances in the areas that are producing big information is going to require more than means and standard deviations. It took almost a year to generate enough collitions and, just then, be able to confirm the Gibbs Bosson with 5 sigmas, a statisc.

On the infinite and beyond:  well, basically calculus. A good understanding of certain concepts such as limits, derivatives, singularities.

Others: Markov chains (random walks), generative models for producing graphs (richer gets richer concept), giant components, ranking and voting (and its problems), boosting, zero knowledge proof, sampling (accepting you cannot store or process all the information, how can you sample to get the right answer?)

In general the good news is that if you have huge information and you lose some, you are still able to find all the answers because the structure and properties doesn’t change. This reminds me “The library of Babel” of Jorge Luis Borges.

Hopcroft points out seven problems in the new directions of computer science:

1. Track ideas in scientific literature (a machine who tells you the key articles of a particular topic)
2. Evolution of communities in social networks
3. Extract information from unstructured data sources}
4. Processing massive data sets and streams
5. Detecting signals from noise
6. Dealing with high dimensional data
7. Much more application oriented…

It sounds a bit like Cultureplex, doesn’t it?

“The information age is a fundamental revolution that is changing all aspects of our lives. Those individuals, institutions and nations who recognize this change and position themselves for the future will benefit enormously” John E. Hopcroft.