# Index

s

sound of letter, 1079

S expressions

number of, 989

S matrices

and discrete quantum mechanics, 1060

in particle physics, 1057

S_{3} (group)

CA based on, 887, 956

as first non-commutative group, 1172

Saccadic eye movements, 1192

Sagan, Carl E. (USA, 1934–1996)

and Pioneer 10 plaque, 1189

Sahara desert

Richat structure in, 1187

Salamander

pigmentation pattern on, 426

Salem, James (USA, 1962– )

as coauthor of paper, 882

in Preface, xiii

Salt

hopper crystals in, 993

Salt Lake

features seen from space, 1187

Sand

apparent continuity of, 327

and Chladni figures, 984

fluid phenomena in, 1001

patterns from wind in, 1183

settling in, 986

Sand dunes

maze-like patterns in, 1013

repetitive patterns of, 1187

and waves on sand, 1001

Sander, Leonard M. (USA, 1941– )

and diffusion-limited aggregation, 994

in Preface, xiii

Sandpile model, 989

Sanskrit

rules in grammar for, 875

Sapir–Whorf hypothesis

and communication, 1181

and math in science, 860

Sarkovskii's theorem, 955

Satisfiability

with 2 and 3 variables, 1146

density of difficult instances of, 1147

emulating Turing machines, 1146

NP completeness of, 767

and proof lengths in logic, 1175

and quantum computers, 1148

Satisfying constraints, 210–221

problem of, 342–351

see also Constraints

Saturn

and extraterrestrial life, 1179

Saussure, Ferdinand de (Switzerland, 1857–1913)

and concept of language, 1181

Saws

characteristic shapes of, 1183

Sawtooth functions

and Thue–Morse sequence, 1081

Scalar curvature, 533

see also Ricci scalar curvature

Scales (in music), 917

Scales (mathematical)

in continuum limit of networks, 1030

and fractal dimensions, 933

see also Limits

Scales (of animals)

coloration of, 1012

phyllotaxis-like patterns in, 1007

Scaling

in additive cellular automata, 270

and dimension, 933

of eddy sizes in turbulence, 997

and origins of nesting, 357, 989

and renormalization group, 955

of visual perception, 1076

see also Nesting

Scanning probe microscopy

and crystal surfaces, 993

for nanotechnology, 1193

Scapula (shoulder blade)

for fortune-telling, 968

Scents

odors in, 1105

Schemas (axiom), 1156

and finite axiomatizability, 1176

Schemas for algorithms, 990

Schickard, Wilhelm (Germany, 1592–1635)

and origin of computers, 1107

Schild ladder, 1051

Scholasticism

and argument by design, 861

and history of logic, 1099

Scholes, Myron S. (USA, 1941– )

and options pricing, 1015

Schönfinkel, Moses I. (Germany/Russia, 1889 – ~1942)

and combinators, 879, 1121

and origins of universality, 1110

and single combinators, 1123

and symbolic systems, 898

Schoute, Johannes C. (Netherlands, 1877–1942)

and phyllotaxis, 1007

Schreger lines

in mammoth dentin, 873

Schröder, F. W. K. Ernst (Germany, 1841–1902)

and axioms of logic, 1151

Schrödinger, Erwin R. J. A. (Austria/Switzerland/Germany/Ireland, 1887–1961)

and quantum mechanics, 1056

Schrödinger equation

discretization of, 1060

as example of PDE, 161

and gauge invariance, 1045

lack of chaos in, 1063

and nested potentials, 1081

and path integrals, 1057

Schroeder diffusers

quadratic residue diffusers, 1183

Schwarzschild, Karl (Germany, 1873–1916)

and Einstein equations, 1053

Schwarzschild solution, 1130, 1133

Science

education, 855

limits to, 6, 748, 1135, 1196

math as foundation of, 859

Science Citation Index

papers on CAs in, 878

Science fiction

and artificial intelligence, 1099

and extraterrestrials, 1180, 1190

and extraterrestrials in 2001, 1183

and free will for computers, 1135

and messages in DNA, 1184

and parallel universes, 1035

robots in, 629

and universe as computer, 1026

*Scientific American*

article of mine in, 881, 882

and CA universality proofs, 1115

and history of CAs, 877

Scientific computing

fundamental issues in, 1133

history of, 1107

summary of relations to, 16

Scientific experiments

repeatability of, 326

Scientific literature

models in the, 368

Scientific pantheism, 1196

Scoping of variables, 1150, 1152

Scores (musical), 1080

Screw dislocations, 993

Screw shell, 1008

Screws

characteristic shapes of, 1183

Scribbles

as source of randomness, 970

Scroll patterns, 872

Sea urchin

form of, 385

Search-and-replace systems, 88

see also Sequential substitution systems

Search trees (backtracking), 1089

Searching

for axioms of logic, 1174

for cryptographic keys, 603

Darwinian evolution as, 386

for doubling CAs, 1185

to find examples for this book, 111, 393

for non-periodic tilings, 220

for optimal cellular automata, 834

for proofs, 1157

to satisfy constraints, 343, 941

in technology development, 842, 1193

for ultimate theory of physics, 466

`Sec`

(secant)

curve of, 145

`Sech`

in solution of KdV equation, 1133

in solution of Toda lattice, 1133

Second Law of Thermodynamics, 441–457

avoided by rule 37R, 453

character of as principle, 1126

and cosmology, 1021

and definition of life, 1178

history of, 1019

limitations of, 451

and microscopic instability, 1020

and my work on CAs, 880

and open systems, 455

and quantum measurement, 1063

and radiation, 1021

and self-organization, 947

textbook treatments of, 1020

Second-order logic, 1167

and arithmetic axioms, 1152

