Wireworld cellular automaton

1 | ANU College of Engineering and Computer Science March 2013

WIRING UP WIREWORLD First assignment for Introduction to Programming and Algorithms 2013

Uwe R. Zimmer based on work by Robert Offner (Probie)

What are you looking at on the right?

• A seven segment display showing the number ?

• A picture of a seven segment dis- play showing the number ?

• A picture of a computer emulating electronic circuits?

• A machine emulating a machine emulating a machine?

• A weird bunch of colour spots?

• A very simple machine, yet as powerful as any other computer?

• A pattern which is probably supposed to change over time?

Yes, you guessed right: this is a cellular automaton. And pattern you see (the whole picture) is its current state. Most cellular automata have a state which is a finite, fixed (here: two) dimen- sional, rectangular pattern (grid, matrix) of cells – which makes it easy to display on a screen. Each cell is in exactly one out of finite list of discrete cell states at any time. As these cell states are finite and fixed, we give each cell state a colour and just print a dot of this colour for each cell in the automaton. So far we only have a weird way to describe a bitmap picture.

The interesting aspect of the cellular automata lies in the rules which are used to progress from one state to the next. So the pictures on this page are actually only snapshots of states and the cellular automata will make them move. This is done by a (usually stunningly small) set of rules which only take the current state of the cell itself and its local neighbourhood into ac- count.

The specific cellular automaton which you see here is called Wireworld and is defined by four possible states for each cell:

• Empty

• Conductor

• Electron head

• Electron tail

and the accompanying four rules to progress each cell into the next state:

• Empty Empty&

• Conductor Electron head Conductor

Electron heads; if 1 or 2 of the 8 adjacent cells are ;otherwise

& (

• Electron head Electron tail&

• Electron tail Conductor&

This sounds like it is just meant to send an electron through a wire, and in fact it does that too. Look at the simple state on the right and progress it a few states further by applying the rules of Wireworld (in your head or on a piece of paper).

2 | ANU College of Engineering and Computer Science March 2013

That’s all? All this effort just to move an electron in a circle? It turns out that this is just the beginning and those four cell states and rules of Wireworld can be employed to express any form of complex computation which for example your computer in front of you is capable of. To get into the mood, have a closer look at this state to the right and progress it a few states further as well in your head (or on a piece of paper).

This state turns out to implement the functionality of an Exclusive-Or gate (the logical function which returns true if exactly one of the inputs is true). Any other logic gate can be formulated in a similar way, and based on what we know about logic: we can build any digital computer out of basic logic gates1.

While Wireworlds can implement logic gates, they are more flexible and we do not need to restrict ourselves to a design in logic gates alone. As you will watch the Wireworlds move along in a few days, you will find that there is for instance also a quite complex encoding of time and synchronization happening. Cellular Automata have been frequently discussed as an alterna- tive mode of computation and also have interesting relations to Quantum Computing and Massively Parallel Computing. I’ll leave it to you to dig deeper, if you are so inclined, but here we continue with your concrete assignment goal.

Programming task Your task is to make the Wireworld move. In Haskell terms you will need to implement the func- tion:

transition_world :: World_model -> World_model

In fact your will implement it twice:

transition_world :: List_2D Cell -> List_2D Cell

transition_world :: Ordered_Lists_2D Cell -> Ordered_Lists_2D Cell

based on two different underlying data structures used to store the current world (state of the automaton) while the Cell states are simply:

data Cell = Head | Tail | Conductor | Empty.

In the first case the world is stored as a single list where each cell has accompanying coordi- nates attached. Thus List_2D translates into

type List_2D e = [(e, (X_Coord, Y_Coord))]

where e is a placeholder for any type (we use it for our type Cell). No particular order on those coordinates is assumed.

In the second case the world is split up into lines (cells sharing the same y coordinate) and each line is stored in a separate list. Each line has a y coordinate, and each cell inside the line has an x coordinate attached to it. The whole world is then a list of those lines. Thus Ordered_ Lists_2D breaks down into:

type Ordered_Lists_2D e = [Sparse_Line e]

data Sparse_Line e = Sparse_Line {y_pos :: Y_Coord, entries :: Placed_Elements e}

type Placed_Elements e = [Placed_Element e]

data Placed_Element e = Placed_Element {x_pos :: X_Coord, entry :: e}

where e is again a placeholder for any type. All Sparse_Lines are ordered ascending by Y_Coord and all cells inside Placed_Elements are ordered ascending by X_Coord.

1 In fact we have too much already, as a “not-and” or NAnd gate alone is suf- ficient to implement any other part of your computer.

3 | ANU College of Engineering and Computer Science March 2013

The two functions transition_world which you need to complete are found in the two mod- ules in the directory Sources/Transitions.

As both data structures offer the same functions it would be possible to write the same code for both of your transition_world functions – yet think carefully whether this would be a clever idea. While the two data-structures offer the same logical functionality, the runtimes which they take to do so may be quite different. Hence it will make sense to write your transition functions in a way that they will exploit the characteristics of the underlying data structures. If you are unsure how they data structures differ, you may also start by running the same code in both functions and measure the number of transitions which each of them will achieve per second (read on to find out how to measure those). This will give you a hint as to what’s happening here. Then start exploring how you could re-arrange your code in order to benefit from the characteristics of the two offered data structures.

Note that none of those data-structures is “dense”, i.e. not all coordinates