Information Technology Reference
In-Depth Information
Table 3.4.
Three common types of cells and their definition (in terms of computing V)
Type of cell
(symbol)
rojection variable
aximal number
of bits
N
defining
the gene
Comments
The most compact
kind of cells
n
V
¦
u
1
Totalistic (t)
k
N
n
1
k
Discussed in
extenso in the
previous sections
n
V
bu
¦
u
Semitotalistic (s)
1
k
N
2
n
k
2
uge number of
possible cells
n
k
1
V
¦
2
u
niversal (a)
k
n
N
2
k
1
n
Note that there is a more general formula for the universal cell, where
V
¦
b
1
k
u
k
k
>
@
[2] with an orientation vector
b
optimied to reduce the number of
transitions as explained above for the semitotalistic cells. owever, unlike in the
case of the semitotalistic cell where the optimiation process is as simple as trying
b
,..,
1
b
all values from 0 to
n
for the single
orientation
parameter
b
, in the case of univer-
sal cells this process is computationally intensive and therefore in the next we will
consider the default orientation
>
@
0
1
n
1
which is not necessary optimal
b
2
,
2
,..,
2
but gives a valid representation of the cell.
ssuming rectangular grids in
D
dimensions, it would be useful to define a
taxonomy formed as a three-letter string (also called a
family label
) containing
information about: the sie of the grid (o ne-dimensional, two-dimensional, three-
dimensional, etc.), the type of cell (as indicated in the above table), and the
number
n
of inputs. The taxonomy thus defines a family of cells but also a grid
model. For example:
x The family of cells “
1t3”
includes totalistic cells on a one-dimensional grid, with
a neighborhood formed by 3 cells (for instance the left, center and right cells).
Note that many other neighborhoods with 3 cells could be defined, denoted by
adding some additional information to the family type. For instance “1t3a” would
define a cell like the above but where the neighborhood is defined as (2 cells to the
left, mid cell, 2 cells to the right), etc.
x The family of cells “
1a3
” has
3
2
2
= 256 members and was extensively studied
by Wolfram. As reported in [17] such cells with ID=110 give a cellular auto-
mation capable of universal computation.
Search WWH ::
Custom Search