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- )
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, 997
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

Sierpinski, Waclaw (Poland, 1882-1969)
and nested curves, 934

Sierpinski carpet, 933

Sierpinski 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

Sierpinski pyramid, 172

Sieve of Eratosthenes, 132, 909
cellular automaton for, 640

Sigma_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, 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, 997
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- )
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- )
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 perception, 585-588

Sound representation
for cellular automata, 869

Sound waves
in fluids, 1000

Soundex system, 1100

Sounds
properties of, 1079