Index



s
sound of letter, 1079

S-boxes
in DES, 960, 1086

S combinator, 711, 1121

S expressions
number of, 989

S matrices
and discrete quantum mechanics, 1060
in particle physics, 1057

S3 (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

Santa Fe Institute, 862, 882

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, 210221
problem of, 342351
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, 441457
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-assembly, 1011, 1193

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, 357360
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, 250254
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, 309314
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 equations, 944, 1141

Sequence homomorphisms (substitution systems), 893

Sequences
analysis of
see Analysis
encoded as integers, 1120
integers as fundamental, 1152
practical methods for studying, 1091
recursive, 128131
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, 8892
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 PNP, 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