This is an automaton invented by Gary Shannon (see the original page; some gates are taken from this page). It is a 2D, totalistic automaton with Moore neighboorhood and 4 different states: black, grey, empty and border. The grey state is a virtual cell, because it is not counted as a neighbor. The rules:
A "battery", which emits one black cell every 4 ticks:
A battery, which emits one black cell every 3 ticks:
The XOR gate, built with a T-joint:
With a battery and an XOR gate, a NOT gate is possible:
At the bottom you can see a curve, which is not part of the XOR gate.
To cross two signal paths, a crossover device is needed (the idea was posted to the comp.theory.cell-automata newsgroup by Paul Chapman for this CA, but John von Neumann has invented a similiar gate for his Universal Constructor many years ago). The crossover is built with curves, XOR gates and an inverse T-joint, which splits an incoming signal into two signals. The crossover works with a space of one cells, too, as the following animation shows:
You can't emulate all logic operations with XOR and NOT, only. Another gate is needed. I've found a NOT IMPLICATION gate. The implication A => B is false only, if A is true and B is false:
It's easy to built a NOR with a NOT IMPLICATION and a NOT gate (written as "!"), as the following logic table shows:
|A||B||!A||(!A => B)||!(!A => B)||A NOR B|
With this gates all other gates can be built to construct a computer.
Another symbolic approach: Paul Chapman calculated a "AND NOT" operation:
!(A => B) = !(!A AND B) = A AND !B
and with this, and the NOT operator, the AND and OR operators are possible:
A AND B = A AND !(!B)
A OR B = !(!A AND !B) [DeMorgan's Law]
Because XOR is easier to built than NOT, it is useful to built AND and OR with AND! and XOR alone:
|A||B||!(A XOR B)||A AND !(A XOR B)||A AND !B||(A AND !B) XOR B|
|= A AND B||= A OR B|
NAND is an AND with a NOT at the output, so all gates exists to construct a computer (NAND alone would be sufficient).
All gate files zipped in MCell format. To make it look like the animations on this page, with black/grey/white/red cells, copy the file "virtual.mcp" from the gate zip file to the MCell\System directory. After restarting MCell you can select it from the menu Colors->PaletteSelection->Virtual.