Coal
and interesting chemicals, 1194

Coarse-graining
and defining randomness, 1068
history of, 1020
in thermodynamics, 448

Coarsening
in cellular structures, 1039

Coastlines
origin of shapes of, 1001

Coats of animals
patterns on, 426

Cobol
and history of computing, 1108

Coccolithophorid
shape of, 385

Cocconi, Giuseppe (Italy/USA/Switzerland, 1914–[2008])
and SETI, 1189

Cochlea
and audio perception, 1079

Cochrane, Canada
and patterns from space, 1187

Cockle shell
growth of, 415

Codd, Edgar F. (USA, 1923–[2003])
and universal CAs, 1117

Code
in notes to this book, 854
see also Programs

Code (hash), 622

Code (machine), 101

Code 10
and my CA history, 882

Code 12
and Ulam systems, 929

Code 20
attractors in, 958
as candidate for universality, 1115
excluded blocks in, 958
halting probability in, 964
persistent structures in, 281, 284
transient lengths in, 964

Code 52
as candidate for universality, 692
phase transition in, 981

Code 52 (2D)
domains in, 980

Code 111 (2D)
domains in, 980

Code 177
randomness from, 64

Code 204 (2D)
self-reproduction in, 824

Code 224 (2D)
see Game of Life

Code 237
nesting in, 65

Code 293 (2D)
domains in, 980

Code 294
localized structures in, 526

Code 295 (2D)
domains in, 980

Code 357
persistent structures in, 282, 286
from simple seed, 69

Code 420
as additive CA, 886
nesting in, 63

Code 468 (2D)
isotropy in, 473

Code 600
repetition in, 62, 69

Code 686
and Ulam systems, 929

Code 686 (2D)
isotropy in, 473

Code 746 (2D)
circular shape from, 178, 334, 979
interior of, 929
isotropy in, 473

Code 843
and computational reducibility, 738

Code 867
examples based on, 868

Code 870
and computational reducibility, 738

Code 912
randomness in, 64

Code 920 (2D)
domains in, 980

Code 942 (2D)
nested pattern from, 171
slices through, 928

Code 948
nesting in, 65

Code 976 (2D)
domains in, 336, 980
phase transition in, 340

Code 1041
complex behavior in, 66

Code 1329
persistent structures in, 282
from simple seed, 62

Code 1599
complex behavior in, 69, 70
and computational irreducibility, 738, 740
and free will, 750

Code 1635
complex behavior in, 66, 67

Code 1659
class 4 behavior in, 238

Code 1749
nesting in, 65

Code 1815
class 4 behavior in, 236
and universality, 692

Code 1893
localized structures in, 526
nested domains in, 360

Code 2007
class 4 behavior in, 237

Code 2040
randomness in, 64

Code 2043
class 4 behavior in, 239

Code 2049
complex behavior in, 66, 68

Code 2058
from simple seed, 69

Code 3702 (2D)
examples based on, 868

Code 29408
shape produced by, 980

Code 174826
shape produced by, 929, 980

Code 175850
shape produced by, 980

Code 1004600
and undecidability, 754, 1137

Code books
and cryptography, 1085
in sound compression, 1080

Codes
error-correcting, 1101
Huffman, 564
Shannon–Fano, 1069
for totalistic CAs, 60
for Turing machines, 888
see also Cryptography

Codewords
in block encoding, 563
in error-correcting codes, 1101
self-delimiting, 1071

Coding theory
algebraic, 1101
and block emulations, 1119

CoefficientList
and Sierpiński pattern, 931

Coffee grains, 986

Cognition
see Thinking

Cogs
characteristic shapes of, 1183

Cohen, Paul J. (USA, 1934–[2007])
and continuum hypothesis, 1155

Coherence
and definition of purpose, 830
and human will, 1136

Coherent states (in quantum theory), 1059

Coherent structures
in QCD, 1061
in turbulent fluids, 997
see also Localized structures

Coiling
in animals, 413

Coin tossing
randomness from, 305, 971
in water, 971

Coincidences
and randomness, 967

Coins
maze patterns on, 873
packing of identical, 349

Cold War
and beliefs about SETI, 1191

Collagen
repetitive structure of, 1003

Collatz problem, 904
see also 3n+1 problem

Collect
analog in Boolean formulas, 1095

Collective behavior
general theory of, 3

Collectives
and defining randomness, 1068

Collisions
and chaos theory, 971
on inspirational cover, 17
law for in rule 110, 964
of planets, 973
in rule 110, 684
of structures in rule 110, 294
and thermodynamic model, 445

Colonization of galaxy, 839

