# Index

Crackling

in natural radio emissions, 1187

Cracks

nesting of, 988

randomness of, 374

Craters

circular shapes of, 1187

as landscape elements, 1001

Creation myths

as models, 992

Creeping flow, 377

Crete

maze at Knossos on, 873

Criminal law

free will in, 1135

Crinkling

patterns of, 996

Critical exponent

in 2D Ising model, 982

Critical pairs

in completion algorithms, 1037

Critical phenomena

and nesting, 989

and phase transitions, 981

and scale invariance, 955

Crossovers

in genetics, 970

Crosstalk

and Walsh functions, 1073

Crowds

motion of people in, 1014

Crumpling

patterns of, 996

Crushing (of solids), 995

nesting in, 988

and sphere packing, 986

Crust (of Earth)

and origin of life, 1179

patterns on, 1001

Crutchfield, James P. (USA, 1955– )

and Markov models, 1084

in Preface, xiii

Cryptanalysis

of additive cellular automata, 601

and dead languages, 1185

and defining randomness, 1068

history of, 1086

and history of computing, 1107

of linear congruential generators, 1089

and meaning of programs, 1183

and rule 30 NP completeness, 770

of shift registers, 1087

of Vigenère ciphers, 599

Cryptography, 598-606

as application of randomness, 1192

and defining randomness, 1068

with digit sequences, 1089

electronic randomness for, 968

as example of technology, 840

and hashing, 1100

history of, 1085

and history of complexity, 49

as process based on rules, 875

quantum, 1058

random keys for, 970

and recognizing meaning, 827

and shift registers, 878, 1086

Crystal growth, 369-373

history of, 993

models of, 993

Crystal lattices

systems on, 169, 929

Crystals

as artificial-looking, 828

Brillouin zones in, 988

diffraction patterns in, 1082

effect of seeds on, 992

formation as phase transition, 983

fracture in, 374

hopper, 993

lack of continuum limit for, 327

as not artifacts, 1183

randomness in shapes of, 373

as self-organizing systems, 824

shapes of, 929

trivalent network and, 1030

Csc (cosecant)

and Moire patterns, 1078

Cube-free sequences, 944

Thue-Morse and, 890

Cube network, 476

transformed to tetrahedron, 1038

Cube roots

and Cantor set generating function, 1092

digits of, 141

Cubes

equations involving sums of, 945

produced by CAs, 1186

Cubic equations

and computational reducibility, 1132

Diophantine, 1164

as exactly soluble, 1133

iterative solutions to, 1101

size of solutions to, 945

Cubic graphs

see Networks, trivalent

Cubic lattices

cellular automata on, 182

class 4 rules on, 949

as crystal lattices, 929

random walks on, 977

Voronoi diagrams for, 987

Cuboid

and 3D cellular automata, 927

Cucumber leaves, 1006

Cultural relativism

not connected to relativity, 1042

Culture

and character of perception, 635

and defining intelligence, 1178

and recognizing intelligence, 825

and response to events, 827

Curie point

in Ising model, 981

Curl

and vector potential, 1045

Curry, Haskell B. (USA, 1900–1982)

and combinators, 898

Currying

and combinators, 1122

of function arguments, 896

Curvature

of curves, 1049

curves defined by, 418, 1009

in differential geometry, 1048

of fronts in crystal growth, 993

gauge fields as, 1045

of growing tissue, 1007

higher-dimensional, 1009

in non-integer dimensions, 1051

in plant growth, 412

in rivers, 1001

singularities in, 1053

Curves

curvature of, 1049

Lissajous, 917

mathematical, 145-148

space-filling, 893

Cusps

in light caustics, 984

Custering

in 2D cellular automata, 877

Cut elimination in proofs, 1155

Cuttlefish

communication by, 1181

pigmentation pattern of, 426

Cybernetics

and biology, 1004

and computational irreducibility, 1132

and definition of complexity, 1068

and free will for machines, 1135

history of, 862

and models of thinking, 1099

as precursor to my work, 879

and self-reproduction, 1179

summary of relations to, 14

Cycles

in attractors, 958

longest in networks, 1029, 1031

in random networks, 963

and repetition periods, 950

in shift rules, 963

shortest in networks, 1029

in state transition graphs, 961

Cyclic

see Repetitive

Cyclic addition systems, 255, 950

state transition graphs for, 961

Cyclic boundary conditions

in CA implementation, 866

periods in CAs with, 950

Cyclic groups

decomposition into, 1172

Cyclic multiplication, 257, 950

state transition graphs for, 961

Cyclic negation

in multivalued logic, 1175

Cyclic shift instructions, 951

Cyclic subgroups

and nested patterns, 956

Cyclic tag systems, 95

emulated by rule 110, 678

emulated by tag systems, 1113

emulating cellular automata, 668

emulating tag systems, 669, 1116

generalizations of, 895

implementation of, 895

mechanical version of, 895

and pointer-based encoding, 1071

random initial conditions in, 949

randomness generation in, 920

vs. shift registers, 1088

Cyclones (in weather), 1178

Cyclotomic (cyclotomic polynomials)

and shift register periods, 975

and solution of logistic map, 1098

Cylinders

in curved space, 1050

and definition of Ricci tensor, 534

fluid flow past, 996

Cylindrical algebraic decomposition, 1154

Cypress leaves, 1006