NKS Glossary

Dr. Todd Rowland
todd_rowland@wolfram.com
Wolfram Science Group
http://www.wolframscience.com/reference/education/

And

And is a Boolean operator which returns True only when both arguments are True.

Bit

A bit can be either 0 or 1. Graphically, a zero corresponds to a white cell and a one corresponds to a black cell.

Boolean Operator

An operator that takes two values, usually assigned the logical values True or False, and returns such a value. There are four traditional Boolean Operators: And, Or, Nand, Xor.

Cell

A cell is the basic unit in a grid, or put differently, a grid is made up of cells. It has a color attribute, normally black or white.

Elementary Cellular Automaton

A rule for updating a cell's color based on its color and the color of its immediate neighbors. The color of a cell in an graphical display of an evolution depends on the colors of the three cells immediately above it.

Emulation

One rule's evolution emulates another rule's evolution if there is a way to represent the second rule's evolution using the first one. One rule emulates another rule if there is an emulation using the first rule, no matter what initial condition is chosen for the second rule.

Evolution

See Cellular Automaton Evolution

Identity Map

The identity map is a function which returns the same value as its input.

Irreducibility

An evolution is irreducible if there is no way to speed up its evolution by making a reliable future prediction.

Initial Condition

The initial condition for an evolution is the string of bits before the first step.  The simplest nontrivial initial condition is a string of bits with a single black cell surrounded by white cells.

Nand

Nand is a Boolean operator which returns True except when both arguments are True.

Or

Or is a Boolean operator which returns False only when both arguments are False.

Rule 30

One of the elementary cellular automaton. It's rule can be translated from the number by the base 2 representation of 30 as {0,0,0,1,1,1,1,0}.

Rule 90

One of the elementary cellular automaton. It's rule can be translated from the number by the base 2 representation of 90 as {0,1,0,1,1,0,1,0}.

Rule 110

One of the elementary cellular automaton. It's rule can be translated from the number by the base 2 representation of 110 as {0,1,1,0,1,1,1,0}.

Rule 250

One of the elementary cellular automaton. It's rule can be translated from the number by the base 2 representation of 250 as {1,1,1,1,1,0,1,0}.

Shift Map

A map which changes the bits in a string by shifting them over.

String

In the context of this course, a string is a string of bits, which is a sequence of bits. In computing, a string might also mean a sequence of letters.

Universal Rules

A rule is universal if it can emulate any other rule.

Xor

Xor is a Boolean operator which returns True only when exactly one of its arguments is True. It is essentially the same as addition with modular arithmetic in mod 2.