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