Color
and pictures in this book, 851
vision, 577, 1074

Color charges
and QCD, 1057

Coloration of animals, 426, 1012

Coloring of networks, 1029, 1031

Combinatorial chemistry, 1193, 1194

Combinatorial optimization, 985

Combinatorial physics, 1027

Combinatorial topology, 1051

Combinatorics
posets in, 1041
and substitution systems, 893
undecidability in, 1138

Combinators
behavior of, 712
emulating cellular automata, 1123
emulating rule 110, 713
halting in, 897
history of, 1121
and history of universality, 1110
as idealization of math, 1150
and network systems, 936
as precursors to my work, 879
properties of, 1122
single universal, 1123
and symbolic systems, 102, 898
as symbolic systems, 711
as universal systems, 711
and variables in axioms, 1156

Combinatory algebra, 1172

Comet orbits
and Gaussian distribution, 977

Common subexpressions
in equation solutions, 945
in multilevel logic, 1096
and networks, 1040
and speedups, 1094

Communication
animal, 1180
between computers, 1182
and definition of intelligence, 826
of effects in CAs, 252
with ETs in science fiction, 1191
theories of, 1181
and use of language, 630

Communications systems
and data compression, 549, 560
and layout of networks, 1031
and shift registers, 878
simulations of, 968
and theories of communication, 1181

Commutative
see Orderless

Commutative Boolean functions, 1173

Commutative diagrams
in category theory, 1154

Commutative groups
axioms for, 773, 1153
decidability for, 1160
enumeration of, 805
and forcing by axioms, 1172
incompleteness of theory, 1160
shortest axioms for, 806
total number of, 1172
see also Abelian groups

Commutative monoids
enumeration of, 952
and generalized additivity, 952

Commutative rings, 1153

Commutative semigroups
Cayley graphs of, 938
enumeration of, 805, 1173
word problems in, 1141

Commutativity
of And, 817
and generalized additivity, 952
in operator systems, 801
of Or, 817
proof in Nand axioms, 775
and speedups in evolution, 1095
unprovability in reduced arithmetic, 800

Commuting operations
and causal invariance, 1036

Companding
in sound compression, 1080

Comparative anatomy
and studies of form, 967

Competition
between programs, 1105
in phase transitions, 983

Compile
and CA evolution, 865

Compiled languages, 1109

Compiler generators, 1104

Compilers
for functional languages, 898
optimal code searches in, 1193
and register machines, 1114

Compiling
see Emulation

Complement
and finite set theory, 1171

Complement cellular automaton, 883

Complete bases
for data, 1072
for logic, 1173

Complete graphs
and planarity tests, 1045

Completely connected sets
and discrete packings, 987

Completeness
vs. Incompleteness Theorem, 1159
meanings of, 1152
in multiway systems, 782, 797
of number representations, 1070
in predicate logic, 1152
of real algebra, 1154
see also Universality (computational)

Completeness theorem
for equational logic, 1172
for first-order logic, 1167

Completion
algorithms for, 1037
and automated proofs, 1158
in multiway systems, 782

Complex analysis
and growth shapes, 1010
and S matrix theory, 1057

Complex bases, 932

Complex maps, 933

Complex numbers
and branching patterns, 1005
cellular automata based on, 886
as defining poset, 1041
and multiway systems, 939
not related to complexity, 1069
as number generalizations, 1168
powers of, 1094
and Sierpiński pattern, 931

Complex plane
nested patterns in, 1093

Complex rules
with simple behavior, 351

Complex systems research
and defining complexity, 1069
history of, 20
organizational structure of, 862

Complexity
adaptive value of, 1002
and animism, 845
applications of, 841
biology as prime example of, 383
in biology vs. thermodynamics, 1003
compared to randomness, 557
definition of, 557–559
and definition of life, 824
explaining in biology, 396
explaining phenomenon of, 735–737
formula size as measuring, 1096
history of definitions of, 1068
of human thinking, 628
of individual integers, 916
ingredients for, 1131
limited by natural selection, 392
as limited in biology, 391
of logic circuits, 1096
and lossy compression, 574
of math formulas, 1068
in mathematics, 772
in models, 364
mystery of in nature, 2
and Principle of Computational Equivalence, 719
of proofs in math, 777
from random initial conditions, 228
in rule 110, 39
and science, 861
as special to humans, 844
and theology, 861
of Turing machine rules, 1119
in Turing machines, 709
and universality, 643

Complexity engineering, 882

Complexity theory
history of, 862
summary of relations to, 13

Complexity theory (computational complexity theory), 1142

Composite heads
in symbolic expressions, 896

