Index
s
sound of letter, 1079
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
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