Archive for the ‘Cellular Automata’ Category

Numba Versus C++ – On Wolfram CAs

Tuesday, March 6th, 2018

Numba Versus C++ by David Butts, Gautham Dharuman, Bill Punch and Michael S. Murillo.

Python is a programming language that first appeared in 1991; soon, it will have its 27th birthday. Python was created not as a fast scientific language, but rather as a general-purpose language. You can use Python as a simple scripting language or as an object-oriented language or as a functional language…and beyond; it is very flexible. Today, it is used across an extremely wide range of disciplines and is used by many companies. As such, it has an enormous number of libraries and conferences that attract thousands of people every year.

But, Python is an interpreted language, so it is very slow. Just how slow? It depends, but you can count on about 10-100 times as slow as, say, C/C++. If you want fast code, the general rule is: don’t use Python. However, a few more moments of thought lead to a more nuanced perspective. What if you spend most of the time coding, and little time actually running the code? Perhaps your familiarity with the (slow) language, or its vast set of libraries, actually saves you time overall? And, what if you learned a few tricks that made your Python code itself a bit faster? Maybe that is enough for your needs? In the end, for true high performance computing applications, you will want to explore fast languages like C++; but, not all of our needs fall into that category.

As another example, consider the fact that many applications use two languages, one for the core code and one for the wrapper code; this allows for a smoother interface between the user and the core code. A common use case is C or C++ wrapped by, of course, Python. As a user, you may not even know that the code you are using is in another language! Such a situation is referred to as the “two-language problem”. This situation is great provided you don’t need to work in the core code, or you don’t mind working in two languages – some people don’t mind, but some do. The question then arises: if you are one of those people who would like to work only in the wrapper language, because it was chosen for its user friendliness, what options are available to make that language (Python in this example) fast enough that it can also be used for the core code?

We wanted to explore these ideas a bit further by writing a code in both Python and C++. Our past experience suggested that while Python is very slow, it could be made about as fast as C using the crazily-simple-to-use library Numba. Our basic comparisons here are: basic Python, Numba and C++. Because we are not religious about Python, and you shouldn’t be either, we invited expert C++ programmers to have the chance to speed up the C++ as much as they could (and, boy could they!).

This webpage is highly annoying, in both Mozilla and Chrome. You’ll have to visit to get the full impact.

It is, however, also a great post on using Numba to obtain much faster results while still using Python. The use of Wolfram CAs (cellular automata) as examples is an added bonus.


Build a working game of Tetris in Conway’s Game of Life (brain candy)

Tuesday, September 19th, 2017

Build a working game of Tetris in Conway’s Game of Life

From the webpage:

In Conway’s Game of Life, there exist constructs such as the metapixel which allow the Game of Life to simulate any other Game-of-Life rule system as well. In addition, it is known that the Game of Life is Turing-complete.

Your task is to build a cellular automaton using the rules of Conway’s game of life that will allow for the playing of a game of Tetris.

Your program will receive input by manually changing the state of the automaton at a specific generation to represent an interrupt (e.g. moving a piece left or right, dropping it, rotating it, or randomly generating a new piece to place onto the grid), counting a specific number of generations as waiting time, and displaying the result somewhere on the automaton. The displayed result must visibly resemble an actual Tetris grid.

Your program will be scored on the following things, in order (with lower criteria acting as tiebreakers for higher criteria):

  • Bounding box size — the rectangular box with the smallest area that completely contains the given solution wins.
  • Smaller changes to input — the fewest cells (for the worst case in your automaton) that need to be manually adjusted for an interrupt wins.
  • Fastest execution — the fewest generations to advance one tick in the simulation wins.
  • Initial live cell count — smaller count wins.
  • First to post — earlier post wins.

A challenge that resulted in one and one-half years of effort by an array of participants to create an answer.

Very deep and patient thinking here.

Good training for the efforts that will defeat both government security forces and DRM on the web.

New Spaceship Speed in Conway’s Game of Life

Saturday, January 14th, 2017

New Spaceship Speed in Conway’s Game of Life by Alexy Nigin.

From the post:

In this article, I assume that you have basic familiarity with Conway’s Game of Life. If this is not the case, you can try reading an explanatory article but you will still struggle to understand much of the following content.

The day before yesterday forums saw a new member named zdr. When we the lifenthusiasts meet a newcomer, we expect to see things like “brand new” 30-cell 700-gen methuselah and then have to explain why it is not notable. However, what zdr showed us made our jaws drop.

It was a 28-cell c/10 orthogonal spaceship:

An animated image of the spaceship

… (emphasis in the original)

The mentioned introduction isn’t sufficient to digest the material in this post.

There is a wealth of material available on cellular automata (the Game of Life is one).

LifeWiki is one and Complex Cellular Automata is another. While not exhaustive of all there is to know about cellular automata, familiarity with take some time and skill.

