# Index

Concatenation

as semigroup operation, 938, 1172

Concatenation sequences, 913

block statistics in, 594

continued fractions for, 915

difficulty of CAs producing, 1186

and pointer-based encoding, 1072

sounds from, 1080

Conchoids (math curves), 875

Concurrent systems

and causal invariance, 1035

Condensates

topological defects in, 1045

Conditional entropies

and texture discrimination, 1077

Conditional probabilities

and Bayes's theorem, 1083

Cone cells

in color vision, 1074

Cone shells

growth of, 414

neurotoxins from, 1011

patterns on, 423

Cones

in Lorentzian spaces, 1051

Confinement in QCD, 1061

Confluence, 1036

for combinators, 1122

and generalized aggregation rules, 979

getting using completion, 1037

in multiway systems, 507

in symbolic systems, 1113

see also Canonical forms

see also Church-Rosser property

Conformal mappings

and flatness in growth, 1007

and hypergeometric functions, 1092

and transformation of biological forms, 1010

Conformal transformations

and gauge invariance, 1045

Conformations of proteins, 1184

Congruence

in axioms of geometry, 1154

Conifers

branching in, 1004

Conjugacy

in additive systems, 952

and CA conservation laws, 1023

in iterated maps, 921

Conjugate systems

and reversible cellular automata, 961

Conjunction

as name for And, 1173

Conjunctions

in human languages, 1173

starting sentences with, 849

as words for logic functions, 1173

Conjunctive Normal Form (CNF), 1095

and resolution method, 1157

Connected clusters

in percolation theory, 983

Connection Machine computer

my use of, 854, 881

Connections (on fiber bundles), 1045

Connectives

possible Boolean, 806

in well-formed formulas, 1150

Connectivity

of branching patterns, 1006

in network evolution, 1039

of networks, 1029

Conscious thinking

and free will, 1135

in visual perception, 582

Consciousness

and quantum theory, 1058, 1063

see also Intelligence

see also Thinking

Conservation laws, 458-464

in cellular automaton fluids, 379

finding in CAs, 1022

for particles in 2D CA, 445

in PDEs, 923

in physics, 1022

for quantum probabilities, 1059

in three-body problem, 972

topological, 1045

undecidability of, 1138

for vector quantities, 1024

Conserved quantities

from algebraic structures, 1023

Conserved traits, 395

Consistency

of arithmetic, 1160, 1163

of axiom systems, 1168

in multiway systems, 797

Consistency of action

and human will, 1136

Consonants

sound of, 1079

and soundex system, 1100

Constancy

color, 1074

Constancy (K) combinator, 1121

Constants

mathematical, 136-144

in operator systems, 1169

Constants of motion

in three-body problem, 972

see also Conserved quantities

Constellations

patterns of, 583, 1187

and SETI, 1189

Constraints

in 1D systems, 940

axioms as, 803

as basis for uniformity, 354

biological schemes for satisfying, 985

and concept of purpose, 829, 1185

in correspondence systems, 1139

Darwinian evolution and, 386

defining networks using, 483

as determining spacetime networks, 482

difficulties in modelling with, 368

enumerating cases satisfying, 959

and mathematical thinking, 1177

vs. mechanisms, 940

in multiway systems, 766

as NP problems, 1142

on operators, 1172

PDEs as, 923

for periodic behavior in CAs, 954

and Principle of Computational Equivalence, 729

probability of violating, 343

problem of satisfying, 342-351

producing complexity with, 351

proofs as systems based on, 1157

and quasicrystal growth, 994

in random systems

see Markov random fields

rule 30 repetition as, 266

satisfied by operators, 805

self-assembly and, 1011, 1193

systems based on, 210-221

undecidability of satisfying, 756

and undecidability of tiling, 1139

Constructibility

and intuitionism, 1158

Constructible reals, 1129

Constructions

of 48-gon, 873

vs. computer experiments, 108

and purposes, 830

rules in geometrical, 875

of universal CA, 648, 675

Constructive proofs

and computer experiments, 899

Consumer electronics

use of randomness in, 1192

use of statistics in, 1082

Contact (movie)

