# Index

Ceiling (integer above)

basic example of, 854

Celestial bodies

and fate, 752

Celestial mechanics

and Bohr atom, 1056

and computational irreducibility, 1133

difficulty of computation in, 1146

randomness in, 314

and three-body problem, 972

Cell complexes, 1050

Cell division

in embryos, 1009

in networks, 1039

in plants, 1004

randomness in, 970

Cells (biological)

adhesion of, 418

fossils of early, 1179

migration of, 418

programmed death of, 419

sensory, 577

shapes of, 1007

shapes of in plants, 404

types of, 1002

and Voronoi diagrams, 987

Cellular arrays, 877

see also Cellular automata

Cellular automata

1D, 53–65

2D, 170–181

3D, 182–183

for *3n+1* problem, 904

5-neighbor 2D, 927

9-neighbor 2D, 927

additive

see Additive cellular automata

and aggregation, 994

from algebraic systems, 886

algorithmic information in, 1067

with associative rules, 956

asynchronous

see Sequential cellular automata

at-angle evolution of, 1118

attractors in, 275

axioms for, 794, 1168

and biological form, 1004

block

see Block cellular automata

blocking transformations in, 269, 701

Boolean formulas for, 616, 869, 1096

cardinality of, 1127

and causal invariance, 1035

and chaos history, 972

circles from, 334

classes of, 231–249

compared to Go, 875

and complexity in biology, 1001

and complexity research, 862

compositions of, 886

computational irreducibility in, 740

computational reducibility in, 744

computations in, 638–641

conservation laws in, 458, 1023

continuous, 155–160

continuous models of, 976

continuum limits of, 327

and cowrie patterns, 1012

and cryptography, 603

crystals growth and, 369

in *d* dimensions, 927

and data compression, 569

deducing rules for, 1089

density conservation in, 459

density transitions in, 341

difference patterns in 2D, 950

diffusion equation from, 1024

and dimensions of networks, 1030

for doubling, 832

elementary

see Elementary cellular automata

emulated by cyclic tag systems, 668

emulated by mobile automata, 664, 1112

emulated by other systems, 664–673

emulated by PDEs, 1129

emulated by substitution systems, 666, 1035

emulated by symbolic systems, 668, 1113

emulated by tag systems, 667, 1113

emulated by TMs, 665, 765, 1113

emulating logic circuits, 662, 1112

emulating mobile automata, 657, 1111

emulating multiplication, 661, 1112

emulating non-deterministic Turing machines, 1146

emulating other systems, 656–663

emulating register machines, 661, 1112

emulating substitution systems, 659, 1111

emulating Turing machines, 658, 1111

equivalences of rules, 883

evolution as P computation, 1142

experiments on, 112

factorization of, 956

for finding primes, 640, 1109

finite-size, 258

firing squad problem in, 1035

formulas for evolution of, 1134

fractals in, 25, 58

see also Additive cellular automata

and fracture, 995

games between, 1105

Gray code sequence of, 352

from groups, 887

growth rules for 2D, 928

halting problems for, 1137

hand computation of, 42

hardware simulators for, 928

for hash codes, 622

history of, 48, 876

history of 2D, 928

history of my work on, 880

history of universal, 1115

ideal gas modelled by, 445

implementation of

see `CellularAutomaton`

implementation of 1D, 865

implementation of 2D, 927

implementation of general, 886, 927

implementation of totalistic, 886

invariant states in, 348

invertible

see Reversible cellular automata

as iterated bitwise maps, 921

of limited size, 258, 961

as mappings, 959

and math morphology, 1077

meaning of, 1183

memory of, 621

minimal for given sequences, 1186

and modelling history, 992

modelling with, 366

as models for crystal growth, 369

as models for fracture, 375

as models for space, 472

as models in finance, 431

as models of fluids

see Cellular automaton fluids

and models of traffic, 1014

with more colors, 107

from multiplication tables, 614

my first pictures of, 19, 864

my first use of, 17

`Nand`

forms for, 619, 1096

and nanotechnology, 841

nearby rules in, 948

neighborhoods for 2D, 928