Still, I offer this as encouragement that fundamental discoveries remain to be made.

But if and only if you reject conventional wisdom that prevents you from looking.

Langton’s ant

Tuesday, September 8th, 2015

Langton’s ant (Wikipedia)

If two-dimensional Turing machines seem too simple, despite their complex emergent behavior, perhaps you would like to push them into three (3) or more dimensions?

The Wikipedia page listed Langton’s Ant in 3D, which has source code so you have a leg up on 3D ants.

Greater than 3D anyone? Understanding that you would encounter all the usual visualization problems of > three dimensional objects. Comparison/analysis of such objects?

I saw this in a tweet by Computer Science.

Generating Sequences of Primes in Conway’s Game of Life

Thursday, September 3rd, 2015

Generating Sequences of Primes in Conway’s Game of Life by Nathaniel Johnston.

From the post:

One of the most interesting patterns that has ever been constructed in Conway’s Game of Life is primer, a gun that fires lightweight spaceships that represent exactly the prime numbers. It was constructed by Dean Hickerson way back in 1991, yet arguably no pattern since then has been constructed that’s as interesting. It seems somewhat counter-intuitive at first that the prime numbers, which seem somehow “random” or “unpredictable”, can be generated by this (relatively simple) pattern in the completely deterministic Game of Life.

You may not have a favorite Bible verse but surely you have an opinion on whether prime numbers are ‘somehow “random” or “unpredictable,” yes?

Take a break from the drivel that makes up most news feeds and get some real mental exercise.

The link to Conway’s Game of Life in the original post is broken. I have repaired it in the quote.

There is much to explore at:


dgol – Distributed Game Of Life

Wednesday, August 19th, 2015

dgol – Distributed Game Of Life by Mirko Bonadei and Gabriele Lana.

From the webpage:

This project is an implementation of the Game of life done by Gabriele Lana and me during the last months.

We took it as a “toy project” to explore all the nontrivial decisions that need to be made when you have to program a distributed system (eg: choose the right supervision strategy, how to make sub-systems communicate each other, how to store data to make it fault tolerant, ecc…).

It is inspired by the Torben Hoffman’s version and on the talk Thinking like an Erlanger.

The project is still under development, at the moment we are doing a huge refactoring of the codebase because we are reorganizing the supervision strategy.

Don’t just nod at the Thinking like an Erlanger link. Part of its description reads:

If you find Erlang is a bit tough, or if testing gives you headaches, this webinar is for you. We will spend most of this intensive session looking at how to design systems with asynchronous message passing between processes that do not share any memory.

Definitely watch the video and progress in this project!

Conway’s Game of Life in Clojure

Monday, April 7th, 2014

Conway’s Game of Life in Clojure by Charles Ditzel.

Charles has collected links to three separate implementations of the “Game of Life” (aka cellular automata).

Before you dismiss cellular automata as “just graphics,” you might want to remember that Stephen Wolfram, the inventor of Mathematica is a long time CA enthusiast.

I’m not saying there is a strong connection between those facts but it seems foolish to presume there is none at all.

Complex Adaptive Dynamical Systems, a Primer

Friday, August 9th, 2013

Complex Adaptive Dynamical Systems, a Primer by Claudius Gros. (PDF)

The high level table of contents should capture your interest:

  1. Graph Theory and Small-World Networks
  2. Chaos, Bifurcations and Diffusion
  3. Complexity and Information Theory
  4. Random Boolean Networks
  5. Cellular Automata and Self-Organized Criticality
  6. Darwinian Evolution, Hypercycles and Game Theory
  7. Synchronization Phenomena
  8. Elements of Cognitive Systems Theory

If not, you can always try the video lectures by the author.

While big data is a crude approximation of some part of the world as we experience it, it is less coarse than prior representations.

Curious how less coarse representations will need to become in order to exhibit the complex behavior of what they represent?

I first saw this at Complex Adaptive Dynamical Systems, a Primer (Claudius Gros) by Charles Iliya Krempeaux.

Introduction to Complexity course is now enrolling!

Tuesday, February 5th, 2013

Santa Fe Institute’s Introduction to Complexity course is now enrolling!

From the webpage:

This free online course is open to anyone, and has no prerequisites. Watch the Intro Video to learn what this course is about and how to take it. Enroll to sign up, and you can start the course immediately. See the Syllabus and the Frequently Asked Questions to learn more.

I am waiting for the confirmation email now.

Definitely worth your attention.

Not that I think subject identity is fractal in nature.

Fractals as you know have a self-similarity property and at least in my view, subject identity does not.

As you explore a subject identity, you encounter other subjects identities, which isn’t the same thing as being self-similar.

Or should I say you will encounter complexities of subject identities?