Compositeness
of elementary particles, 1044

Composition (music)
with substitution systems, 1080

Compositions
of cellular automata, 886
of functions, 896
of polynomials in iterated maps, 1098

Compound leaves, 1005

Compounds
chemical, 1194

Compressible flow (in fluids)
see Supersonic flow

Compression
audio, 1080
of CA patterns, 562
and computational reducibility, 746, 1134
and computer communication, 1182
of data, 560–576
in extraterrestrial signals, 836
lossy, 572
maximal in block encoding, 1071
in mobile automata, 72, 488
and recognition of meaning, 827
software for, 1069

Compton scattering, 1060

Computability
see Decidability

Computable reals, 1128

Computation
analog, 730, 1128
in cellular automata, 638–641
as conceptual foundation, 5
continuous, 730, 1128
efficiency of, 758
math notation for, 1182
minimal systems for specific, 832
not for definite tasks, 715
notion of, 637–714
reversible, 1018
and thermodynamic behavior, 444
thermodynamics of, 1018, 1020
universality as basis for study of, 674
see also Computing
see also Programs

Computation universality
history of, 1109
see also Universality

Computational complexity theory, 758, 1142
and computational irreducibility, 1132
of computing π, 912
and defining randomness, 1068
and definition of complexity, 1069
of math function evaluation, 1134
and Principle of Computational Equivalence, 766
summary of relations to, 14

Computational Equivalence, Principle of, 715–846
see also Principle of Computational Equivalence

Computational fluid dynamics, 1000
and Navier–Stokes , 996

Computational geometry
and nearest neighbors, 1101
recursive algorithms in, 1142
and Voronoi diagrams, 987

Computational irreducibility, 737–750
and chemistry, 1193
and complexity, 748
and computational complexity theory, 1148
and epistemology, 1196
and extraterrestrial trade, 1191
and free will, 750
and Gödel's Theorem, 788
history of, 1132
and human responsibility, 1136
and intractability, 758
introduction to, 6
and limits of science, 1135
in mathematics, 779
my discovery of, 881
in operator systems, 815
origins of, 1133
and Principle of Computational Equivalence, 738
in QED, 1060
and three-body problem, 972
ubiquity of, 745
and weather prediction, 1178

Computational learning theory, 1102

Computational neuroscience
and visual perception, 1076

Computational reducibility, 738
in additive CAs, 1094
and associative evolution, 1094
as basis for existing science, 741
and compression, 746
and engineering, 829
and exact solutions, 1133
examples of, 744, 747
in network of theorems, 821
and regularities, 746

Computational science, 44

Computational work
and computational irreducibility, 739

Computer-aided design (CAD)
and discrete surfaces, 1050

Computer algebra
and computer experiments, 899
and Feynman diagrams, 1057
and gravity theory, 1048
see also Algebraic computation

Computer art, 11

Computer-assisted proofs
see Automated theorem proving

Computer experiments
basic, 23
and chaos theory, 899
and computational irreducibility, 1132
and continuous systems, 167
and ergodicity, 1020
and iterated maps, 919
lack of meaningful, 898
and learning about this book, 856
methodology of, 108–113
my first on CAs, 880
my need to do more, 20
on natural selection, 1002
problems with chaos in, 919
and solitons, 899
and symbolic computation, 899
and theorems, 899
for this book, 46, 111, 854

Computer graphics
and discrete surfaces, 1050
and history of modelling, 992
and models of plant growth, 1005
and models of shell shapes, 1008
and nesting, 934
and substitution systems, 893
surface roughness in, 996
textures in, 1077
use of randomness in, 841, 1192

Computer interfaces
graphical vs. language, 631
history of, 1102

Computer languages
and context-free grammars, 939
and history of computing, 1108
and human thinking, 627
influence on thinking of, 1181
logic primitives in, 1173
and P equivalence, 764
redundancy in, 1086
and universality, 642
see also Languages (computer)

Computer programs
in notes, 853
see also Programs

Computer science
education and this book, 855
structure of algorithms in, 990
summary of relations to, 10, 863
undecidability in, 1138

Computer simulations
see Simulations

Computerized data taking, 992

Computers
communication between, 1182
and definition of intelligence, 822
and discoveries in this book, 46
free will for, 1135
future of, 1196
future technology of, 841
historical cost of using, 45
and history of CAs, 876
physical components in, 1195
quantum, 1147
randomness in, 970
and rule-based systems, 860
and universality, 642
used in creation of book, 854

Computing
causal invariance in distributed, 1035
history of, 1107
intuition from, 40, 46, 872
number representations in, 1070
see also Computation