Friday, October 26, 2012

[lgneexpj] Powerful cellular automata

It is difficult to build a Turing-complete universal computer in Conway's Game Of Life.  The famous examples are a counter machine (which encounters exponential slowdown) and a puffer train which lays down tape cells.

Is there a different cellular automaton rule that would make it easier to build computers?  The motivation is to actually build it in silicon as an alternative to current microprocessor design.  Cellular automata are very simple and exhibit wonderful locality (no need for long wires, so the clock can be run extremely fast), reflecting the actual locality of our physical world.  The problem of translating code to run on this chip is left to the compiler.

No comments :