# The Virtual cellular automaton

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:

1. A black cell turns into a grey cell on the next generation, regardless of its neighbors.
2. A grey cell turns into an empty cell on the next generation, regardless of its neighbors.
3. An empty cell turns into a black cell, if the number of black neighbors are 1 or 3.

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
false false true false true true
true false false true false false
false true true true false false
true true false true false false

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
false false true false false false
false true false false false true
true false false false true true
true true true true false true
= 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.

10. March 2003, Frank Buß