• Jim MacArthur
Robots, automata and electronics


Rule 110 automaton, version 2

Tuesday, 29th July 2014

Alt text not implementedThis is the second version of my rule 110 automaton. It's a simplified version of the old 3D printed automation, and made from laser cut parts instead of using 3D sintering.

Rule 110 is an elementary but Turing-complete 1-dimensional cellular automaton. Each cell of the new generation is based on the corresponding cell in the previous generation, and its two neighbours. It follows these rules:

000 001 010 011 100 101 110 111
0 1 1 1 0 1 1 0

When the previous generation and new generation are represented by ball bearings, they look like this. The bottom row is the new generation and the top row is the previous generation.

Alt text not implemented

What's now required is a mechanism that will push the new generation ball bearings from their initial position at 1 to a new position at 0 if the relevant cells match the pattern. To do this, we drop levers onto the track and where the data is in the right pattern, they will fall onto the track:

Alt text not implemented

The two levers sensing the input row now form a logical 'or' operation; if either lever falls, they'll push a third lever which then pushes the ball bearing in the output row into the '0' position.

Alt text not implemented

Here's a very tedious video of an acrylic version working - it takes just over 4 minutes to run 37 cells, so clocking in at 146mHz. It's the fastest computer I've built so far. This YouTube video has annotations which explain some of its operations. You may want to turn annotations on if you don't normally do so.

It's not fully automatic like the Turing machine, requiring a person to reset the output row and turn the machine round for each generation of the rule 110 cellular automaton. It is however much more relaible and much quicker. The 5/2 Turing machine emulates rule 110 (that's it's proof of universality) which this automaton calculates directly, and it would take two passes at the tape to calculate this cellular automaton.