nesting in, 25, 58

see also Additive cellular automata

on networks, 930, 936

non-computability in, 1128

NP completeness in, 767

number of symmetric, 886

origins of nesting in, 270

outcome of evolution in, 753

and P completeness, 1149

as parallel computers, 1109

and patterns on shells, 389

perceptrons for, 1102

with periodic initial conditions, 267

perturbations on, 325

phase transitions in, 339

and pigmentation patterns, 427

possible sequences from, 1186

from powers, 1093

for powers of 3, 903

probabilistic, 591

purpose in, 830

quantum analogs of, 1147

quantum-dot, 1193

for quantum systems, 1060

`r=1`

see Elementary cellular automata

`r=1/2`

, 806, 885

`r=3/2`

, 1088

with random initial conditions, 224–228

random initial conditions for 2D, 246

random mutations in, 391

as randomness generators, 973

and reaction-diffusion, 427, 1013

and regular languages, 1138

repetitive behavior in, 267

reversible

see Reversible cellular automata

rotational invariance in 2D, 473

as rule-based systems, 860

rule numbering for, 53

in sandpile models, 989

for Schrödinger equation, 1060

second-order

see Reversible cellular automata

and self-gravitating systems, 1021

self-reproducing, 1179

from semigroups, 887

sequences of rules in, 241

sequential, 1034

and shell patterns, 423, 1012

and shift registers, 975, 1088

smooth shapes in, 333

spectra of, 1082

speed of light in, 518

for squaring, 639, 1109

state space of, 869, 958

states vs. digit sequences, 950

as statistical tests, 596

structures in, 281–296

structures in as particles, 525

and study of form, 967

surjective, 280

symmetry in 2D, 927

synchronization in, 1035

as syntax checkers, 1109

technology applications of, 841

as texture generators, 578, 1078

thermodynamic behavior in, 443

three-color, 60

and tiling problems, 1139

time vs. space in, 481

as too rigid for ultimate theory, 467

totalistic

see Totalistic cellular automata

ultimate theory of physics and, 1026

undecidability in, 753, 1136, 1138

universal, 644–656, 675

universal 2D, 693

for Voronoi diagrams, 987

weighted totalistic, 427

Cellular automaton fluids, 378–382

as application of randomness, 1192

compressible flow in, 1000

detailed issues with, 999

and generalized fluid flow, 1000

history of, 999

my papers on, 882

on square grids, 999

Cellular logic systems, 877

Cellular spaces

see Cellular automata

Cellular structures

and networks, 1039

from superposed waves, 984

Cellular telephones

radio signals from, 1188

and shift registers, 1086

`CellularAutomaton`

(in Mathematica), 867

framework for, 886

Cellulose

and rigidity of plants, 1004

Census data

and soundex system, 1100

as source of randomness, 968

Center for Complex Systems Research, xiii

Center-surround cells

in visual system, 1075

Central groupoids, 1171

Central Limit Theorem, 329, 976

and differences in 2D CAs, 950

history of, 977

and nesting, 990

and typical data, 1083

Central pattern generators (in animals), 1011

Ceremonial functions, 830

Cerenkov light, 984

CFD (computational fluid dynamics), 1000

Chain (unbranched) hydrocarbons, 1194

Chains

in evaluation, 907

in hashing, 1100

in posets, 1041

Chains (metal)

characteristic shapes of, 1183

Chaitin, Gregory J. (USA/Argentina, 1947– )

and algorithmic randomness, 1068

and experimental math, 899

in Preface, xiii

and randomness in arithmetic, 1067

and universal objects, 1127

Chaitin–Kolmogorov complexity

see Algorithmic information

Chalk

fracture in, 994

Champernowne, David G. (England, 1912–2000)

and normal numbers, 912

Champernowne number, 913

continued fraction of, 915

Change of variables

and amount of computation, 732

Changes

in initial conditions, 252

*Chaos* (book), 971

Chaos theory

artifacts in computations on, 1184

audio studies of, 1080

and Bianchi IX cosmology, 1053

and computational irreducibility, 1133

and computer experiments, 899

and continuous computation, 1128

