Finding The Mona Lisa In Life
Written by Mike James   
Saturday, 21 March 2020

This is a fun project that may well suggest interesting follow ups. And you don't have to be an expert on the Game of Life  to join in.

Cellular automata are fascinating because they give rise to such complex behavior from such simple rules. John Conway's Game of Life GoL is perhaps the best known and it is astonishingly complicated given how simple its rules are. What is even more astonishing is the time and effort people put into finding configurations of cells that achieve particular behaviors.

If you take an image and digitize it to binary then you can regard this as a starting point for a GoL configuration. Take the Mona Lisa for example. Digitizing it gives:

monalisa

You can then run the simulation and see what happens. As blocks of live cells next to each other die at the next step you almost immediately get an outline and then configurations which slowly decay and look less and less like the original.

What about the problem of finding a configuration that evolves into a well known image? This is the problem that  Kevin Galligan tackles on his personal blog. If you think this is easy then you probably haven't noticed that GoL is not a reversible cellular automaton. You can't easily go backward in time from a configuration you want to an earlier configuration that evolves into it. However, what you can do is write down a Boolean equation that gives the state of the grid in terms of what it would have to be to generate the current state. For example, if the cell is alive then if it was alive in the earlier state it must have 2 or 3 alive neighbours, but if it was dead then 3 of its neighbours must have been alive. You can write this down as a logical equation involving the states of the cells.

The big problem is that this equation is big and difficult so solve. You have to find values of all of the variables that make the equation true. If you have a passing acquaintance with computer science theory you will recognize this as a SAT problem and there are automatic SAT solvers which we can use. However, SAT is an NP Complete problem and this makes it one of those problems that very quickly becomes too big to solve. Nevertheless you can work with 400 cells in something like 250 seconds.

So you can take a state and write down the logical equation for the state that will evolve into it in one time step. You can then take that state and write down its logical equation and solve for the state that came before it, and so on. Problem solved!

Not quite. There can be multiple solutions at each step and there can be no solution at all. Some configurations are called "Gardens of Eden" because you can prove (not easily) that there is no configuration that evolves into them. It seems that these are more common than you might imagine and hence difficult to avoid. All but one of the images that were tried resulted in a Garden of Eden at the very first backward step.

To return to the digitized Mona Lisa, what do you think the configuration that evolves into it after just one step looks like?

monalisacell

Not much trace of the the original!

Have a look at Kevin's blog for more examples.

Why so many Gardens of Eden?

Even if you don't find this fun at least you now know what you can use a SAT solver for.

 

  •  Mike James is the author of The Programmer’s Guide To Theory which as its subtitle "Great ideas explained" suggests, sets out to present the fundamental ideas of computer science, including SAT an informal and yet informative way.

 

More Information

https://kevingal.com/blog/mona-lisa-gol.html

Related Articles

Training A Cellular Automaton

Tetris On Game Of Life - A Great Achievement

SmoothLife - A Continuous Conway's Life 

Cellular Automata - The How and Why

Does John Conway Hate Life?

A New Spaceship Speed In Life

Waterbear Spaceship - Conway's Life 

The Game of Life in hardware

A New Computational Universe - Fredkin's SALT CA

A New Kind of Science Is Ten

Spreadsheets are special

Life in WPF

It's life but not ...

Brain-like computing?

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.

 

Banner


GitHub To Acquire npm
17/03/2020

Microsoft is purchasing npm, the package manager for Node.js. The intention is for npm to be freely available and their will be continued, paid for, support customers who use npm Pro, Teams, and  [ ... ]



OpenSilver - Silverlight Reborn?
11/03/2020

There are many programmers who regret the passing of Silverlight - it was a great idea. Could it be that modern technology can bring it back from the dead? OpenSilver is an open source attempt at doin [ ... ]


More News

graphics

 



 

Comments




or email your comment to: comments@i-programmer.info

 

 

Last Updated ( Saturday, 21 March 2020 )