I don’t often post on Geek, and my computer science is very rusty, so please bear with me.

Some recent posts on Flame brought up the concept of macrocomputation, such as analog computers like Stonehenge or the pyramids, or slide rules. Actually, computers need not be built out of matter at all, and I mean programmable digital computers, with virtual i/o devices, registers, logic gates, boolean logic, storable programs and memory.

Those of you who’ve heard of Conway’s Game of Life

http://en.wikipedia.org/wiki/Conway’s_Game_of_Life

are no doubt familiar with the concept of Cellular Automata. Cellular automata are virtual objects that exist in a staightforward 2D grid which manipulates itself according to some very simple and easily defined rules. Conway’s Game generates a fascinating zoo of objects that exist as constellations of pixels defined as pieces of grid turned on or off. I don’t have room to describe it here, but the WIKI article does a great job of explaining it, with moving pictures.

The point is these virtual creatures are not made of matter, just collections of grid squares that are either on or off, and defined by extremely simple rules. They move around, reproduce, live and die, vanish, maintain structural integrity, interact with predictable results and exist in a bewildering array of different types, forming a virtual universe which is only now being explored. (That’s why its called “Life”), these virtual creatures behave in many ways like living things. You don’t need a computer to create cellular automata, a pencil and graph paper will work just fine theoretically, although it quickly becomes very difficult to visualize more complex patterns in practice without computer assistance of some kind.

Conway’s game can produce moving objects (called gliders), devices for generating moving objects (glider guns), and more complex devices which can modulate streams of moving objects. This allows you to transmit information. Other objects exist which oscillate between different states (which serve as clocks to synchronize multiple activities) and even some objects which can make copies of themselves, or totally destroy other objects. This allows the writing and erasing of memory and i/o.

Different combinations of these objects placed in certain geometric grid configurations can be used to constuct Boolean operators and junctions, switches, registers, i.e., virtual analogues of all the mechanical and logical components of a digital computer. This is not a simulated computer, it is a real computer composed of virtual parts governed by the Conway game rules.

In other words, you can create a computer of parts which exist only in an imaginary grid, and these computers can be be made to run stored programs. You can build a computer with no matter at all, just thought. Although for it to work, it has to be running on a mechanical computer.

Conway’s simple automata exist in 2D space with only 4 rules:

1.Any live cell with fewer than two live neighbours dies, as if caused by under-population.
2.Any live cell with two or three live neighbours lives on to the next generation.
3.Any live cell with more than three live neighbours dies, as if by overcrowding.
4.Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

And that is it. Those four rules operating on a 2D grid can be used to create hundreds of virtual objects with differnt properties.

Other Cellular automata exist in higher dimensions, and with more complex rule sets, the possibilities are endless, and some have even suggested that the fabric of quantum spacetime itself is a fractal cellular automaton existing in some n-dimensional space. After all, if you can build a computer of virtual parts, surely you can assemble quarks into subatomic particles that way.

Read the Wiki artical, and follow up some of the other sources. Its fascinating stuff.