This is the second version of my rule 110 automaton. It's a simplified version of the old 3D printed cellular automaton, 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 |
We can simplify this by saying that if all three cells are one, or the rightmost two cells are zero, then the output is zero, otherwise it is one.
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.