Tuesday, 29th July 2014

This 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.

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:

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.

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.

- Mechanical decoder logic
- Langton's Ant with Hexbugs
- Sliding plate logic gates
- AVR Minimus servo controller
- Zeta toggle-switch computer
- Rule 110 automaton, version 2
- Failed experiment: Water logic gates
- Grue detection t-shirts
- Error correction of the NPL time signal
- Simple, headphone-controlled phone robot
- More 2D Game demos
- Investigating Raspberry Pi performance problems
- 2D Platform games with PyGame
- Exhibiting the Mk2 Turing machine
- Chorded keyboard for mobile phones
- Automating layout of laser-cut models
- Turing Machine and Maker Faire