and divergence of geodesics, 1049

executive toys illustrating, 1183

and financial markets, 1015

and fluid flow, 381

and free will, 752, 971, 1135

and hard sphere gases, 1022

history of, 971

and history of complexity research, 862

and history of numbers, 901

and history of randomness, 968

in iterated maps, 149–155

as limit on science, 1135

and Lyapunov exponents in CAs, 950

and my work on CAs, 19

in ODEs, 922

and origin of randomness, 304–314

and QCD, 1061

and quantum measurement, 1063

and recognizing chaos, 972

and solar system, 973

summary of relations to, 13

and thermodynamics, 1020

in three-body problem, 972

and turbulence, 997

and weather prediction, 1178

Chaperone molecules, 988

Characteristic polynomials

and CA entropies, 958

*Characteristica universalis* (universal language), 1109, 1149

Charcoal

in archeology, 1183

Charge

conservation of, 527, 1022

and gauge invariance, 1045

quantization of, 528, 1046

Charge carriers

and thermal noise, 968

Chartres

maze at, 873

Chaté, Hugues (France, 1961– )

and CA classes, 948

and continuous CAs, 922

`ChebyshevT`

(Chebyshev polynomials)

and logistic map formulas, 1098

Checkerboard

generated by rule 250, 25

as updating pattern, 982

Cheetah

pigmentation pattern of, 426

Chemical kinetics

rate equations in, 984

Chemical networks

and origin of life, 1179

Chemical perception, 1105

Chemical processes

and animal growth, 419

and animal pigmentation, 427

and plant growth, 409

randomness from, 970

and reaction-diffusion, 1012, 1013

Chemical synthesis

basic theory for, 1194

and nanotechnology, 1193

Chemistry

as analog of science in this book, 843

arguments for atoms in, 876

and computational irreducibility, 1193

and definition of life, 825

interesting compounds in, 1194

of martian soil, 1179

networks with analogies in, 1040

success of math in, 859

Chemotherapy

search for compounds for, 1193

Chervil (cow parsley)

shape of wild, 385

Chess

programs for, 1099

Chi-rho page (of Book of Kells), 873

Child development, 1102

history of, 1099

and language, 630

Children

and animism, 1195

and concept of programs, 1177

and free will, 1136

and purposes in nature, 1185

randomness in games of, 968

recognition of intelligence in, 825

China

Pascal's triangle in, 870

Chinese lattice, 874

Chinese Remainder Theorem

and encoding of lists, 1120

and GCD array, 1093

Chips (integrated circuits)

and Boolean minimization, 1097

and history of CAs, 877

and history of computing, 1108

and `Nand`

, 1173

randomness sources on, 970

Chirality of molecules

and definition of life, 1178

Chirping (of radar pulses), 1188

Chladni figures, 984

Chloroplast

form of, 385

Chomsky, Noam (USA, 1928– )

and generative grammars, 939

and models of language, 1104

and universals in language, 1181

Chomsky hierarchy (of formal languages), 939

Chords (musical), 917

in audio for CAs, 869

perception of, 587, 1079

waveforms of, 146

Chorus (natural radio signals), 1187

Christianity

and free will, 1135

rejecting animism, 1195

Christoffel symbols, 1049

Chromatic number

of networks, 1029

Chromaticity values, 1074

Chromosomes

random distribution into, 970

Chunks (in short-term memory), 1102

Church, Alonzo (USA, 1903–1995)

and Church's Thesis, 1125

and defining randomness, 1068

and lambda calculus, 1121

and models of computation, 879

and number combinators, 1122

and origins of universality, 1110

and undecidability, 1136

Church numerals

in combinators, 1122

in symbolic systems, 897

Church–Rosser property, 1036

for combinators, 1122

for symbolic systems, 898

Church's Thesis, 1125

Cicero, M. Tullius (Italy, 106–43 BC)

and free will, 1135

Cilia

symmetries in, 1007

Ciphers, 598

see also Cryptography

Circadian rhythms, 1011

Circle method (in number theory), 1165

Circle packings, 349

history of, 985

with unequal circles, 350

Circles

