# Index

C (programming language)

and chaos experiments, 919

as example of language, 1109

and history of computing, 1108

and my first CA experiments, 864

my use of, 854, 899

programs for CAs, 865

and register machines, 101

C curve

from 1D substitution system, 892

from 2D substitution system, 190

C60

and spherical networks, 1049

Cabala (universal object), 1127

Cabbage

phyllotaxis in, 409

Cable (wire rope)

and nesting in, 874

Cactus

phyllotaxis in, 409

regular shape of, 385

CAD (cylindrical algebraic decomposition), 1154

Caesar, Julius (Italy, 100–44 BC)

and cryptography, 1085

Caesar ciphers, 1085

Cages (small girth networks), 1029

Cahn-Hilliard equation, 980

Calabi-Yau manifolds, 1028, 1052

Calcite

hopper crystals in, 993

Calculators

chaos experiments on, 919

and history of computing, 1107

reverse Polish notation in, 896

Calculus

axioms for, 774

and computational reducibility, 1132

and continuous computation, 1129

equations based on, 161

history of notation for, 1182

and natural selection, 394

origin of word, 925

proofs in, 1177

role in history of science, 44

see also Propositional logic

Calculus of variations

and geodesics, 1049

Calculus ratiocinator

of Leibniz, 1149

California Institute of Technology, xiii

Calligraphy

Kufi, 874

Calls

of birds, 1180

Calogero-Moser model, 1133

Camouflage

stripes of zebras as, 1012

use of randomness in, 1192

and visual perception, 1077

Campbell, John H. (USA, 1938– )

and patterns on shells, 1012

in Preface, xiii

Cams

characteristic shapes of, 1183

for randomness generation, 969

Canalizing behavior (class 2 Boolean networks), 936

Canals

on Earth and Mars, 1180

Cancers

from DNA errors, 970

see also Tumor growth

Cannon balls

packing of, 986

Canonical ensemble

in 2D Ising model, 982

and path integrals, 1061

Canonical forms

establishing axioms with, 1170

in multiway systems, 1036

in proof searching, 1157

and proofs in logic, 1175

see also Confluence

Canonical quantization, 1057

of gravity, 1054

Canonical systems

see Multiway systems

Canons

rules for musical, 875

Cantor, Georg F. L. P. (Germany, 1845–1918)

and Cantor set, 893

and the continuum, 1127

and definition of dimension, 1030

and diagonal arguments, 1128

and digit sequences, 902

and history of numbers, 901

and real numbers, 1153

and set theory, 1154

and transfinite numbers, 1162

Cantor normal form

and Goodstein sequences, 1163

for ordinal numbers, 1162

Cantor pairing function (sigma), 1127

Cantor set

attractors as forming, 959

and CA cardinality, 1128

and CA state space, 869, 958

from continuous systems, 1130

generating function for, 1092

properties of, 890

Sarkovskii's theorem for, 955

and shift registers, 975

spectrum of, 586, 1081

from substitution system, 83

Cantor's diagonal argument, 1127

Capacity (dimension), 959

Capillaries

branching in, 413, 1008

Capital Asset Pricing Model (CAPM), 1015

Caps on sphere

areas of, 1050

Carbon dioxide

and life on Mars, 1180

Cardinality

and the continuum, 1127

Cardinals

as generalizing numbers, 1168

as transfinite numbers, 1162

Cards

shuffling of, 968, 974

for storing programs, 1107

CarmichaelLambda

and linear congruential periods, 974

and quadratic generators, 975

Carnot, Sadi N. L. (France, 1796–1832)

and thermodynamics, 1019

Carpets

and 2D cellular automata, 929

Sierpinski, 188

Carrier frequencies, 835, 1188

Carry digits

in arithmetic, 124

non-locality of, 730

in powers, 1093, 1112

in subtraction, 870

and Turing machines, 760

Cars

engine knocking in, 1194

evolution in, 1003

as randomness analogy, 304

traffic models, 1014

turning tracks of, 418

Cartesianism

and matter in space, 1028

see also Descartes, René

Cartilage

as precursor of bone, 1010

Cartoons

and visual perception, 1076

Cartwright, Mary L. (England, 1900–1998)

and chaos theory, 971

CAs

see Cellular automata

Cascades of eddies, 997

Casimir, Hendrik B. G. (Netherlands, 1909–2000)

and electron model, 1044

Casimir effect, 1062

and uniform spectra, 988

Casinos

and randomness of dice, 969

Castel del Monte

and nested architectural forms, 874

Catalan, Eugène C. (Belgium, 1814–1894)

and iterated aliquot sums, 911

Catalan (Catalan's constant)

and dimer problem, 959

from rational integral, 916

Catalan numbers (Binomial)

and balanced parentheses, 989

and Cantor set, 890

and number of expressions, 897

Catalan's Conjecture, 1166

Catalysis

repeatable randomness in, 976

Catalysts

searching for, 1193

Catastrophe theory

and biological form, 1004

and curved surfaces, 1009

discreteness from, 984

in rate equations, 984

summary of relations to, 12

Catch

and context-free parsing, 1103

and pointer-based encoding, 1071

and testing invariances, 1022

and testing reversibility, 1017

Categoricity

of axiom systems, 799, 1172, 1172'

Category theory

axioms for, 774

history of, 1154

and idealization of math, 1150

and spin networks, 1055

Catenary

characteristic shape of, 1183

as exactly soluble, 1133

Caterpillars

eating paths of, 1011

Catfish

pigmentation pattern of, 426

Cats

patterns in tortoiseshell, 1014

Cauchy functional equation, 953

Cauchy problem

vs. constraints, 940

for general relativity, 1053

Cauchy surfaces, 1041

Cauliflower shape, 385

Causal invariance, 503

and concept of motion, 522, 529

and distributed computing, 1035

and emulated CAs, 1035

and gauge invariance, 527

for networks, 515

and quantum phenomena, 542

in simulating mobile automata, 1034

Causal networks

and cosmology, 1056

curvature in, 534

difficulty of deducing, 493

as directed graphs, 1033

from evolution history, 1033

exponential growth in, 496

and general relativity, 1053

as Hasse diagrams, 1033

history of, 1032

implementation of, 1033

and information transmission, 520

invariance of, 503

loops in, 494

from mobile automata, 488, 1033

from multiway systems, 507

vs. multiway systems, 1037

in network evolution, 514

and perceived spacetime, 516

and posets, 1040

random, 1052

and replacement orders, 501

reversibility in, 495

slices through, 516

from substitution systems, 497

and torsion, 1052

Causality

and Bell's inequalities, 1065

and free will, 1136

Causes

compared to regularities, 352

Caustics

and classical limits, 1059

discreteness from, 984

Cave paintings

interpretation of, 839

purposes of, 1184

recognition of, 874

and visual perception, 1076

Cayley, Arthur (England, 1821–1895)

and group theory, 1153

and iterated maps, 918

Cayley graphs, 938

cellular automata on, 930

and hyperbolic space, 1050

limiting geometry of, 1051

and network constraints, 1032

and sorting networks, 1142

Cayley's theorem

as example theorem, 1159

CCITT compression standard, 1070

CCSR (Center for Complex Systems Research), xiii

CDC 7600 computer, 854

CDMA

and radio signals, 1188

and SETI, 1190

and shift registers, 1086

CDs (compact discs)

bandwidth of, 1079