extraterrestrial contact in, 1190

Context

and recognition of purpose, 830

and theories of communication, 1181

Context-free languages, 939, 1103

math notation as, 1182

parentheses and, 989

patterns generated by, 1091

PCP and, 1139

pumping lemma for, 944

random, 1084

rule 184 as recognizing, 1109

undecidability in, 1137

Context-sensitive languages, 939

Continental drift

as non-math theory, 859

Continued fraction map (Gauss map), 914, 955

Continued fractions, 143, 914-915

and billiard systems, 971

computation of, 914

and digital slopes, 916

and encoding of reals, 1127

generalized, 914

history of, 915

and iterated maps, 919

and multiplication systems, 903

and Pell equation, 944

and phyllotaxis, 411

as precursors to my work, 878

and quadratic Diophantine equations, 1164

and sine curves, 147

ContinuedFraction, 914

see also Continued fractions

Continuity

and axioms of topology, 1155

of CA mappings, 869

and confusion about Gödel's Theorem, 1132

and the continuum, 1127

and difficulty of computer experiments, 899

discreteness from, 337

in genetic programs, 1002

in geometry axioms, 1154

and mathematical intuition, 925

in natural selection and engineering, 394

nesting as historical counterexamples in, 934

origins of, 327-336, 463-464

origins of in fluids, 379

and Principle of Computational Equivalence, 729

of space, 472

Continuous cellular automata, 155-160

additive, 1092

cardinality of, 1128

classification of, 948

history of, 921

implementation of, 921

as models of boiling, 994

as models of phyllotaxis, 1007

and probabilistic rules, 976

for quantum mechanics, 1059

with random initial conditions, 243

Continuous computation, 730, 1128

Continuous functions

additivity of, 953

cellular automaton maps as, 961

evaluation of, 1134

number of, 1127

Continuous models

of crystal growth, 993

of fracture, 995

Continuous Pascal's triangle, 922

Continuous systems

and Church's Thesis, 1126

vs. discrete systems, 167

emulating discrete, 731, 1129

isotropy in, 980

in physics, 729

and undecidability, 1138

Continuous truth values, 1175

Continuous variables

invention of, 901

models with, 368

Continuum, the, 1127

Continuum equations

see Partial differential equations

Continuum Hypothesis, 1127

in set theory, 1155

and truth from incompleteness, 1167

unprovability of, 1163

Continuum limits

different forms of, 1023

for diffusion equation, 1024

of networks, 1030

Contours

in landscapes, 1001

in visual perception, 578

Contractive mappings, 277, 959

Contradictions

and proofs of undecidability, 1137

as scheme for proofs, 1177

Control theory

and artificial intelligence, 1099

and complex behavior, 841

and cybernetics, 862

time series in, 1083

Convection, 1000

and history of pattern, 947

maze patterns in, 1013

patterns of, 377

repeatable randomness in, 976

repetitive cells in, 988

and snowflake development, 372

Convention in languages, 1181

Convergence

of fractal dimensions, 933

of isotropy in finite differences, 980

of iterated maps, 918

of metric expansion, 1050

in multiway systems, 507, 1036

in natural selection, 392

in negotiation processes, 430

of PDE solutions, 924

in plant phyllotaxis, 410

Convergent evolution, 397

Convergent series

as exact solutions, 1133

Conversation

and defining intelligence, 1178

Convolution

in visual perception, 1075, 1076

see also ListConvolve

Convolutional codes

and CA encodings, 1119

Conway, John H. (England/USA, 1937– )

and 2D Turing machines, 930

and arithmetic recurrences, 1115

and Game of Life, 877, 880, 949

and iterated run-length encoding, 905

and non-periodic tilings, 943

in Preface, xiii

and recursive sequences, 907

and universality of Life, 1117

Cook, Matthew (USA, 1970– )

and cyclic tag systems, 895

and polyomino tiling, 943

in Preface, xii

and rule 110, 1115

Cook, Stephen A. (USA/Canada, 1939– )

and NP completeness, 1143

Cooking recipes, 1193

Cooley-Tukey transform, 1074

Cooperation

theories of evolution of, 1104

