# Index

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 pi, 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