Index
Shadowing property of chaotic systems, 920
Shafarevich–Tate group, 1164
Shaking
of granular materials, 986
as source of randomness, 968, 969
Shallit, Jeffrey O. (USA/Canada, 1957– )
and continued fractions, 914
Shannon, Claude E. (USA, 1916–2001)
and analog computers, 1129
and Boolean algebra, 1097
and coding theory, 1069
and cryptography, 1086
and information theory, 1071, 1181
and statistical mechanics, 1020
and Turing machines, 1119
Shannon–Fano codes, 1069
Shannon information
for cellular automata, 959
and evolution of languages, 1181
and thermodynamics, 1020
see also Measure entropy
see also Redundancy
Shape space
of antibodies, 1184
Shapes
from aggregation systems, 979
of animals, 421
in complex maps, 933
and human experience, 1177
of leaves, 401–407, 1005
limiting in cellular automata, 929
parametrization of, 980
possible from growth, 1010
smooth from 2D CAs, 980
variation in 2D CAs, 179
Shared subexpressions
in equation solutions, 945
in multilevel logic, 1096
and networks, 1040
and speedups, 1094
Sharks
patterns in teeth of, 1007
Sharpening
and image processing, 1077
Shattering of solids, 995
Shaw, Robert S. (USA, 1946– )
and chaos theory, 971
in Preface, xiii
Sheep
fortune-telling from, 968
Sheffer, Henry M. (USA, 1883–1964)
and axioms for logic, 1151, 1175
and Nand, 1173
Sheffer axioms
and Laws of Form, 1173
for logic, 773, 808
Sheffer stroke
as name for Nand, 1173
Shell patterns, 423
biology of, 1011
and cellular automata, 389
purpose invented for, 387
Shells
as animal artifacts, 1184
biology of, 1008
collecting, 1011
history of studying, 1008
internal, 1008
natural selection of shapes, 417
shapes of, 414–417
Shepherdson, John C. (England, 1926–[2015])
and register machines, 896
Shift-commuting block maps
as cellular automata, 961
and history of CAs, 878
see also Cellular automata
Shift instructions
and CA boundary conditions, 951
and CA implementation, 866
Shift map, 149
and computer experiments, 919
exact iterates of, 919
history of, 961
and origin of randomness, 308
see also Doubling map
see also Rule 170
Shift registers
applications of, 1086
block frequencies in, 594
and CDMA signals, 1188
and cryptography, 1085
and extraterrestrial messages, 1190
flat spectra from, 1081
and history of CAs, 877
vs. linear congruences, 975
linear feedback, 1086
nonlinear feedback, 1088
as precursors to my work, 879
as random generators, 968, 974
searching for long period, 1193
sequences from, 1084
Shift rules
in cellular automata, 883
state transition graphs for, 963
Ships
fracture as issue for, 995
Shipwrecks
recognizing, 1183
Shocks
in CA fluids, 1000
in continuous fluids, 996
in numerical solutions of PDEs, 924
as origin of discreteness, 984
picture of in fluids, 377
as singularities in PDEs, 923
Shor, Peter W. (USA, 1959– )
in Preface, xiii
and quantum computing, 1148
Short descriptions
of general data, 553
Shortcuts
and computational reducibility, 738
and math proofs, 779
and NP completeness, 1148
Shortest descriptions
and algorithmic information, 1067
in block encoding, 1071
for integers, 916
Shortest paths
and distance on networks, 478
geodesics as, 1048
and polynomial time, 1146
see also Geodesics
Shortest programs
and algorithmic information, 1067
for particular sequences, 1186
undecidability of, 1138
see also Smallest programs
Shot noise, 968
in premium bond lottery, 969
Shotgun method
as application of randomness, 1192
Shub, Michael I. (USA, 1943– )
and quadratic pseudorandom generators, 1090
Shuffle-exchange process, 905
Shuffling (of cards), 968, 974
Sierpiński, Waclaw (Poland, 1882–1969)
and nested curves, 934
Sierpiński carpet, 933
Sierpiński pattern
and 2D substitution system, 187
in Cosmati mosaics, 873
formula for, 608
history of, 934
methods for generating, 931
network based on, 197
in network evolution, 509
and recursive multiplication algorithm, 1142
and rule 90, 25, 870
see also Rule 60
see also Rule 90
Sierpiński pyramid, 172
Sieve of Eratosthenes, 132, 909
cellular automaton for, 640
Σn sets, 1139
Signal processing
for SETI, 1189
and Walsh transforms, 1073
Signals
artificial radio, 1188
from pulsars, 1188
recognizing intelligent, 835
Signature
of spacetime metrics, 1051
Significance (statistical), 594
Signs in languages, 1181
Silicon crystal
fracture of, 374
Silverman, Brian (Canada, 1957– )
in Preface, xiii
and WireWorld CA, 1117
Similarities
between natural systems, 298
in memory, 625
Simon, Herbert A. (USA, 1916–2001)
and automated proofs, 1157
Simple behavior
origins of, 351–361
and Principle of Computational Equivalence, 719
Simple groups
classification of finite, 945
Simple programs
crucial experiment on, 23–50
modelling with, 363–369
and searching for technology, 842
world of, 51–113
Simplex
and trivalent networks, 1029
Simplicial complexes, 1050
and approximating space, 1051
and quantum gravity, 1054
Simplicity
of human artifacts, 828
in scientific models, 1025
in ultimate theory of physics, 470, 1026
see also Simple behavior
Simplification
Boolean, 1095
of iterated map formulas, 1098
Simplify
and proofs, 1158
and real algebra, 1154
see also FullSimplify
Simulated annealing, 985
as application of randomness, 1192
for design optimization, 1193
Simulation games
and history of CAs, 877
Simulations
computational complexity of, 1148
and computational irreducibility, 742
as computationally expensive, 872
of financial markets, 1015
and history of complexity, 862
randomness in, 968, 1192
of rule 90 by rule 126, 269
of ultimate theory of physics, 466
see also Emulation
see also Models
Simultaneity
in relativity theory, 523
and spacelike slices, 1041
in the universe, 486
Sin (sine)
as basis for radio signals, 1188
and computational reducibility, 747
and constructible reals, 1129
curve of, 145
curves with curvature from, 418
difficulty of evaluating, 1134
emulating Mod, 1129
in form for iterated map, 921
and formulas for repetition, 607
and Fourier analysis, 1072
and Fourier series, 917
and logistic map formulas, 1098
and musical notes, 1080
and orthogonal bases, 1072
and uniform distribution mod 1, 904
and universal equations, 1129
and Weierstrass functions, 918
Sinai, Yakov G. (Russia/USA 1935– )
and ergodicity of billiards, 1022
Sine-Gordon equation, 163
Single-cell recording, 1075
Singularities
in Navier–Stokes equations, 996
in PDEs, 164, 923
in spacetime and computation speeds, 1130
Singularity theorems (in general relativity), 1048, 1053
Sinh
in solving 2D Ising model, 982, 1133
SinIntegral
curve of, 145
SIS (program for logic minimization), 1096
Sitnikov, Kirill A. (Russia, 1926– )
and 3-body problem, 973
Six-vertex model
as exactly soluble, 1133
SixJSymbol (6j symbol)
and spin networks, 1055
SK machines
and combinators, 898
Skeletons
forms of animal, 420
of radiolarians, 1011
Skepticism
and teleology, 1185
Sketches
and visual perception, 1076
Skewes number
and numbers of primes, 910
Skewing transformations, 933
Skin
pattern of cells in, 1007
see also Pigmentation patterns
Skolem, A. Thoralf (Norway, 1887–1963)
and non-standard arithmetic, 1169
and set theory, 1154
Skulls
process of growth of, 1010
related by transformations, 1010
Skunk
pigmentation pattern of, 426
Slash-dot (/.)
basic examples of, 854
Sleep, 1100
Sliding-block codes
as cellular automata, 961
Slime molds
spiral waves in, 1013
Slopes
digital representation of, 916
Slot (#)
and projection function, 907
Slow dynamics
in 2D cellular automaton, 336
Slow ship (in Game of Life), 964
Smale, Stephen (USA, 1930– )
and chaos theory, 971
in Preface, xiii
Small changes in initial conditions
see Sensitive dependence
Small programs
and computational complexity theory, 758
crucial experiment on, 23–50
world of, 51–113
Small universal Turing machines, 707, 1119
Smallest programs
and algorithmic complexity theory, 1143
and recognition of purpose, 832
for single CA steps, 884
see also Shortest programs
Smell
and experience of dogs, 827
sense of, 1105
Smith, Alvy Ray, III (USA, 1943– )
and branching in plants, 1005
and L systems, 893
in Preface, xiii
and universal CAs, 1115
Smith, Cyril S. (USA, 1903–1992)
and cellular structures, 1039
Smoke patterns, 377
Smoothing
and image processing, 1077
Smoothness
origin of, 327
see also Continuity
SMP (forerunner of Mathematica)
evaluation of recursive functions in, 906
in my personal timeline, 864
my use of, 854
and origins of this book, 18
semantic patterns in, 1156
and tiering of function arguments, 896
Smullyan, Raymond M. (USA, 1919–[2017])
and combinators, 898
Snail shell
growth of, 415
Snakes
pigmentation patterns on, 426
SNOBOL (computer language), 894
Snow
character of, 993
Snowflake pattern
and 2D cellular automaton, 171
and 2D substitution system, 188
Snowflakes, 370
that are the same, 992
history of studies of, 992
issues in modelling, 364, 366
as motivating question, 17
SO(3)
and spin networks, 1055
SO(8) lattice
isotropy of, 980
SO(d)
and spin, 1046
Soap bubbles
packings of, 988
Soap films
vs. Einstein equations, 1052
fluid flow in, 999
in packings, 988
shapes of, 1009
turbulence in, 377
Soap foams
evolution of, 1039
Soccer ball
as defining curved space, 532
as spherical network, 1049
Social animals
and communication, 1180
Social sciences
and complex systems, 862
and defining complexity, 1068
and game theory, 1104
Gaussian distribution in, 977
historical foundations for, 1135
and history of statistics, 1082
mechanistic explanations in, 1185
quantitative laws in, 1014
summary of relations to, 9, 863
Socrates (Greece, ~470–399 BC)
and purpose in nature, 1185
Sofic systems, 958
Softshell
pigmentation pattern on, 426
Software
defining complexity of, 1069
design of as motivation, 18
for experiments in this book, 856
vs. genetic programs, 383, 1003
and history of computing, 1108
intuition from, 872
in practical computers, 1108
used in producing book, 852
Soil samples
tests for life in martian, 1179
Solar
see Sun
Solar system
randomness in, 973
see also Planets
Solid mechanics
as model for animal growth, 1010
Solid-state physics
and quantum theory, 1056
Solids
atomic-scale features on, 1193
breaking of, 374–375
extraterrestrials based on, 1180, 1190
growth of crystals of, 369
history preserved in, 1184, 1195
and memory, 823
modelled with springs, 374
and repeatable randomness, 976
surfaces of and crystal growth, 993
Solitons
and computational irreducibility, 1132
and conservation laws in PDEs, 1023
and elementary particles, 1044
and experimental math, 899
and Fermi–Pasta–Ulam experiment, 1020
optical for SETI, 1189
and sine-Gordon equation, 163
slowing of randomization by, 970
as topological defects, 1045
Solomonoff, Ray J. (USA, 1926–[2009])
and algorithmic randomness, 1068
Solutions
exact, 1133
Sonar data, 1183
Songs
of birds, 826, 1180
of whales, 826, 1180
Sonic booms, 984
Sonification
and auditory perception, 1080
of cellular automata, 869
Sophistication of computations
see Principle of Computational Equivalence
Sort
algorithms for, 1142
lower bound on, 1143
and multiway system, 1036
networks for, 1142
NP completeness in verifying algorithms for, 1145
randomized algorithms for, 1192
and sequential substitution system, 894
and simple model of space, 518
in states of multiway systems, 937
and substitution system, 502
Souls
as defining features of life, 1178
Sound
in 2D, 923
and animal communication, 1180
emitted in fracture processes, 995
Sound compression, 1080
lossy, 572
Sound effects
and auditory perception, 1079
Sound representation
for cellular automata, 869
Sound waves
in fluids, 1000
Soundex system, 1100
Sounds
properties of, 1079