Coordinate singularities

in general relativity, 1048, 1053

Coordinates

and multiway strings, 1036

for network nodes, 478

Copernican astronomy

and extraterrestrial life, 1180

and history of gravity, 1047

vs. ideas of this book, 844

Copy operations

and Nand expressions, 1096

Coral

as animal artifacts, 1184

Coral reefs

symmetry of, 1187

Coralbells (plant), 1006

Córdoba, Great Mosque of, 873

Core collapse

in self-gravitating systems, 1021

Core memory

of early computer, 864

Cores

of elementary particles, 527

Corn

structure of, 385

Corner-overlapping patterns, 941

Corners

in code 976, 980

Cornu spiral, 418

Corollaries

defining features of, 1176

Coronas (in splashes), 988, 1000

Corpuscular theories, 876, 1024

Correlation entropy, 959

Correlations

in 2D Ising model, 982

and Bell's inequalities, 1064

between digits, 902

and CA difference patterns, 950

in CA evolution, 953

in class 3 CAs, 949

and defining communication, 827

and defining complexity, 1069

in DNA sequences, 1184

in H theorem, 1020

in human languages, 1086

in noise with given spectrum, 969

and non-standard diffusion processes, 1024

in phase transitions, 989

in quantum theory, 543

in random environments, 304

and random networks, 1039

in random patterns, 584

and randomness tests, 595, 1085

and spectra, 587, 1082

in stirring and shaking, 969

in visual textures, 1078

see also ListCorrelate

Correspondence systems (PCP)

NP completeness in, 1145

and undecidability, 757, 1139

Corrugation

in ammonite septa, 1008

in animal development, 418

characteristic shape of, 1183

in tissue sheets, 413

Cortex

auditory, 1079

sensorimotor, 1099

visual, 580

Cos (cosine)

and area of circle on sphere, 1050

and Bell's inequalities, 1064

and limit of 6j symbols, 1055

and logistic map formulas, 1098

and nested radicals, 915

and tent map, 919

Cosets

and state transition graphs, 963

Cosh

in solution of catenary, 1133

in solution of logistic map, 1098

Cosine transform

in data compression, 1070, 1074

Cosmas (Italy, ~1210 – ~1235)

and mosaic patterns, 873

Cosmati mosaic work, 873

Cosmic microwave background

and alignment of time, 1022

as analog of ether, 1042

and galaxy formation, 1021

and history of gravity, 1048

and initial conditions, 1026

origin of uniformity of, 1055

as source of radio noise, 1187

Cosmic rays

particles produced by, 1044, 1047

as possible artifacts, 1187

Cosmological principle (uniformity of universe), 1055

Cosmological term (in Einstein equations), 1052

and inflationary universe, 1055

and vacuum solutions, 1053

Cosmology

and Anthropic Principle, 1185

basic issues in, 1055

and Einstein equations, 1053

and ether in, 1042

formation of galaxies in, 1021

and history of gravity, 1048

my work in, 17, 864

network models of, 1056

and Second Law, 1020, 1021

and simple initial conditions, 1026

topological defects in, 1045

see also Universe

Cot (cotangent)

and shift map, 919

Coth

continued fraction for, 914

and solution of Ising model, 982

Countable models

of operator systems, 1172

Counter

Turing machine acting as, 888

Counter machines (register machines), 97-102, 896

Counterfactuals (quantum values), 1064

Counterpoint

rules of musical, 875

Countries

of people in the index, 852

Coupled map lattices, 155-160, 922

see also Continuous cellular automata

Coupling constants

in quantum field theory, 1057

and renormalization group, 955

Coupon collector's test, 1085

Courant condition (for PDEs), 924

Covalent forces

and virtual electrons, 1060

Cover

of inspirational book, 17, 864

of this book, 851

Covers

in Boolean minimization, 1095

Cow parsley

shape of, 385

Cowe, Russell J. (UK, 1946– )

and shell patterns, 1012

Cowfish

pigmentation pattern of, 426

Cowrie shells

growth of, 415, 1008

patterns on, 1012

CP violation (time reversal violation), 1019

CPT invariance, 1019