Like all social constructs, identification of a subject is simple because we have chosen to view it that way.

Are you ready to look beyond our usual assumptions?

Update: Introduction to Complexity [Santa Fe Institute]

Wednesday, December 5th, 2012

The Santa Fe Institute has released the FAQ and syllabus for its “Introduction to Complexity” course in 2013.

The course starts January 28, 2013 and will last for eleven (11) weeks.

Lecture units:

  1. What is Complexity?
  2. Dynamics, Chaos, and Fractals
  3. Information, Order, and Randomness
  4. Cellular Automata
  5. Genetic Algorithms
  6. Self-Organization in Nature
  7. Modeling Social Systems
  8. Networks
  9. Scaling
  10. Cities as Complex Systems
  11. Course Field Trip; Final Exam

Funding permitting there may be a Complexity part II in the summer of 2013.

Your interest and participation in this course may help drive the appearance of the second course.

An earlier post on the course: Introduction to Complexity [Santa Fe Institute].

Conway’s Game of Life for Curved Surfaces (Parts 1 and 2)

Thursday, November 29th, 2012

Conway’s Game of Life for Curved Surfaces (Part 1) and Conway’s Game of Life for Curved Surfaces (Part 2) by Mikola Lysenko.

A generalization of John Conway’s original Game of Life on curved surfaces.

Definitely not for the faint of heart and will likely have you consulting old text books.

A simple game that even in its original version, unfolds into complexity. To say nothing of the extended version.

See Cellular automaton (history and applications).

I first saw this in a tweet from Math Update.

Adventures In Declarative Programming: Conway’s Game Of Life

Friday, August 31st, 2012

Adventures In Declarative Programming: Conway’s Game Of Life by Manuel Rotter.

From the post:

My first blog post about declarative programming explained how to write a Sudoku solver in the logic programming language Prolog. This time I’ll show you how to implement Conway’s Game of Life in the functional programming language Clojure.

But before that, let me explain a few general things. The first three paragraphs are for readers who are not familiar with certain concepts. People who already know what Clojure or Conway’s Game of Life is, may feel free to skip those paragraphs. It starts getting serious at “Game of Life in Clojure”.

Having a result that interests me makes learning something new easier.

Here it is “Conway’s Game of Life,” a two dimensional type of Cellular Automata.

You may also find the following of interest:

Game of Life 3D

The Game of Life in 3D (using three.js)

If you have heard of Wolfram’s A New Kind of Science, be aware the full text is online for free viewing with other materials at: Wolfram Science.

A Computable Universe,
Understanding Computation and
Exploring Nature As Computation

Friday, June 1st, 2012

Foreword: A Computable Universe, Understanding Computation and Exploring Nature As Computation by Roger Penrose.


I am most honoured to have the privilege to present the Foreword to this fascinating and wonderfully varied collection of contributions, concerning the nature of computation and of its deep connection with the operation of those basic laws, known or yet unknown, governing the universe in which we live. Fundamentally deep questions are indeed being grappled with here, and the fact that we find so many different viewpoints is something to be expected, since, in truth, we know little about the foundational nature and origins of these basic laws, despite the immense precision that we so often find revealed in them. Accordingly, it is not surprising that within the viewpoints expressed here is some unabashed speculation, occasionally bordering on just partially justified guesswork, while elsewhere we find a good deal of precise reasoning, some in the form of rigorous mathematical theorems. Both of these are as should be, for without some inspired guesswork we cannot have new ideas as to where look in order to make genuinely new progress, and without precise mathematical reasoning, no less than in precise observation, we cannot know when we are right — or, more usually, when we are wrong.

An unlikely volume to search for data mining or semantic modeling algorithms or patterns.

But one that should be read for the mental exercise/discipline of its reading.

The asking price of $138 (US) promises a limited readership.

Plus a greatly diminished impact.

When asked to participate in collections, scholars/authors should ask themselves:

How many books have I read from publisher X?*

*Read, not cited, is the appropriate test. Make your decision appropriately.

If republished as an accessible paperback, may I suggest: “Exploring the Nature of Computation”?

The committee title makes the collage nature of the volume a bit too obvious.

Clojure Game of Life

Monday, April 2nd, 2012

Clojure Game of Life

From the post:

This is a Conway’s Game of Life in functional style written in Clojure.

Wikipedia (Cellular Automaton) mentions:

Cellular automata are also called “cellular spaces”, “tessellation automata”, “homogeneous structures”, “cellular structures”, “tessellation structures”, and “iterative arrays”.

You may recall that Stephen Wolfram wrote A New Kind of Science (1280 pages) about cellular automata. Had a great author. Needed a great editor as well.

At a minimum, I take cellular automata for the proposition that computational artifacts exist, whether we expect or forecast them or not.

At a maximum, well, that’s an open research question isn’t it?