# Stephen Smith's Blog

Musings on Machine Learning…

with one comment

# Introduction

Last time we looked at a simple physical dynamical system namely Taylor Couette Fluid Flow, where a very simple experiment led to more and more complicated solutions as a parameter was varied, namely the speed of the inner cylinder. In this article we are going to look at an example from Mathematics and an example from Computer Science. What we are interested in is how very complicated behaviour results from very simply stated problems. We are looking into insights in how something as complicated as human intelligence can result from the simple behaviour of billions of our neural cells. Or for that matter can we have intelligence arise from the simple behaviour of billions of logic gates in a modern computer? The amazing thing is that as we study nature we see this phenomena more and more, whether it’s fractals appearing in nature or the chaotic behaviour of ecological systems. It turns out that much of the richness and complexity of our environment can result from a few very simple rules.

# The Mandelbrot Set

Everyone has seen fantastic images of the Mandelbrot Set. Such as:

Or a zoom in:

To see more detail along with more fabulous graphics, have a look at the WikiPedia article here.

The definition of the Mandelbrot Set is remarkably simple. It is the set of complex numbers c such that the quadratic map

Zn+1 = Zn^2 + c

converges. In the graphics black represents the convergent points, and then the colors are specified by how fast a point diverges. The Mandelbrot Set is a fractal, meaning that as you zoom in on it you see the same structures recurring at all magnifications. The key point is that we get this infinite complexity out of such a simple defining equation. We are used to simple formulas like quadratics leading to simple predictable behaviour like parabolas. However once you start iterating simple behaviours you start getting this amazingly rich complexity appearing.

# The Game of Life

Another well known example of complex behaviour from very simple rules is John Conway’s Game of Life. The definition of the game is quite simple, so I’ll just quote the WikiPedia entry:

“The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead, or “populated” or “unpopulated”. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations.”

For lots of examples and images have a look at the full WikiPedia article here. Below is a gif showing a set pattern spawning gliders that fly off diagonally:

Some games just die out, others are extremely chaotic. Some people tried to “solve” the Game of Life, ie given an initial condition have a formula that predicts what will happen without having to run the full simulation. But is was shown that you can actually create an Universal Turing Machine in the game and hence solving this is equivalent to the Halting Problem and hence is impossible.

# Summary

The Mandelbrot Set is one example of many where a very simple problem statement leads to infinitely complex solutions. The Game of Life shows how another simple statement leads to extremely complex and unpredictable behaviour. Further since you can create a Universal Turing Machine in the Game of Life, Turing’s Completeness theorem shows you could solve any problem computation using the Game of Life. This partly shows how Turing’s work is so influential and how so many things that we may not think of a computers, are in fact equivalent to computers.

Our brain consists of billions of neurons that have very simple rules that then get applied over and over in an iterative manner, so as we’ve seen this will lead to very complicated, rich and stable patterns emerging. Our thesis then is that this is the foundation of intelligence.

Written by smist08

June 2, 2017 at 6:27 pm