areas of, 1050

and constructible reals, 1129

lattice points inside, 910

in ornamental art, 873

Circuits (logic)

and computational complexity theory, 1148

and DNF, 1095

layout of, 985

minimal sizes of, 1096, 1143

multilevel minimization in, 1096

and names for operators, 1173

as network system analog, 193

optimal blocks in, 1193

and P completeness, 1149

in practical computers, 1108

as representing functions, 1095

use of `Nand`

in, 806

Circular (cyclic) boundary conditions, 255

Circular growth

in 2D cellular automaton, 178, 979

in 2D random walks, 329

in aggregation systems, 331, 978

Circular reflector

caustics from, 984

chaos from, 311

Circular shapes

of heavenly bodies, 875

Circumference (of networks), 1029

Cirrus clouds

pattern formation in, 947

Cissoids, 875

Citations

for cellular automata, 878

in this book, 850

Cities

growth patterns of, 1014

lack of nesting in, 874

pattern of lights of, 1187

Civet

pigmentation pattern of, 426

Clam shell

growth of, 414

Class 1 behavior, 231

and non-universality, 694

as origin of uniformity, 353

and reversible CAs, 1018

Class 2 behavior, 231

attractors in, 275

in class 3 systems, 269

and limited size, 255

and non-universality, 694

in reversible CAs, 1018

and transition graphs, 962

Class 3 behavior, 231

in 2D cellular automata, 248

attractors in, 278

class 2 behavior in, 269

in continuous CAs, 922

in early neural nets, 1102

and finite-size periods, 258

and fracture patterns, 995

localized structures in, 526

in power cellular automata, 1093

randomness in, 261

in reversible CAs, 1018

and transition graphs, 962

universality in, 698

see also Rule 30, 90, etc.

Class 4 behavior, 231, 235–239

in 2D cellular automata, 248, 948

in 3-color 2-neighbor CAs, 1116

in 3-color totalistic CAs, 948

in 3D cellular automata, 949

attractors in, 278

as between class 2 and 3, 240

in continuous CAs, 244, 922

and defining complexity, 1069

and extraterrestrials, 839

fluctuations in, 960

and history of universality, 1115

number of structures in, 1047

particle collisions in, 540

in reversible CAs, 440, 1018

structures in, 281–296

and universality, 691

see also Rule 110, etc.

Class field theory

and almost integers, 915

Classes, theory of (in foundations of math), 1151, 1171

Classes of cellular automata, 231–249

chaos in, 250

entropies in, 960

frequencies of, 948

history of, 948

undecidability of, 948

Classes of systems

universality of, 1123

Classification

in biology, 1003

of plants, 1004

Classification schemes

undecidability of, 1138

Classifier systems (sequential substitution systems), 894

Clausius, Rudolf J. E. (Germany, 1822–1888)

and thermodynamics, 1019

Clay

in archeology, 1183

self-replication in, 1179

Clebsch–Gordan coefficients

and spin networks, 1055

Cliques

and discrete packings, 987

Clock

and Descartes on complexity, 861

as model of planets, 860

as seed for random generator, 970

Clocksprings

characteristic shapes of, 1183

Closed curve

as origin of repetition, 355

Closed forms, 1133

for 3-body problem, 972

for logistic map, 1098

for nested patterns, 610

see also Exact solutions

see also Formulas

Closed systems

thermodynamics in, 455

Clothes

parametrizations of, 1010

Clothoid curve, 418

Cloud seeding, 992

Cloud streets

discreteness in, 984

as repetitive, 988

Clouds

patterns of, 377

snowflake formation in, 372, 992

turbulent convection in, 1001

and weather prediction, 1178

Club of Rome (world models), 862

Cluster analysis

and Voronoi diagrams, 987

Clusters

in aggregation systems, 332, 978

in diffusion-limited aggregation, 994

in sphere packings, 986

Clusters (in networks), 510, 1039

total numbers of, 1029

CM-1 (Connection Machine) computer, 854

CMOS FETs

and `Nand`

, 1173

CNF (Conjunctive Normal Form), 1095

and satisfiability, 1146