Second-order phase transitions, 981

Secrecy systems

see Cryptography

Security envelopes

randomness in, 1192

Security systems

cryptographic, 598

and recognizing artifacts, 1183

`SeedRandom`

, 973

Seeds

for crystals, 369

for random generators, 970

Segmentation in animals, 417

Segregation diagram (for I Ching), 893

Séguier, Jean-Armand de (France, 1862–1937)

and semigroups, 1153

Seiberg–Witten model

as exactly soluble, 1133

Sejnowski, Terrence J. (USA, 1947– )

and neural networks, 1100

in Preface, xiii

Sekerka, Robert F. (USA, 1937– )

and dendritic growth, 993

Select (select elements)

basic example of, 853

Selection

see Natural selection

Selective availability (timing encryption in GPS), 1086

Self-adjoint approximations

and second-order CAs, 1018

Self-avoiding walks, 978

Self-delimiting digit sequences, 560

Self-energy

and corrections to mass, 1046

of electron, 1044

in QED, 1057

Self-gravitating systems, 1021

and my work on CAs, 880

and Voronoi diagrams, 987

Self-limiting growth

in plants, 1006

Self-organization, 223

and attractors, 275

and definition of life, 824

and gravitational systems, 1021

history of, 947

and history of complexity, 862

and persistent structures, 282

and reaction-diffusion, 1013

and rule 37R, 455

and Second Law, 1021

summary of relations to, 16

Self-organized criticality, 989

confusion about, 969

Self-reference

and Gödel's Theorem, 1159

and proofs of undecidability, 1137

see also Recursion

Self-reproduction

and cellular automata, 961

and definition of life, 824, 1178

history of, 1179

and history of CA universality, 1117

and history of CAs, 876

Self-similarity

and *1/f* noise, 969

in cellular automata, 58

and dimension, 933

of Gaussian distribution, 977

in growth of shells, 414, 1008

history of, 934

in networks, 509

origin of in additive CAs, 270, 955

origins of, 357–360

with random initial conditions, 273

in rule 90, 25, 870

in substitution systems, 83

see also Fractals

see also Nesting

Semantics

and semiotics, 1181

Semi-Thue systems

see Multiway systems

Semiconductor devices

*1/f* noise in, 969

randomness in, 303, 970

Semiconductors

as components in technology, 1195

crystal growth of industrial, 993

and history of computing, 1108

Semigroups

axiom for, 773

CAs based on, 886, 956

constraints defining, 945

enumeration of, 805

history of, 1153

and invertible multiway systems, 1018

Krohn–Rhodes decomposition of, 1069

and multiway systems, 938, 1172

and nesting in associative cellular automata, 956

number of, 945

undecidability of equivalence of, 1138

undecidability of word problem for, 1136

universality of, 1159

word problem for, 1141

see also Commutative semigroups

Semilattices, 1171

Semiotics, 1181

Sensitive dependence

on angles in plant phyllotaxis, 412

on branching parameters, 405

in cellular automata, 250–254

and computational irreducibility, 1133

in fluid flow, 381

and free will, 1135

and history of chaos theory, 971

vs. intrinsic randomness, 261, 322

in iterated maps, 153

in Lorenz equations, 998

in ODEs, 922

as origin of randomness, 309–314

in quantum mechanics, 1063

of snowflakes on seeds, 992

and weather prediction, 1178

see also Chaos theory

Sensorimotor cortex, 1099

Sensory input

and perception, 1105

and thinking, 1098

Sentences (in human languages), 1103

Sentential calculus

see also Logic

see also Propositional calculus

Septa

in chambered shells, 1008

Septic (degree 7) equations, 1132

Sequence homomorphisms (substitution systems), 893

Sequences

analysis of

see Analysis

encoded as integers, 1120

integers as fundamental, 1152

practical methods for studying, 1091

recursive, 128–131

see also Digit sequences

see also Lists

Sequencing of events in universe, 497

Sequency order

for Walsh functions, 573, 1073

Sequential automata

see Mobile automata

Sequential cellular automata, 1034

and convolutional codes, 1119

and texture generation, 1078

Sequential machines

history of, 958

see also Finite automata

Sequential network systems, 936

Sequential substitution systems, 88–92

and causal networks, 499

computational reducibility in, 1134

emulated by CAs, 660, 1111

emulating CAs, 667, 1113

generalized to 2D, 192

and genetic programs, 1002

history of, 894

implementation of, 893

vs. multiway systems, 204, 894

vs. operator evolution systems, 1170

random initial conditions in, 949

vs. sequential CAs, 1034

Serial test, 1085

Series

and Sierpiński pattern, 931

Series expansions

and continuous functions, 1127

in QED, 1060

of special functions, 1134

and three-body problem, 972

Sestina

and rules for poetry, 875

Set entropy, 959

Set theory, 1154

additional axioms for, 1167

axioms for, 774

and consistency of arithmetic, 1168

and continuum hypothesis, 1127

emulating arithmetic, 1160

and Fermat's Last Theorem, 1166

finite, 1171

and finite axiomatizability, 1176

as foundation for math, 1149

and Goodstein sequences, 1163

and history of universality, 1110

needed for word problems, 1160

and proofs of universality, 1127

and proving P!=NP, 1146

selection of axioms for, 800

and transfinite numbers, 1162

SETI (search for extraterrestrial intelligence), 822

and higher perception, 635

history of, 1188

messages to send in, 1189

practical arguments in, 1191

Sets

operators on, 1171

recursive, 1138

and undecidability, 1138

Settling

of granular materials, 986

Sex

and biological evolution, 386, 985, 1002

random determination for offspring, 1192

Sextic (degree 6) equations, 945

Sferics (natural radio signals), 1187