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, 5365
2D, 170181
3D, 182183
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, 231249
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, 638641
conservation laws in, 458, 1023
continuous, 155160
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, 664673
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, 656663
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, 224228
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, 281296
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, 644656, 675
universal 2D, 693
for Voronoi diagrams, 987
weighted totalistic, 427

Cellular automaton fluids, 378382
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

Celtic art, 43, 873

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, 149155
as limit on science, 1135
and Lyapunov exponents in CAs, 950
and my work on CAs, 19
in ODEs, 922
and origin of randomness, 304314
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

Choice
axiom of, 774, 1154

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, 235239
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, 281296
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, 231249
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